该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

有 $n$ 个人参与接龙游戏，第 $i$ 个人的词库是整数序列 $S_i$。每轮由一个人选择自己词库中长度在 $[2,k]$ 内的连续子序列，作为本轮的接龙序列。

第一轮的接龙序列必须以元素 $1$ 开头；后续每轮的接龙序列必须以上一轮接龙序列的最后一个元素开头。

相邻两轮不能由同一个人进行；但本轮进行接龙的人可以与上上轮或更早轮次的人相同。词库可以在不同轮次中重复使用。

给定 $q$ 个任务。第 $j$ 个任务要求进行恰好 $r_j$ 轮接龙，最后一轮的最后一个元素为 $c_j$。请分别判断每个任务是否存在满足条件的游戏过程。

输入格式

从文件 chain.in 读入。

第一行包含一个正整数 $T$，表示数据组数。

每组数据的第一行包含三个整数 $n,k,q$，表示参与人数、接龙序列长度上限和任务数。

接下来 $n$ 行，第 $i$ 行先给出词库长度 $l_i$，再给出 $l_i$ 个整数 $S_{i,1},S_{i,2},\ldots,S_{i,l_i}$。

接下来 $q$ 行，第 $j$ 行包含两个整数 $r_j,c_j$，描述一个任务。

输出格式

输出到文件 chain.out。

对每组数据的每个任务按输入顺序输出一行。若任务可以完成，输出 $1$；否则输出 $0$。

样例

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\le T\le5$，$1\le n\le10^5$，$2\le k\le2\times10^5$，$1\le q\le10^5$，$1\le l_i,S_{i,j},c_j\le2\times10^5$，$1\le r_j\le100$。每组数据中所有词库长度之和 $L=\sum l_i\le2\times10^5$。

表中 $r$ 表示所有任务的最大轮数。

特殊性质 A：$k=2\times10^5$。

特殊性质 B：$k\le5$。

特殊性质 C：每组数据中，任意一个整数在全部词库中的出现次数之和不超过 $5$。