Arthur 拥有一个公牛农场。他的生意非常兴隆，以至于最近他开始为提供足够的牛栏而发愁。他的农场里有 $n$ 个牛栏，还有 $(n-1)$ 头公牛。重要的是，不能有两头公牛共用一个牛栏（否则它们可能会互相伤害）。Arthur 有一个遥控器，可以让他移动牛栏里的公牛。按下按钮会导致所有公牛同时移动。具体来说，如果一头公牛在按下第 $i$ 个按钮之前位于第 $j$ 个牛栏，那么它会移动到第 $t_{i,j}$ 个牛栏。

由于需要修理一些牛栏，Arthur 准备了一份包含 $q$ 个询问的列表。每个询问询问是否可以通过某种方式操纵公牛，使得在最后第 $b$ 个牛栏中没有公牛，前提是开始时只有第 $a$ 个牛栏是空的，并且只能使用前 $c$ 个按钮。记住，在任何时刻，两头公牛都不能共用一个牛栏！

输入格式

输入包含多个测试用例。第一行包含一个整数 $t$ ($1 \le t \le 2000$)，表示测试用例的数量。接下来是各测试用例的描述。

每个测试用例的第一行包含三个整数 $n, \ell, q$ ($1 \le n, \ell \le 2000, 1 \le q \le 10^6$)，分别表示牛栏的数量、遥控器按钮的数量和询问的数量。

接下来的 $\ell$ 行中，第 $i$ 行包含 $n$ 个数字 $t_{i,1}, t_{i,2}, \dots, t_{i,n}$，其中 $t_{i,j}$ 表示按下第 $i$ 个按钮后，第 $j$ 个牛栏中的公牛将移动到的牛栏编号。

接下来的 $q$ 行中，第 $i$ 行包含三个数字 $a_i, b_i, c_i$，表示第 $i$ 个询问的参数。

数字 $t_{i,j}$ 以及 $a_i, b_i, c_i$ 经过编码以减小输入大小。一个数字 $x$ 的编码是一个由两个字符组成的字符串，字符分别为 ASCII 码 $48 + \lfloor x/50 \rfloor$ 和 $48 + (x \bmod 50)$。三个数字的编码是它们各自编码的拼接。例如，字符串 ?;;=EL 编码了三个数字 $761, 563, 1078$。

保证所有测试用例中 $n$ 的总和不超过 $2000$，$\ell$ 的总和不超过 $2000$，且 $q$ 的总和不超过 $10^6$。

保证 $1 \le t_{i,j}, a, b \le n, 0 \le c \le \ell$。

输出格式

对于每个测试用例，在新的一行中打印一个长度为 $q$ 的字符串。如果第 $i$ 个询问中可以安全地移动公牛，则第 $i$ 个字符应为 $1$，否则应为 $0$。

样例

样例输入 1

2
5 2 4
0305040201
0404040404
030300
020500
050102
020501
6 2 4
030603010601
010203060504
030202
060402
050602
060401

样例输出 1

1011
0100

样例输入 2

1
3 3 6
020202
030301
030201
020102
030203
010201
010303
020303
010202
010101

样例输出 2

010101