"Let's play Hanafuda!"
"Hanafuda... But I don't know the rules..."
"Eh......"
Not familiar with the traditional games of her country, Shinobu is helpless! So Alice and Shinobu had to return to the UniversalNO card game they were both familiar with.
The first line of input consists of two integers \(m\) and \(c\), denoting the range of card numbers and the number of card colours respectively.
The second line of input consists of a single integer \(n_1\), denoting the initial number of cards in Alice's hand.
The next \(n_1\) lines contain 2 integers \(x_{1, i}\), \(y_{1, i}\) each, denoting that Alice's \(i^{th}\) card has a number \(x_{1, i}\) and colour \(y_{1, i}\).
The following line of input consists of a single integer \(n_2\), denoting the initial number of cards in Shinobu's hand.
The next \(n_2\) lines contain 2 integers \(x_{2, i}\), \(y_{2, i}\) each, denoting that Shinobu's \(i^{th}\) card has a number \(x_{2, i}\) and colour \(y_{2, i}\).
Output \(n_1\) lines each containing a single integer. On the \(i^{th}\) line, output 0 if Shinobu wins given that Alice plays the \(i^{th}\) card first, and 1 if Alice wins instead.
Subtask #  Score  Constraints 

1  9  \(n_1, n_2 \leq 10\) \(m = c = 1\) 
2  10  \(n_1, n_2 \leq 10\) \(m, c \leq 10\) 
3  11  \(n_1, n_2 \leq 50\) \(m, c \leq 2\) 
4  12  \(n_1, n_2 \leq 100\) \(m, c \leq 100\) 
5  13  \(n_1, n_2 \leq 400\) \(m, c \leq 100\) 
6  14  \(n_1, n_2 \leq 1000\) \(m, c \leq 100\) 
7  15  \(n_1, n_2 \leq 4000\) \(m, c \leq 1000\) 
8  16  No additional constraints 
Sample Input 1  Sample Output 1 
2 4

0

Let's denote a card with number \(x\) and colour \(y\) as \((x, y)\).
If Alice's first card is \((2, 3)\), then after the swap Alice can only play the card \((2, 2)\), to which Shinobu can play \((2, 4)\) to win.
If Alice's first card is \((2, 4)\), then after the swap Alice again can only play the card \((2, 2)\), to which Shinobu can play \((2, 3)\) to win.
If Alice's first card is \((1, 2)\), then after the swap Alice can play the card \((1, 1)\) to immediately win.
Sample Input 2  Sample Output 2 
2 4

0

If Alice's first card is \((2, 4)\), then after the swap Alice has no playable cards and immediately loses.
If Alice's first card is \((1, 2)\), then after the swap Alice can play either of the two cards \((1, 1)\) to immediately win.
Sample Input 3  Sample Output 3 
6 4

1

Subtask  Score 

1  9 
2  10 
3  11 
4  12 
5  13 
6  14 
7  15 
8  16 
9  0 