Karen and Coffee

수업 중에 깨어 있고 집중하려면 카렌에게 커피가 필요하다!

커피 애호가인 카렌은 완벽한 커피 한 잔을 내리기 위한 최적의 온도를 알고 싶어 한다. 실제로 그녀는 모두에게 호평받는 "The Art of the Covfefe"을 비롯한 여러 조리법 책을 읽는 데 시간을 들였다.

그녀는 n개의 커피 조리법을 알고 있다. i-th번째 조리법에서는 최적의 맛을 내려면 커피를 li도 이상 ri도 이하의 온도에서 내려야 한다고 권한다.

카렌은 적어도 k개의 조리법에서 권하는 온도를 허용 가능한 온도라고 생각한다.

카렌은 마음이 꽤 자주 바뀌기 때문에 q개의 질문을 한다. 각 질문에서 그녀가 a도 이상 b도 이하의 온도로만 커피를 준비하려고 할 때, 그 범위에 속하는 허용 가능한 정수 온도가 몇 개인지 알려 주어라.

입력의 첫 번째 줄에는 세 정수 n, k (1 ≤ k ≤ n ≤ 200000), q (1 ≤ q ≤ 200000)가 주어진다. 각각 조리법의 수, 어떤 온도가 허용 가능하려면 그 온도를 권해야 하는 조리법 수의 최솟값, 카렌이 하는 질문의 수를 나타낸다.

다음 n개의 줄에는 조리법이 주어진다. 구체적으로 이 중 i-th번째 줄에는 두 정수 li와 ri (1 ≤ li ≤ ri ≤ 200000)가 주어지며, i-th번째 조리법에서 커피를 li도 이상 ri도 이하의 온도에서 내리도록 권한다는 뜻이다.

다음 q개의 줄에는 질문이 주어진다. 각 줄에는 a와 b, (1 ≤ a ≤ b ≤ 200000)가 주어지며, a도 이상 b도 이하인 허용 가능한 정수 온도의 수를 알고 싶다는 뜻이다.

각 질문마다 a도 이상 b도 이하인 허용 가능한 정수 온도의 수를 나타내는 정수 하나를 한 줄에 출력한다.

첫 번째 테스트 케이스에서 카렌은 3개의 조리법을 알고 있다.

1. 첫 번째 조리법은 커피를 91도 이상 94도 이하의 온도에서 내리도록 권한다.
2. 두 번째 조리법은 커피를 92도 이상 97도 이하의 온도에서 내리도록 권한다.
3. 세 번째 조리법은 커피를 97도 이상 99도 이하의 온도에서 내리도록 권한다.

적어도 2개의 조리법에서 권하는 온도는 허용 가능하다.

그녀는 4개의 질문을 한다.

첫 번째 질문에서 그녀는 92도 이상 94도 이하인 허용 가능한 정수 온도의 수를 알고 싶어 한다. 그러한 온도는 3개이다. 92도, 93도, 94도는 모두 허용 가능하다.

두 번째 질문에서 그녀는 93도 이상 97도 이하인 허용 가능한 정수 온도의 수를 알고 싶어 한다. 그러한 온도는 3개이다. 93도, 94도, 97도는 모두 허용 가능하다.

세 번째 질문에서 그녀는 95도 이상 96도 이하인 허용 가능한 정수 온도의 수를 알고 싶어 한다. 그러한 온도는 없다.

마지막 질문에서 그녀는 90도 이상 100도 이하인 허용 가능한 정수 온도의 수를 알고 싶어 한다. 그러한 온도는 4개이다. 92도, 93도, 94도, 97도는 모두 허용 가능하다.

두 번째 테스트 케이스에서 카렌은 2개의 조리법을 알고 있다.

1. 첫 번째 조리법인 "wikiHow to make Cold Brew Coffee"에서는 커피를 정확히 1도에서 내리도록 권한다.
2. 두 번째 조리법인 "태양 표면 온도의 적어도 36.3306배에 달하는 온도에서 내리지 않은 커피가 무슨 소용인가?"에서는 커피를 정확히 200000도에서 내리도록 권한다.

적어도 1개의 조리법에서 권하는 온도는 허용 가능하다.

그녀의 첫 번째이자 유일한 질문에서 그녀는 실제로 합리적인 허용 가능한 정수 온도의 수를 알고 싶어 한다. 그러한 온도는 없다.