flowercards

Flower Cards

"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 rules of "UniversalNO" are as follows: Each card has a colour and an integer number. The two players take turns to play cards from their hands, with Alice going first. Initially, the deck is empty. Each turn, the player must choose a card from their hand which has the same colour, the same number, or both, as the card currently on top of the deck (if the deck is empty, any card may be chosen). Then, this card is removed from their hand and placed on the top of the deck. Each player must play one card on their turn, and if no card can be played that player loses.

After Alice and Shinobu played a few rounds, they decided that these original rules depended too much on luck alone. They thus added a new rule: After Alice plays the first card, the two will immediately swap their hands, after which it will be Alice's turn again, and the game then continues according to the normal rules.

Once their hands have been swapped, both players know all the cards in both hands, and can therefore formulate optimal strategies.

Alice and Shinobu have drawn their cards, and are about to begin a new round. For each possible first card Alice can play from her hand, determine who wins given that both players play optimally.

Input format

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 format

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.

Limits

\(1 \leq n_1, n_2 \leq 40000\).
\(1 \leq x_{1, i}, x_{2, i} \leq m \leq 10000\).
\(1 \leq y_{1, i}, y_{2, i} \leq c \leq 10000\).

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

Samples

Sample Input 1	Sample Output 1
2 4 3 2 3 2 4 1 2 2 2 2 1 1	0 0 1

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 2 2 4 1 2 2 1 1 1 1	0 1

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 6 1 2 4 1 6 1 1 3 1 2 2 4 5 5 1 2 2 5 2 6 4 6 1	1 1 1 0 1 1