题目描述

有 $n$ 个人，每个人都有一个整数序列词库。游戏进行若干轮，规则如下：

• 每一轮需要选择一个人，且不能与上一轮选择的人相同。
• 被选中的人需要提供其词库中的一个长度在 $2$ 到 $k$ 之间的连续子序列（子数组）。
• 第一轮提供的子序列必须以数字 $1$ 开头。
• 之后的每一轮，提供的子序列必须以上一轮子序列的最后一个元素开头。

现在有 $q$ 个任务，每个任务给出两个整数 $r$ 和 $c$，请你判断是否能够恰好进行 $r$ 轮，并且最后一轮提供的子序列的最后一个元素恰好为 $c$。如果可以，输出 1；否则输出 0。

输入格式

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

对于每组数据：

• 第一行包含三个正整数 $n, k, q$，分别表示人数、子序列长度上限和任务个数。
• 接下来 $n$ 行，每行先是一个正整数 $l_i$，表示第 $i$ 个人的词库长度，然后是 $l_i$ 个整数，表示该词库的序列。
• 接下来 $q$ 行，每行包含两个正整数 $r_j, c_j$，表示一个任务：是否能够恰好 $r_j$ 轮且最后元素为 $c_j$。

输出格式

对于每个任务，输出一行一个整数：可以则输出 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$ 组数据，$3$ 个人，$k=3$，$7$ 个任务。

• 任务 1：进行 $1$ 轮，结尾为 $2$。可以选第 $1$ 个人的子序列 $[1,2]$（长度 $2$，在 $[2,3]$ 内，且以 $1$ 开头），恰好 $1$ 轮，结尾为 $2$，输出 1。
• 任务 2：$1$ 轮结尾为 $4$。不存在以 $1$ 开头且以 $4$ 结尾的长度在 $[2,3]$ 内的子序列，输出 0。
• 任务 3：$2$ 轮结尾为 $4$。可以第一轮选 $[1,2]$，第二轮选另一个人的以 $2$ 开头、以 $4$ 结尾的子序列，满足条件，输出 1。
• 任务 4：$3$ 轮结尾为 $4$。无法构造满足条件的方案，输出 0。
• 任务 5：$6$ 轮结尾为 $6$。可以构造出长度为 $6$ 的接龙序列，输出 1。
• 任务 6：$1$ 轮结尾为 $1$。不允许长度为 $1$ 的子序列（要求长度至少 $2$），输出 0。
• 任务 7：$7$ 轮结尾为 $7$。不可能，输出 0。

数据范围与提示

• $1 \le T \le 5$
• $1 \le n, q \le 10^5$
• $2 \le k \le 2 \times 10^5$
• 单组数据中所有 $l_i$ 的总和不超过 $2 \times 10^5$
• $1 \le r_j \le 100$
• 序列中的元素均为正整数，且大小不超过 $10^5$