题目背景

小 A 最近迷上了逻辑推理，所以小 B 给他出了一道题。

题目描述

小 B 的题目可以抽象成下面的形式。

题目一共有 $n$ 个逻辑变量 $A_1\sim {A_n}^{[1]}$ ，$m$ 个推理规则，以及 $q$ 个询问。

其中，推理规则均形如 $S_i\Rightarrow[A_{T_i} = \texttt{true}]$，且 $T_i\in[1,n]$。

$S_i$ 满足下面的限制：

1. $S_i$ 用后缀表达式给出，而且各个子串用空格隔开。

2. $S_i$ 是一个合法的表达式$^{[2]}$。

比如说，A1 A2 & A3 | 就是一个合法的 $S_i$。

同时，定义 $|S_i|$ 为 $S_i$ 中字符串的个数。

定义一次推理：若当前的 $A$ 能使 $S_i$ 为真$^{[3]}$，得出 $A_{T_i}=\texttt{true}$。

接下来有 $q$ 次互相独立的询问。每次询问给定推理的初始条件，即若干个 $i$ 满足 $A_i=\texttt{true}$。问最少需要几次推理才可以推出 $A_x=\texttt{true}$。如果无解，请输出 -1。

---

对题目部分内容的解释：

$[1]$：逻辑变量：指只有真值或假值的变量，你可以认为 C++ 中的 bool 是一种逻辑变量。

$[2]$：合法的表达式：

1. 单个变量是合法的表达式（在输入中形如 $\texttt{Ax}$，如 $\texttt A1$、$\texttt A114$）。

2. 若 $A$ 与 $B$ 都是合法的表达式，则 $A\ B\ \texttt{|}$ 与 $A\ B\ \texttt{\&}$ 都是合法的表达式。

$[3]$：怎样的 $A$ 才能使 $S_i$ 为真？

1. 将 $S_i$ 中的 $\texttt{Ax}$ 替换成 $A_x$ 的真假值。需要注意的是，这样并不会真正修改 $S_i$。比方说，A1 A2 | A3 & 在 $A=(\texttt{true},\texttt{false},\texttt{true})$ 的时候 $S_i$ 就会被替换成 true false | true &。

2. 将替换过后的 $S_i$ 进行表达式计算，其中：

• | 表示逻辑或、& 表示逻辑与。

• 将原来的表达式按照后缀表达式计算。

3. 最后的结果（$\texttt{true}$ 或者 $\texttt{false}$）就代表了当前的 $A$ 能否满足 $S_i$。

输入格式

本题有多组测试数据。

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

接下来包含 $T$ 组数据，每组数据的格式如下：

第一行包含三个整数 $n,m,q$。

接下来 $2m$ 行为 $m$ 个推理规则：

• 第 $2i$ 行包含两个数 $|S_i|,T_i$。

• 第 $2i+1$ 行包含 $|S_i|$ 个字符串，表示 $S_i$。

接下来 $q$ 行为 $q$ 次询问，每次询问给定一个字符串 $s$ 和一个整数 $x$。其中 $x$ 表示需要推出的条件，$|s|=n$ 且：

• 如果 $s_i=\texttt{1}$，那么 $A_i=\texttt{true}$。

• 如果 $s_i=\texttt{0}$，那么 $A_i=\texttt{false}$。

输出格式

对于每组测试数据输出 $q$ 行，每行包含一个整数，表示询问的答案。

2
4 4 3
7 4
A1 A2 | A2 A3 | &
5 2
A1 A3 A4 & |
5 1
A2 A3 & A4 |
1 1
A1
1010 4
1101 2
1000 4
3 0 2
100 1
100 2

1
0
2
0
-1

提示

【样例解释】

对于第 $1$ 个询问，直接运用第一个推理规则即可。

对于第 $3$ 个询问，按顺序运用第 $2$ 和第 $1$ 个推理规则即可。

【数据范围】

本题采用捆绑测试。

记 $\sum q$ 表示单个测试点中 $q$ 的和。

$\text{Subtask}$	$n\le$	$m\le$	$\vert S_i\vert\le$	$\sum q\le$	分值
$1$	$10$			$100$	$10$
$2$	$15$	$30$		$1000$	$20$
$3$	$18$	$100$		$5\times10^5$	$30$
$4$	$20$				$40$

对于所有的测试数据，保证：$1\le T\le 10$，$1\le n\le 20$，$1\le m,|S_i|\le 100$，$1\le \sum q\le 5\times10^5$。

【提示】

本题输入量较大，请使用较快的输入方式。