#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,c 分别表示点数和颜色的种类数。
第二行一个整数 n_1 表示 Alice 初始的牌数。
接下来 n_1 行,其中的第 i 行两个整数 x_{1,i},y_{1,i} 分别表示 Alice 的第 i 张牌的点数和颜色。
接下来一行一个整数 n_2 表示 Shinobu 初始的牌数。
接下来 n_2 行,其中的第 i 行两个整数 x_{2,i},y_{2,i} 分别表示 Shinobu 的第 i 张牌的点数和颜色。

输出格式

输出共 n_1 行,其中第 i 行一个整数 r_i 表示 Alice 第一次出第 i 张牌的情况下游戏的结果。 r_i=0 表示 Shinobu 有必胜策略, r_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 的牌。
若第一张出 (2,3) ,则交换后 Alice 只能出 (2,2) ,接下来 Shinobu 只要出 (2,4) 即可获胜。
若第一张出 (2,4) ,则交换后 Alice 只能出 (2,2) ,接下来 Shinobu 只要出 (2,3) 即可获胜。
若第一张出 (1,2) ,则交换后 Alice 只需出 (1,1) 即可获胜。

样例输入 2

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

样例输出 2

0
1

样例解释 2

若第一张出 (2,4) ,则交换后 Alice 无牌可出,失败。
若第一张出 (1,1) ,则交换后 Alice 只需出 (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

数据范围与提示

对于所有数据, 1\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 # 分值 n_1,n_2 的范围 m,c 的范围
1 9 n_1,n_2\le 10 m=c=1
2 10 m,c\le 10
3 11 n_1,n_2\le 50 m,c\le 2
4 12 n_1,n_2\le 100 m,c\le 100
5 13 n_1,n_2\le 400
6 14 n_1,n_2\le 1000
7 15 n_1,n_2\le 4000 m,c\le 10^3
8 16 n_1,n_2\le 40000 m,c\le 10^4