레벨 검사

Vasya는 여전히 컴퓨터 게임을 좋아하고, 여전히 게임 테스터로 일한다. 지난번에 만난 이후로 달라진 것은 거의 없다. 코딩을 배울까 고민만 하고 결심을 굳히지는 못했으며, 그 결과 여전히 좁은 방에 갇혀 같은 브라우저 게임을 테스트하고 있다.

얼마 전 게임 디자이너들은 레벨에 비선형 게임 플레이가 필요하다고 결정했다. 이제 게임의 기본 레벨 맵은 끝없는 직사각형 격자 위의 $N$개의 통행 가능한 칸의 집합이다. 플레이어, 무기, 몬스터는 항상 통행 가능한 칸에 위치한다. 한 게임 턴에 플레이어는 현재 칸에서 인접한 통행 가능한 칸으로 이동할 수 있다. 두 칸이 변을 공유하면 인접하다고 한다.

안타깝게도 Vasya에게 이 획기적인 방침 변화는 골칫거리일 뿐이다. 그는 지금 게임의 첫 번째 레벨을 테스트하느라 바쁘다. 문제는 게임 시작 시점에 플레이어에게 무기가 없어서, 몬스터와의 전투는 모두 어이없는 실패로 끝난다는 점이다. 게임 테스터인 Vasya는 플레이어가 몬스터와 처음 마주치기 전에 반드시 무기를 하나라도 찾도록 보장해야 한다. 목표 사용자층의 지능은 늘 그렇듯 바닥에 가깝다. 따라서 실패할 확률이 극히 작아도 그 미래의 플레이어들은 반드시 그렇게 한다.

디자이너들은 첫 번째 레벨에 대해 지나치리만큼 완벽주의를 부린다. 레벨의 기본 맵은 이미 승인되어 고정되었지만, Vasya는 매일 이 레벨에 대한 새로운 오브젝트 배치를 잔뜩 받는다. 오브젝트 배치는 레벨의 어느 칸에 몬스터, 무기, 플레이어의 초기 위치가 있는지를 정의한다. 각 오브젝트 배치마다 Vasya는 위에서 말한 어이없는 실패가 일어날 수 있는지 판단해야 한다. Vasya를 도와주자. Vasya가 두 번째 PoE의 복잡한 게임 플레이를 즐기는 동안 빠르게 배치를 분석하는 프로그램을 작성하라. 플레이어가 무기가 있는 칸으로 이동하면 무기를 자동으로 줍고, 몬스터가 있는 칸으로 이동하면 전투가 반드시 일어난다는 점을 명심하라.

입력 파일의 첫 줄에는 기본 레벨 맵의 통행 가능한 칸 수 $N$이 주어진다 ($1 \le N \le 3 \cdot 10^5$). 다음 $N$개의 줄은 이 칸들을 설명한다. 각 줄에는 두 정수 $x$와 $y$가 주어진다 (칸의 좌표, $0 \le x, y \le 10^6$). 이 칸들은 모두 서로 다름이 보장된다.

다음 줄에는 분석할 오브젝트 배치의 수 $T$가 주어진다 ($1 \le T \le 10^5$). 이어서 $T$개의 블록이 오며, 각 블록은 하나의 오브젝트 배치를 설명한다.

블록은 두 정수 $M$ (몬스터 수)과 $W$ (무기 수)가 있는 줄로 시작한다 ($0 \le M, W \le 10^5$). 다음 줄에는 플레이어가 처음 위치한 칸의 좌표가 주어진다. 그다음 $M$개의 줄에는 몬스터가 있는 칸의 좌표가, 블록의 마지막 $W$개의 줄에는 무기가 있는 칸의 좌표가 주어진다. 이 $(M+W+1)$개의 칸 각각에 대해 두 정수 $x$와 $y$가 주어지며, 이 칸들은 모두 통행 가능하고 서로 다름이 보장된다.

모든 오브젝트 배치에 걸친 몬스터의 총수는 $10^5$을 넘지 않는다. 마찬가지로 모든 오브젝트 배치에 걸친 무기의 총수도 $10^5$을 넘지 않는다.

각 오브젝트 배치에 대해 답을 한 줄에 하나씩 출력한다. 답은 입력 파일에서 오브젝트 배치가 정의된 순서와 같은 순서로 출력해야 한다. 플레이어가 실패할 수 있으면 fail을, 그렇지 않으면 ok를 출력한다.

예제의 세 오브젝트 배치 (p는 플레이어, m은 몬스터, w는 무기):