#536. 「LibreOJ Round #6」花札

内存限制:512 MiB 时间限制:2500 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: liu_cheng_ao

题目描述

「Let's play Hanafuda!」

「花札吗…… 不过我不知道规则……」

「欸…………」

对自己国家的传统游戏不熟悉,Shinobu 也很无奈呀!于是 Alice 和 Shinobu 只好回到了她们都熟悉的 UniversalNO 纸牌游戏。

「UniversalNO」的规则如下:每张牌有一种颜色和一个点数。两个人轮流出牌,由 Alice 先手,最开始牌堆为空,出的人可以出任意牌(放到牌堆顶),之后出的牌必须和当时牌堆顶的牌的颜色或点数至少有一个相同。有牌可出者必须出,无牌可出者输。

Alice 和 Shinobu 玩了几局后觉得原来的规则太依靠运气,于是她们加了一个新玩法:Alice 出了第一张之后,两个人立即交换手里的牌,然后从 Alice 开始继续按原来的规则进行游戏。当然,这次 Alice 出的牌必须和她刚开始出的颜色或点数至少有一个相同。

交换之后两人都知道对方的手牌(就是开局时自己的手牌),于是就有必胜策略了。

现在已知 Alice 和 Shinobu 手里一开始的牌,请你求出对于 Alice 第一次出牌的每种情况,谁有必胜策略。

输入格式

第一行两个整数 m,cm,c 分别表示点数和颜色的种类数。
第二行一个整数 n1n_1 表示 Alice 初始的牌数。
接下来 n1n_1 行,其中的第 ii 行两个整数 x1,i,y1,ix_{1,i},y_{1,i} 分别表示 Alice 的第 ii 张牌的点数和颜色。
接下来一行一个整数 n2n_2 表示 Shinobu 初始的牌数。
接下来 n2n_2 行,其中的第 ii 行两个整数 x2,i,y2,ix_{2,i},y_{2,i} 分别表示 Shinobu 的第 ii 张牌的点数和颜色。

输出格式

输出共 n1n_1 行,其中第 ii 行一个整数 rir_i 表示 Alice 第一次出第 ii 张牌的情况下游戏的结果。ri=0r_i=0 表示 Shinobu 有必胜策略,ri=1r_i=1 表示 Alice 有必胜策略。

样例

样例输入 1

2 4
3
2 3
2 4
1 2
2
2 2
1 1

样例输出 1

0
0
1

样例解释 1

(x,y)(x,y) 表示一张点数为 xx 颜色为 yy 的牌。
若第一张出 (2,3)(2,3),则交换后 Alice 只能出 (2,2)(2,2),接下来 Shinobu 只要出 (2,4)(2,4) 即可获胜。
若第一张出 (2,4)(2,4),则交换后 Alice 只能出 (2,2)(2,2),接下来 Shinobu 只要出 (2,3)(2,3) 即可获胜。
若第一张出 (1,2)(1,2),则交换后 Alice 只需出 (1,1)(1,1) 即可获胜。

样例输入 2

2 4
2
2 4
1 2
2
1 1
1 1

样例输出 2

0
1

样例解释 2

若第一张出 (2,4)(2,4),则交换后 Alice 无牌可出,失败。
若第一张出 (1,1)(1,1),则交换后 Alice 只需出 (1,1)(1,1) 即可获胜。

样例输入 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

样例输出 3

1
1
1
0
1
1

数据范围与提示

对于所有数据,1n1,n240000,1x1,i,x2,im104,1y1,i,y2,ic1041\le n_1,n_2\le 40000,1\le x_{1,i},x_{2,i}\le m\le 10^4,1\le y_{1,i},y_{2,i}\le c\le 10^4

Subtask # 分值 n1,n2n_1,n_2 的范围 m,cm,c 的范围
1 99 n1,n210n_1,n_2\le 10 m=c=1m=c=1
2 1010 n1,n210n_1,n_2\le 10 m,c10m,c\le 10
3 1111 n1,n250n_1,n_2\le 50 m,c2m,c\le 2
4 1212 n1,n2100n_1,n_2\le 100 m,c100m,c\le 100
5 1313 n1,n2400n_1,n_2\le 400 m,c100m,c\le 100
6 1414 n1,n21000n_1,n_2\le 1000 m,c100m,c\le 100
7 1515 n1,n24000n_1,n_2\le 4000 m,c103m,c\le 10^3
8 1616 n1,n240000n_1,n_2\le 40000 m,c104m,c\le 10^4