T580706 「2025 扬大ACM选拔赛」D - Aya and Momizi

Aya plays chess against her rival Momizi. They are the only two players in the game. The chessboard is very large and can be viewed as a 2D plane. Aya placed $n$ rooks and Momizi placed $m$ rooks. Each rook is a point with integer coordinates on the chessboard. One rook is $\textit{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 Aya and Momizi to decide which rooks are $\textit{attacked}$.

The first line contains two integers $n, m~$ ($1\le n, m\le 2\times 10^5$) —— the number of rooks placed by Aya and the number of rooks placed by Momizi. The $i$-th ($1\le i\le n$) line of the next $n$ lines contains two integers $x, y~$ ($-10^9\le x, y\le 10^9$) —— the location $(x, y)$ of the $i$-th rook placed by Aya. The $i$-th ($1\le i\le m$) line of the next $m$ lines contains two integers $x, y~$ ($-10^9\le x, y\le 10^9$) —— the location $(x, y)$ of the $i$-th rook placed by Momizi. It is guaranteed that the $n+m$ rooks placed by the players are distinct (i.e. **no two rooks have the same location**).

Output a string with length $n$ on the first line. The $i$-th ($1\le i\le n$) character should be $1$ if the $i$-th rook placed by Aya is $\textit{attacked}$ and $0$ otherwise. Output a string with length $m$ on the second line. The $i$-th ($1\le i\le m$) character should be $1$ if the $i$-th rook placed by Momizi is $\textit{attacked}$ and $0$ otherwise.

The sample test case is shown below.  The red points are rooks placed by Aya，and the blue points are rooks placed by Momizi. The rook $(0, 0)$,$(0, -1)$ and $(-1, 0)$ are $\textit{attacked}$.