Rooks

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. A rook is attacked by another rook if all of the following hold:

• 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 decide which rooks are attacked.

The first line contains two integers $n_1$ and $n_2$ ($1 \le n_1, n_2 \le 200000$), separated by a single space. They are the number of rooks placed by Prof. Pang and the number of rooks placed by Prof. Shou. The next $n_1$ lines each contain two integers $x, y$ ($-10^9 \le x, y \le 10^9$), separated by a single space, giving the location of one rook placed by Prof. Pang. The next $n_2$ lines follow in the same format for the rooks placed by Prof. Shou. All rooks are at distinct locations.

The first line is a string of length $n_1$. The $i$-th character is 1 if the $i$-th rook placed by Prof. Pang is attacked, and 0 otherwise. The second line is a string of length $n_2$. The $i$-th character is 1 if the $i$-th rook placed by Prof. Shou is attacked, and 0 otherwise.