보물 찾기

Timmy의 생일을 맞아 부모님이 해적 테마 파티를 열어 주셨다! 마당에 보물이 묻혀 있고, 이제 Timmy와 해적단이 그것을 찾아야 한다. 보물이 어디에 묻혀 있는지 누가 볼 수 있는지 알려 주어 해적들이 보물을 찾도록 도와주자.

게임을 재미있게 만들기 위해 마당에 시야를 가리는 벽이 세워져 있다. 각 해적은 무엇을 볼 수 있는지 결정하는 시야 범위를 가진다. 각 해적은 일정 거리까지 볼 수 있으며, 바라보는 방향을 기준으로 반원 모양으로만 볼 수 있다(아래 그림 참고). 보고 있는 점과 보고 있는 해적 사이에 다른 해적이나 벽의 일부가 곧바로 놓여 있으면 그 점은 해적의 시야 범위에 들어와도 볼 수 없다. 각 해적은 하나의 점이고, 각 벽은 두께가 없는 선이다.

보물이 묻힌 곳을 볼 수 있는 해적은 누구인가?

그림 F.1: 왼쪽 그림은 예제 입력 1을 나타내며, 가장 오른쪽 해적만이 묻힌 보물의 위치를 볼 수 있다. 오른쪽 그림은 예제 입력 2를 나타내며, 가운데 해적만이 묻힌 보물을 볼 수 있다.

입력의 첫째 줄에는 벽의 개수 $W$ ($0 \leq W \leq 1 \, 000$)와 해적의 수 $P$ ($1 \leq P \leq 1 \, 000$)가 주어진다.

둘째 줄에는 보물의 좌표가 주어진다.

다음 $W$개의 줄은 벽을 나타낸다. 각 줄에는 이 벽의 두 끝점인 두 좌표 $(x,y)$와 $(x',y')$가 주어진다. 두 끝점은 서로 다르다.

다음 $P$개의 줄은 해적을 나타낸다. $i$번째 줄에는 $i$번째 해적의 위치인 좌표 $(x_i,y_i)$와 이 해적이 바라보는 방향으로 볼 수 있는 가장 먼 점인 $(x_i',y_i')$가 주어진다. 두 좌표는 서로 다르다. 즉, 이 해적의 반원 반지름은 $(x_i, y_i)$와 $(x_i',y_i')$ 사이의 거리이다.

모든 좌표는 $|x|,|y| \leq 10^9$인 정수 쌍 $(x,y)$이다. 두 해적이 같은 좌표에 위치하지 않고, 보물은 어떤 해적과도 같은 좌표를 가지지 않으며, 어떤 벽의 일부도 해적이나 보물에 닿지 않는다. 벽은 다른 벽과 어떤 방식으로든 겹칠 수 있다.

$P$개의 줄을 출력한다. 각 줄은 해적 하나에 대응한다. $i$번째 줄에는 $i$번째 해적이 보물이 묻힌 곳을 볼 수 있으면 visible, 아니면 not visible을 출력한다.