题目描述

在玩惯了成语接龙之后，小 J 和他的朋友们发明了一个新的接龙规则。

总共有 n 个人参与这个接龙游戏，第 i 个人会获得一个整数序列 S_i 作为他的词库。一次游戏分为若干轮，每一轮规则如下：

• n 个人中的某个人 p 带着他的词库 S_p 进行接龙。若这不是游戏的第一轮，那么这一轮进行接龙的人不能与上一轮相同，但可以与上上轮或更往前的轮相同。
• 接龙的人选择一个长度在 [2, k] 的 S_p 的连续子序列 A 作为这一轮的接龙序列，其中 k 是给定的常数。若这是游戏的第一轮，那么 A 需要以元素 1 开头，否则 A 需要以上一轮的接龙序列的最后一个元素开头。
• 序列 A 是序列 S 的连续子序列，当且仅当可以通过删除 S 的开头和结尾的若干元素（可以不删除）得到 A。

为了强调合作，小 J 给了 n 个参与游戏的人 q 个任务，第 j 个任务需要这 n 个人进行一次游戏，在这次游戏里进行恰好 r_j 轮接龙，且最后一轮的接龙序列的最后一个元素恰好为 c_j。为了保证任务的可行性，小 J 请来你判断这 q 个任务是否可以完成的，即是否存在一个可能的游戏过程满足任务条件。

输入格式

本题有多组测试数据。 输入的第一行包含一个正整数 T，表示数据组数。 接下来包含 T 组数据，每组数据的格式如下： 第一行包含三个整数 n, k, q，分别表示参与游戏的人数、接龙序列长度上限以及任务个数。 接下来 n 行：第 i 行包含 (l_i + 1) 个整数 l_i, S_{i,1}, S_{i,2}, ..., S_{i,l_i}，其中第一个整数 l_i 表示序列 S_i 的长度，接下来 l_i 个整数描述序列 S_i。 接下来 q 行：第 j 行包含两个整数 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 <= T <= 5；1 <= n <= 10^5，2 <= k <= 2 x 10^5，1 <= q <= 10^5；1 <= l_i <= 2 x 10^5，1 <= S_{i,j} <= 2 x 10^5；1 <= r_j <= 100，1 <= c_j <= 2 x 10^5；单组测试数据内所有 l_i 的和 <= 2 x 10^5。

本题为 CSP-J 第二轮真题（2024 年，chain）。

在线判题使用官方样例与补充测试数据，程序输出与答案一致即判对。