F. Rooks
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Prof. Pang plays chess against his rival Prof. Shou. They are the only two players in the game. The chessboard is very large and can be viewed as a 2D plane. Prof. Pang placed $$$n_1$$$ rooks and Prof. Shou placed $$$n_2$$$ rooks. Each rook is a point with integer coordinates on the chessboard. One rook is attacked by another rook if they satisfy all of the following conditions:

  • They are placed by different players.
  • They have the same $$$x$$$-coordinate or $$$y$$$-coordinate.
  • There is no other rook on the line segment between them.
Help Prof. Pang and Prof. Shou to decide which rooks are attacked.
Input

The first line contains two integers $$$n_1, n_2$$$ ($$$1\le n_1, n_2\le 200000$$$) separated by a single space denoting the number of rooks placed by Prof. Pang and the number of rooks placed by Prof. Shou.

The $$$i$$$-th ($$$1\le i\le n_1$$$) line of the next $$$n_1$$$ lines contains two integers $$$x, y$$$ ($$$-10^9\le x, y\le 10^9$$$) separated by a single space denoting the location $$$(x, y)$$$ of the $$$i$$$-th rook placed by Prof. Pang.

The $$$i$$$-th ($$$1\le i\le n_2$$$) line of the next $$$n_2$$$ lines contains two integers $$$x, y$$$ ($$$-10^9\le x, y\le 10^9$$$) separated by a single space denoting the location $$$(x, y)$$$ of the $$$i$$$-th rook placed by Prof. Shou.

It is guaranteed that the $$$n_1+n_2$$$ rooks placed by the players are distinct (i.e., no two rooks can have the same location).

Output

Output a string with length $$$n_1$$$ on the first line. The $$$i$$$-th ($$$1\le i\le n_1$$$) character should be $$$1$$$ if the $$$i$$$-th rook placed by Prof. Pang is attacked and $$$0$$$ otherwise.

Output a string with length $$$n_2$$$ on the second line. The $$$i$$$-th ($$$1\le i\le n_2$$$) character should be $$$1$$$ if the $$$i$$$-th rook placed by Prof. Shou is attacked and $$$0$$$ otherwise.

Example
Input
3 2
0 0
0 1
1 0
0 -1
-1 0
Output
100
11