룩

면접 대비

시간 제한2초메모리 제한1024 MB

요약

두 플레이어의 룩 좌표가 주어질 때, 같은 행이나 열에서 사이에 다른 룩 없이 상대 룩과 맞닿은 룩을 찾아 표시합니다.

난이도: 보통10점 중 4점
유형: 정렬, 해시맵, 구현
정답자: 아직 제출이 없습니다

문제

Pang 교수는 라이벌 Shou 교수와 체스를 둔다. 게임에는 두 명의 플레이어만 있다. 체스판은 매우 크며 2차원 평면으로 볼 수 있다. Pang 교수는 룩 $n_1$ 개를, Shou 교수는 룩 $n_2$ 개를 놓았다. 각 룩은 체스판 위의 정수 좌표를 갖는 점이다. 한 룩이 다른 룩을 공격한다는 것은 다음 조건을 모두 만족하는 경우이다.

두 룩을 놓은 플레이어가 서로 다르다.
x좌표 또는 y좌표가 같다.
두 룩을 잇는 선분 위에 다른 룩이 없다.

Pang 교수와 Shou 교수가 어떤 룩이 공격받는지 알 수 있도록 도와라.

입력

첫 줄에 두 정수 $n_1$ , $n_2$ ( $1 \le n_1, n_2 \le 200000$ )가 공백으로 구분되어 주어진다. 각각 Pang 교수가 놓은 룩의 개수와 Shou 교수가 놓은 룩의 개수이다. 이어지는 $n_1$ 개 줄에는 Pang 교수가 놓은 룩의 좌표 $x, y$ ( $-10^9 \le x, y \le 10^9$ )가 공백으로 구분되어 한 줄에 하나씩 주어진다. 그다음 $n_2$ 개 줄에는 Shou 교수가 놓은 룩의 좌표가 같은 형식으로 주어진다. 모든 룩의 위치는 서로 다르다.

출력

첫 줄에는 길이 $n_1$ 의 문자열을 출력한다. $i$ 번째 문자는 Pang 교수의 $i$ 번째 룩이 공격받으면 1, 그렇지 않으면 0이다. 둘째 줄에는 길이 $n_2$ 의 문자열을 같은 방식으로 출력한다. Shou 교수의 $i$ 번째 룩이 공격받으면 $i$ 번째 문자는 1이고, 그렇지 않으면 0이다.

예제1

예제 1
입력
```
3 2
0 0
0 1
1 0
0 -1
-1 0
```
예상 출력
```
100
11
```