题目描述

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

总共有 $n$ 个人参与这个接龙游戏，第 $i$ 个人拥有一个整数序列 $S_i$ 作为他的词库。

一次游戏分为若干轮，每一轮规则如下：

1. 某个人 $p$ 选出他的词库 $S_p$ 中的一个连续子序列 $A$ 作为这一轮的“接龙序列”，其长度必须在 $[2, k]$ 之间。
2. 如果是第一轮，那么 $A$ 的第一个元素必须是 $1$。
3. 如果不是第一轮，那么 $A$ 的第一个元素必须与上一轮的接龙序列的最后一个元素相同。
4. 这一轮进行接龙的人不能与上一轮相同。即如果这是第 $j$ 轮（$j > 1$），且第 $j-1$ 轮是由 $q$ 接龙的，那么必须满足 $p \neq q$。

现在有 $q$ 个任务，第 $j$ 个任务给定 $r_j, c_j$，表示要求进行恰好 $r_j$ 轮游戏，且最后一轮的接龙序列的最后一个元素恰好为 $c_j$。

请你判断每个任务是否可以完成。即，判断是否存在一个合法的游戏过程，使得该过程恰好包含 $r_j$ 轮，且第 $r_j$ 轮的接龙序列的最后一个元素恰好为 $c_j$。

输入格式

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

对于每组测试数据： 第一行包含三个整数 $n, k, q$。 接下来 $n$ 行，第 $i$ 行首先包含一个整数 $l_i$，表示第 $i$ 个人的词库序列 $S_i$ 的长度；紧接着有 $l_i$ 个整数，表示序列 $S_i$ 的元素。 接下来 $q$ 行，每行包含两个整数 $r_j, c_j$，表示一个任务。

输出格式

对于每组测试数据，输出 $q$ 行。第 $j$ 行输出一个整数 $1$ 或 $0$：如果第 $j$ 个任务可以完成，输出 $1$；否则输出 $0$。

数据范围

• $1 \le T \le 5$
• $1 \le n \le 10^5$
• $2 \le k \le 2 \times 10^5$
• $1 \le q \le 10^5$
• $2 \le l_i \le 2 \times 10^5$
• $\sum l_i \le 2 \times 10^5$
• 序列中的元素在 $[1, 2 \times 10^5]$ 之间。
• $1 \le r_j \le 100$
• $1 \le c_j \le 2 \times 10^5$