有 $n$ 位参与者，第 $i$ 位参与者持有一个整数序列 $S_i$。一轮操作中，你需要选择一位参与者，并从其序列中选取一个长度在 $[2,k]$ 内的连续子序列。

第一轮选取的子序列首元素必须为 $1$。从第二轮起，本轮子序列的首元素必须等于上一轮子序列的末元素。相邻两轮不能由同一位参与者完成，但可以隔轮再次使用同一位参与者；序列中的元素不会被消耗。

每个询问给出一对 $(r,c)$，要求恰好进行 $r$ 轮且最后一个子序列以 $c$ 结尾。各询问相互独立，请判断是否可行。

输入格式

第一行一个整数 $T$，表示测试数据组数。

每组数据的第一行包含 $n,k,q$。随后给出 $n$ 行：第 $i$ 行先给出 $l_i$，再给出序列 $S_i$ 的 $l_i$ 个元素。最后给出 $q$ 行，每行一个询问 $r_j,c_j$。

输出格式

对每个询问输出一行：可行输出 $1$，否则输出 $0$。

样例 1

1
3 3 7
5 1 2 3 4 1
3 1 2 5
3 5 1 6
1 2
1 4
2 4
3 4
6 6
1 1
7 7

1
0
1
0
1
0
0

数据范围与原题特殊限制

对于所有测试数据，保证：

• $1 \leq T \leq 5$；
• $1 \leq n \leq 10^5$，$2 \leq k \leq 2 \times 10^5$，$1 \leq q \leq 10^5$；
• $1 \leq l_i \leq 2 \times 10^5$，$1 \leq S_{i,j} \leq 2 \times 10^5$；
• $1 \leq r_j \leq 10^2$，$1 \leq c_j \leq 2 \times 10^5$；
• 设 $\sum l$ 为单组测试数据内所有 $l_i$ 的和，则 $\sum l\leq 2\times 10^5$。

特殊性质 A：保证 $k = 2 \times 10^5$。

特殊性质 B：保证 $k \leq 5$。

特殊性质 C：保证在单组测试数据中，任意一个字符在词库中出现次数之和均不超过 $5$。

来源与数据说明

原题页面。以上题意为重新整理的表述，规则、输入输出和约束与原题一致。本题使用独立生成的训练数据，原题测试点表仅说明原比赛范围与特殊性质，本包评分不复刻官方测试点分布。标准输入输出，不要求文件读写。