接龙（chain）
题目描述
在玩惯了成语接龙之后，小 J 和他的朋友们发明了一个新的接龙规则。
总共有 n 个人参与这个接龙游戏，第 i 个人会获得一个整数序列 S_i作为他的词库。
一次游戏分为若干轮，每一轮规则如下：
• n 个人中的某个人 p 带着他的词库 Sp 进行接龙。若这不是游戏的第一轮，那么这一轮进行接龙的人不能与上一轮相同，但可以与上上轮或更往前的轮相同。
• 接龙的人选择一个长度在 [2, k] 的 Sp的连续子序列 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ᵢ + 1) 个整数 lᵢ, Sᵢ,₁, Sᵢ,₂, … , Sᵢ,lᵢ，其中第一个整数 lᵢ 表示序列 Sᵢ 的长度，接下来 lᵢ 个整数描述序列 Sᵢ。
接下来 q 行：
第 j 行包含两个整数 rⱼ, cⱼ，描述一个任务。
输出格式
对于每个任务：输出一行包含一个整数，若任务可以完成输出 1，否则输出 0。
样例 1 说明
在下文中，我们使用 {Aᵢ} = {A₁,A₂,⋯,Aᵣ} 表示一轮游戏中所有的接龙序列，{pᵢ} = {p₁,p₂,⋯,pᵣ} 表示对应的接龙的人的编号。由于所有字符均为一位数字，为了方便我们直接使用数字字符串表示序列。
对于第一组询问，p₁ = 1、A₁ = 12 是一个满足条件的游戏过程。对于第二组询问，可以证明任务不可完成。注意 p₁ = 1、A₁ = 1234 不是合法的游戏过程，因为此时 |A₁| = 4 > k。对于第三组询问，{pᵢ} = {2,1}、{Aᵢ} = {12,234} 是一个满足条件的游戏过程。对于第四组询问，可以证明任务不可完成。注意 {pᵢ} = {2,1,1}、{Aᵢ} = {12,23,34} 不是一个合法的游戏过程，因为尽管所有的接龙序列长度均不超过 k，但第二轮和第三轮由同一个人接龙，不符合要求。对于第五组询问，{p_i} = {1, 2, 3, 1, 2, 3}、{Ai} = {12, 25, 51, 12, 25, 516} 是一个满足条件的游戏过程。 • 对于第六组询问，可以证明任务不可完成。注意每个接龙序列的长度必须大于等于 2，因此 A1 = 1 不是一个合法的游戏过程。
• 对于第七组询问，所有人的词库均不存在字符 7，因此任务显然不可完成。
样例 2
该样例满足测试点 1 的特殊性质。
样例 3
该样例满足测试点 2 的特殊性质。
样例 4
该样例满足特殊性质 A，其中前两组测试数据满足 n ≤ 1000、r ≤ 10、单组测试数
据内所有词库的长度和 ≤ 2000、q ≤ 1000。
样例 5
该样例满足特殊性质 B，其中前两组测试数据满足 n ≤ 1000、r ≤ 10、单组测试数
据内所有词库的长度和 ≤ 2000、q ≤ 1000。
样例 6
该样例满足特殊性质 C，其中前两组测试数据满足 n ≤ 1000、r ≤ 10、单组测试数
据内所有词库的长度和 ≤ 2000、q ≤ 1000。
数据范围
| 测试点 | n ≤ | r ≤ | ∑l ≤ | q ≤ | 特殊性质 |
|---|---|---|---|---|---|
| 1 | 10^3 | 1 | 2000 | 10^3 | 无 |
| 2, 3 | 10 | 5 | 20 | 10^2 | |
| 4, 5 | 10^3 | 10 | 2000 | 10^3 | A |
| 6 | 10^5 | 10^2 | 2×10^5 | 10^5 | |
| 7, 8 | 10^3 | 10 | 2000 | 10^3 | B |
| 9, 10 | 10^5 | 10^2 | 2×10^5 | 10^5 | |
| 11, 12 | 10^3 | 10 | 2000 | 10^3 | C |
| 13, 14 | 10^5 | 10^2 | 2×10^5 | 10^5 | |
| 15 ~ 17 | 10^3 | 10 | 2000 | 10^3 | 无 |
| 18 ~ 20 | 10^5 | 10^2 | 2×10^5 | 10^5 | |
| 对于所有测试数据，保证： | |||||
• 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；
• 设 为单组测试数据内所有 l_i 的和，则 。特殊性质 A：保证 k = 2 × 10^5。
特殊性质 B：保证 k ≤ 5。
特殊性质 C：保证在单组测试数据中，任意一个字符在词库中出现次数之和均不超过 5。
特殊性质 B：保证 k ≤ 5。
特殊性质 C：保证在单组测试数据中，任意一个字符在词库中出现次数之和均不超过 5。
样例
输入样例 1
1
3 3 7
5 1 2 3 4 1
3 1 2 5
3 5 1 6
1 2
1 4
2 5
3 4
6 6
1 2
6 6
输出样例 1
1
0
1
0
1
0
0