题目描述
在玩惯了成语接龙之后，小 $ 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 $ 个任务是否可以完成的，即是否存在一个可能的游戏过程满足任务条件。
输入格式
从文件 $ chain.in $ 中读入数据。
本题有多组测试数据。
输入的第一行包含一个正整数 $ 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 $ ，描述一个任务。
输出格式
输出到文件 $ chain.out $ 中。
对于每个任务：输出一行包含一个整数，若任务可以完成输出 $ 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
1
0
1
0
1
0
0
提示
样例 1 解释
在下文中，我们使用 { $ A_i $ }={ $ A_1, A_2, · · · , A_r $ } 表示一轮游戏中所有的接龙序列，{ $ p_i $ }={ $ p_1, p_2, · · · , p_r $ }表示对应的接龙的人的编号。由于所有字符均为一位数字，为了方便我们直接使用数字字符串表示序列。
- 对于第一组询问， $ p_1 = 1 $ 、 $ A_1 = 12 $ 是一个满足条件的游戏过程。
- 对于第二组询问，可以证明任务不可完成。注意 $ p_1 = 1 $ 、 $ A_1 = 1234 $ 不是合法的游戏过程，因为此时 $ |A_1| = 4 > k $ 。
- 对于第三组询问，{ $ p_i $ }={ $ 2, 1 $ }、{ $ A_i $ }={ $ 12, 234 $ }是一个满足条件的游戏过程。
- 对于第四组询问，可以证明任务不可完成。注意{ $ p_i $ }={ $ 2, 1, 1 $ }、{ $ A_i $ }={ $ 12, 23, 34 $ }不是一个合法的游戏过程，因为尽管所有的接龙序列长度均不超过 $ k $ ，但第二轮和第三轮由同一个人接龙，不符合要求。
- 对于第五组询问，{ $ p_i $ }={ $ 1, 2, 3, 1, 2, 3 $ }、{ $ A_i $ }={ $ 12, 25, 51, 12, 25, 516 $ }是一个满足条件的游戏过程。
- 对于第六组询问，可以证明任务不可完成。注意每个接龙序列的长度必须大于等于 $ 2 $ ，因此 $ A_1 $ = $ 1 $ 不是一个合法的游戏过程。
- 对于第七组询问，所有人的词库均不存在字符 $ 7 $ ，因此任务显然不可完成。
样例 2
见选手目录下的 $ chain/chain2.in $ 与 $ chain/chain2.ans $ 。
该样例满足测试点 $ 1 $ 的特殊性质。
样例 3
见选手目录下的 $ chain/chain3.in $ 与 $ chain/chain3.ans $ 。
该样例满足测试点 $ 2 $ 的特殊性质。
样例 4
见选手目录下的 $ chain/chain4.in $ 与 $ chain/chain4.ans $ 。
该样例满足特殊性质 $ A $ ，其中前两组测试数据满足 $ n ≤ 1000 $ 、 $ r ≤ 10 $ 、单组测试数
据内所有词库的长度和 $ ≤ 2000 $ 、 $ q ≤ 1000 $ 。
样例 5
见选手目录下的 $ chain/chain5.in $ 与 $ chain/chain5.ans $ 。
该样例满足特殊性质 $ B $ ，其中前两组测试数据满足 $ n ≤ 1000 $ 、 $ r ≤ 10 $ 、单组测试数
据内所有词库的长度和 $ ≤ 2000 $ 、 $ q ≤ 1000 $ 。
样例 6
见选手目录下的 $ chain/chain6.in $ 与 $ chain/chain6.ans $ 。
该样例满足特殊性质 $ C $ ，其中前两组测试数据满足 $ n ≤ 1000 $ 、 $ r ≤ 10 $ 、单组测试数
据内所有词库的长度和 $ ≤ 2000 $ 、 $ q ≤ 1000 $ 。
数据范围
对于所有测试数据，保证：
- $ 1 ≤ T ≤ 5 $ ；
- $ 1 ≤ n ≤ 10^5 $ ， $ 2 ≤ k ≤ 2 × 10^5 $ ， $ 1 ≤ q ≤ 10^5 $ ；
- $ 1 ≤ l_i ≤ 2 × $ $ 10^5 $ ， $ 1 ≤ S_{i, j} ≤ 2 × $ $ 10^5 $ ；
- $ 1 ≤ r_j ≤ 10^2 $ ， $ 1 ≤ c_j ≤ 2 × 10^5 $ ；
- 设 $ \sum l $ 为单组测试数据内所有 $ l_i $ 的和，则 $ \sum l ≤ 2 × $ $ 10^5 $ 。
特殊性质 $ A $ ：保证 $ k = 2 × 10^5 $ 。
特殊性质 $ B $ ：保证 $ k ≤ 5 $ 。
特殊性质 $ C $ ：保证在单组测试数据中，任意一个字符在词库中出现次数之和均不超过 $ 5 $ 。
