광물 수집

여러분은 광산에서 광물을 수집하고 가공하여 회사에 납품하는 일을 하고 있다. 일하는 광산은 반직선의 형태로 되어 있다. 광산에는 매일 아침 $N$개의 종류의 광물이 생성된다. 이때, $i$번 광물은 수직선 $x_i$ 위치에 $y_i$개 생성된다. $(1 \le i \le N)$

회사로부터 받은 특이한 로봇 하나를 원격 조작하여 광물을 채취하고 가공하려고 한다. 이 로봇의 특징은 다음과 같다.

처음 로봇의 위치는 $0$이다.
원하는 위치로 이동할 수 있다. 이때 이동한 거리만큼 에너지를 소모한다.
같은 위치에 있는 광물을 원하는 개수만큼 $1$개씩 담을 수 있다.
1. 로봇은 최대 $M$개 광물을 담을 수 있는 저장소가 있으며, 한 번 담은 광물은 버릴 수 없다.
2. 광물을 담는 데 에너지를 소모하지 않는다.
로봇은 위치 $0$에서 보석을 제조할 수 있다.
1. 보석을 제조하려면 로봇은 저장소에 적어도 $1$개 이상의 광물을 가지고 있어야 한다.
2. 현재 로봇의 저장소에 담긴 광물들을 모두 소모하여 보석을 만든다.
  1. 이때 만든 보석 $j$는 집합 $S_j$로 표현할 수 있으며, 집합 $S_j$는 제조에 사용한 광물 번호의 집합이다.
3. 보석을 제조하는 데 에너지를 소모하지 않는다.

여러분은 일과는 광산에 존재하는 모든 광물을 소모하여 보석을 만들고 로봇을 처음 위치로 돌려놓는 것이다. 똑똑한 여러분은 하루에 일과를 끝낼 수 있는 최소한의 에너지 $E$만큼만 사용하여 로봇을 조종해 보석을 만든다. 당일 일과를 무사히 마쳤다면 다음 날에는 당일 아침과 같은 상태로 복원된다.

회사에서 매일 VIP의 요구 사항 $1$개를 전달받는다. $k$일차 요구 사항은 양의 정수 $a_k$, $b_k$로 구성되어 있다. 이는 $a_k$번 광물과 $b_k$번 광물을 포함한 보석을 요구함을 의미한다. $(1 \le k \le Q)$

$k$일차 요구 사항을 받았을 때, $E$만큼의 에너지를 사용하여 여러분의 일과를 무사히 마치면서 $a_k, b_k \in S_j$를 만족하는 보석 $j$를 만들 수 있는지 판단하는 프로그램을 작성하시오.

첫 번째 줄에 광물의 종류 $N$, 로봇 저장소에 담을 수 있는 광물의 최대 수 $M$, 근무 기간 $Q$가 공백으로 구분되어 주어진다. $(2 \le N, M \le 200\,000;$ $1 \le Q \le 200\,000)$

두 번째 줄에는 $N$개의 줄에 걸쳐 광물의 정보가 주어진다. 그중 $i$번째 줄에는 $i$번 광물의 위치 $x_i$, 광물의 개수 $y_i$가 공백으로 구분되어 주어진다. 주어지는 광물의 위치는 서로 다르다. $(1 \le x_i, y_i \le 10^9)$

그다음 줄부터 $Q$개의 줄에 걸쳐 VIP 고객의 요구 사항이 주어진다. 그중 $k$번째 줄에는 서로 다른 두 개의 광물 $a_k$와 $b_k$가 공백으로 구분되어 주어진다. $(1 \le a_k, b_k \le N;$ $a_k \neq b_k)$

문제

입력

출력