题目描述

「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

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

0
1

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

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

数据范围与提示

对于所有数据，$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$。