暂无测试数据。

我们寻找到的这个地方，作为归宿来说实在太过脆弱，我们所珍视的种种，总会被轻易破坏，倘若这就是我们的宿命，我们将不再屈服，我们已经忍到极限了。

——广

少年们再也无法忍受，决定奋起反抗。

但是他们遇到了卫士的阻碍，于是他们开始与卫士战斗

定义对战胜负的条件为： 少年和卫士按顺序轮流对战， 战败者所在的队伍换下一个人入场， 直到一个人在一次对战中失败， 且所在的队伍没有任何可以上场的人， 则该队伍战败。

给定一个根节点为 $1$ ，大小为 $n$ 的树, 每个点有一个种类值 $val$ ， $m$ 次询问每次先读入两个值 $k_i$ 和 $target$, 然后再读入一个长度为 $k_i$ 的少年组成的序列； 从树的根到点 $target$ 经过的所有点构成的序列为卫士们组成的序列， 查询少年组成的队伍能否战胜卫士组成的队伍。

输入格式

第一行读入 $3$ 个正整数 $n, m, num$ 。分别表示树的大小， 询问个数和颜色种类数。

第 $2$ 行到第 $num+1$ 行每行 $num$ 个为 $0$ 或 $1$ 的整数，其中第 $i+1$ 行第 $j$ 个数表示种类为 $i$ 的少年能否战胜种类为 $j$ 的卫士。

第 $num+2$ 行有 $n$ 个非负整数， 其中第 $i$ 个数表示 $a_i$ 的种类;

第 $num+3$ 行到第 $num+n+2$ 行, 每行两个正整数 $x, y$， 表示 $x$ 到 $y$ 有一条无向边;

接下来 $m$ 组读入，每组第一行读入两个数值 $k_i$ 和 $target$ 第二行读入一个长度为 $k_i$ 的少年组成的序列

输出格式

一共 $m$ 行，每行如果少年们胜出，输出 $1$ ；否则输出 $0$

数据范围

对于 $20\%$ 的数据 $n \leq 5000$

对于另外 $20\%$ 的数据，树是一条链

对于另外 $20\%$ 的数据 $num \leq 2$

对于 $100\%$ 的数据 $n \leq 2000000, num \leq 20, \sum_{i=1}^{m} k_i \leq n$

5 2 2
1 1 
1 0 
1 1 2 1 2 
1 2
1 3
2 4
1 5
3 4
1 1 1 
2 3
2 2

1
0