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 and , denoting the range of card numbers and the number of card colours respectively.
The second line of input consists of a single integer , denoting the initial number of cards in Alice's hand.
The next lines contain 2 integers , each, denoting that Alice's card has a number and colour .
The following line of input consists of a single integer , denoting the initial number of cards in Shinobu's hand.
The next lines contain 2 integers , each, denoting that Shinobu's card has a number and colour .
Output format
Output lines each containing a single integer. On the line, output 0 if Shinobu wins given that Alice plays the card first, and 1 if Alice wins instead.
Limits
.
.
.
Subtask #
|
Score
|
Constraints
|
1 |
9 |
|
2 |
10 |
|
3 |
11 |
|
4 |
12 |
|
5 |
13 |
|
6 |
14 |
|
7 |
15 |
|
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 and colour as .
If Alice's first card is , then after the swap Alice can only play the card , to which Shinobu can play to win.
If Alice's first card is , then after the swap Alice again can only play the card , to which Shinobu can play to win.
If Alice's first card is , then after the swap Alice can play the card 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 , then after the swap Alice has no playable cards and immediately loses.
If Alice's first card is , then after the swap Alice can play either of the two cards 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
|