거대 드론 쇼

올해 거대 드론 쇼는 아무 문제 없이 모든 참가자가 계획을 지킨다면 크게 성공할 예정이다.

계획은 세부 사항까지 모두 정해져 있다. 처음에 $n$대의 드론이 지면에 놓여 있다. 움직임을 기술하기 위해 3차원 직교 좌표계를 쓰며, 지면은 평면 $z = 0$이다. $i$번째 드론의 시작 위치는 $(x_i, y_i, 0)$이다.

쇼 도중 통신할 수 있도록 드론 쌍 사이에 $m$개의 케이블이 있다. 케이블은 처음에 지면 위에 놓여 있고, 일부 드론 쌍을 잇는 직선 선분이다. 케이블 네트워크는 연결되어 있다. 어떤 드론에서든 케이블을 따라 다른 모든 드론에 도달할 수 있다. 케이블이 엉키지 않도록 어떤 두 선분도 교차하지 않는다(끝점만 공유할 수 있다).

쇼에서는 $k$번의 이동을 순서대로 수행한다. 각 이동은 드론 한 대의 높이($z$ 좌표)를 바꾼다. 각 이동은 부드럽게 이루어지며, 이전 이동이 끝나야 시작한다. 이동 중에는 일부 드론 사이의 거리가 바뀔 수 있고, 케이블은 어느 정도 늘어날 수 있다. 케이블마다 최대 길이가 정해져 있다. 끝점 드론 사이의 거리가 이 값을 넘으면 케이블이 끊어진다.

주최 측은 일부 케이블이 끊어지는 상황에 대비하고 있다. 그러나 특정 드론 쌍은 직접 또는 간접적으로 계속 통신할 수 있어야 한다. $q$개의 중요한 드론 쌍이 주어질 때, 쇼 도중 어느 시점에 그 쌍의 통신이 불가능해지는지 판단하라. 불가능해진다면 연결을 끊는 이동의 번호를 구하라.

첫 줄에 테스트 케이스의 수 $z$ ($1 \le z \le 400$)가 주어진다. 각 테스트 케이스는 다음 형식이다.

첫 줄에 드론의 수 $n$ ($2 \le n \le 500000$)이 주어진다. 이어서 $n$개의 줄에 $i$번째 드론의 좌표 $x_i$, $y_i$ ($|x_i|, |y_i| \le 10^8$)가 정수 두 개로 주어진다. 같은 시작 위치에 있는 드론은 없다.

다음 줄에는 케이블의 수 $m$ ($1 \le m \le 3n$)이 주어진다. 이어서 $m$개의 줄에 정수 $u$, $v$, $l$ ($1 \le u, v \le n$, $u \ne v$, $1 \le l \le 10^9$)이 주어진다. 이는 연결되는 드론 두 대의 번호와 케이블의 최대 길이이다. 한 쌍의 드론은 최대 하나의 케이블로 연결된다. 각 케이블의 시작 위치에서의 길이는 최대 길이 이내이다.

다음 줄에는 이동의 수 $k$ ($1 \le k \le 500000$)가 주어진다. 이어서 $k$개의 줄에 정수 $v$, $h$ ($1 \le v \le n$, $|h| \le 10^9$)가 주어진다. 이는 움직이는 드론의 번호와 높이 변화량이다. $h$가 양수이면 드론이 올라가고, 음수이면 내려간다. 어떤 드론도 지면 아래로 내려가지 않는다고 가정해도 된다. 즉 모든 $z$ 좌표는 항상 0 이상이다.

마지막 줄에는 확인할 쌍의 수 $q$ ($1 \le q \le 500000$)가 주어진다. 이어서 $q$개의 줄에 드론 번호 $u$, $v$ ($1 \le u, v \le n$, $u \ne v$)가 주어진다.

모든 테스트 케이스에 대해 $n$의 총합은 $1000000$을 넘지 않는다. $k$의 총합과 $q$의 총합도 각각 $1000000$을 넘지 않는다.

각 테스트 케이스마다 $q$개의 정수를 입력 순서대로 한 줄에 하나씩 출력한다. 각 드론 쌍에 대해, 두 드론이 더 이상 통신할 수 없게 된 첫 이동의 번호를 출력한다. 이동 번호는 1부터 시작한다. 쇼 전체 동안 쌍이 계속 연결되어 있다면 $-1$을 출력한다.