실 전화기

ACM 시의 도로는 그림 1처럼 완벽한 격자 모양으로 놓여 있다. 모든 교차로는 세로 도로 번호와 가로 도로 번호로 구분된다. 이 도시의 몇몇 건물은 매우 중요해서 경찰이 24시간 감시해야 한다. 건물 하나가 한 블록을 통째로 차지하므로, 각 건물을 격자의 한 칸으로 생각할 수 있다. 그림 1에서 검은 칸이 중요한 건물이며, $1$번 건물은 네 교차로 $(3, 7)$, $(3, 8)$, $(4, 7)$, $(4, 8)$로 둘러싸인 블록에 있다.

ACM 경찰서(APD)는 중요한 건물마다 경찰관 한 명을 배치한다. 경찰관은 자신이 맡은 건물을 둘러싼 네 교차로 중 하나에 서 있어야 한다. 예를 들어 그림 1에서 $1$번 건물을 맡은 경찰관은 $(3, 7)$, $(3, 8)$, $(4, 7)$, $(4, 8)$ 중 한 곳에 서 있어야 한다.

경찰관들은 서로 연락을 주고받아야 한다. 서장은 장난감을 무척 좋아해서 무전기를 모두 없애고 대신 실 전화기를 쓰게 했다. 실 전화기는 종이컵 두 개(때로는 깡통 두 개)를 실로 이은 것으로, 실이 팽팽하게 당겨져 있을 때에만 작동한다. 실은 건물을 통과할 수 없으므로 항상 도로를 따라 이어진다. 따라서 교차로 $(x_1, y_1)$과 $(x_2, y_2)$에 서 있는 두 경찰관은, 두 사람을 잇는 실의 길이가 도로를 따라 잰 최단 거리 $|x_1 - x_2| + |y_1 - y_2|$와 같을 때에만 통화할 수 있다.

그림 1. ACM 시의 도로와 중요한 건물의 위치.

모든 실 전화기가 제대로 작동하도록 경찰관들이 설 교차로를 정해 주어야 한다. $1$번부터 $n$번까지 번호가 붙은 중요한 건물 $n$개의 위치가 주어진다. 건물들은 서로 충분히 떨어져 있어서 어떤 두 건물도 둘러싼 교차로를 공유하지 않는다. 또한 어떤 경찰관들이 실 전화기를 함께 쓰는지와 각 실의 길이가 그림 2(a)와 같은 가중치 연결 그래프로 주어진다. 정점 $i$($i = 1, 2, \ldots, n$)는 $i$번 건물을 맡은 경찰관을 뜻한다. 간선 $(i, j)$는 $i$번 건물과 $j$번 건물을 맡은 두 경찰관이 실 전화기를 함께 쓴다는 뜻이며, 간선의 가중치는 그 실의 길이다. 이 그래프는 항상 연결되어 있다. $n$명의 경찰관을 배치해 모든 실 전화기가 작동하게 할 수 있는지 판별하여라. 그림 2(b)는 예제에 대한 올바른 배치 하나를 보여 준다. 작은 원이 경찰관이 선 교차로이며, 모든 도로 거리가 해당 실의 길이와 일치함을 확인할 수 있다.

그림 2. 실 전화기의 길이와 경찰관의 올바른 배치.

입력은 표준 입력으로 주어진다. 첫 줄에는 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스의 형식은 다음과 같다.

첫 줄에는 중요한 건물의 수 $n$이 주어지며, $1 \le n \le 3000$이다. 이어지는 $n$개의 줄에는 각각 두 정수 $x$와 $y$가 주어진다. 그중 $i$번째 줄은 $i$번 건물이 네 교차로 $(x, y)$, $(x+1, y)$, $(x, y+1)$, $(x+1, y+1)$로 둘러싸인 블록에 있음을 뜻하며, $1 \le x, y \le 3000000$이다. 그다음 줄에는 간선의 수 $m$이 주어지며, $1 \le m \le 300000$이다. 이어지는 $m$개의 줄에는 각각 세 정수 $u$, $v$, $d$가 주어지며, 이는 정점 $u$와 $v$ 사이에 가중치가 $d$인 간선이 있음을 뜻한다. $1 \le d \le 6000000$이다.

표준 출력으로 출력한다. 각 테스트 케이스마다 한 줄을 출력한다. 모든 실 전화기가 작동하도록 경찰관을 모두 배치할 수 있으면 possible을, 그렇지 않으면 impossible을 출력한다.