学生 Z 这学期选修了“编译原理”课程，他对文法非常感兴趣。

一个文法可以表示为 $G = (V_T, V_N, S, P)$。 $V_T$ 表示终结符。 $V_N$ 表示非终结符。 $S$ 表示开始符号，它是推导过程的初始符号，也可以被视为一种特殊的非终结符。 $P$ 表示产生式。产生式分为左右两部分，中间用 "->" 连接。这意味着产生式的左侧可以被右侧替换。例如，左侧为 $S$、右侧为 $Aa$ 的产生式 $S \to Aa$ 表示符号串 $Aa$ 可以用来替换符号串 $S$。

推导是将符号串中的非终结符替换为相应产生式右侧的过程。

文法的最左推导结果从开始符号开始。每次推导都会将符号串中最左侧的非终结符替换为相应产生式右侧的符号串。经过多次推导后得到最终的符号串。

例如，对于文法 "G[S]:S->aaBB B->bb"："a"、"b" 是终结符，"B" 是非终结符，"S" 是开始符号，"S->aaBB" 和 "B->bb" 是产生式，那么 $S \to aaBB \to aabbB \to aabbbb$ 是该文法的一个最左推导，"aabbbb" 是结果。

学生 Z 迫不及待地想写一个文法，但他写的文法相对简单，并满足以下条件： 1. 该文法的每个终结符都是小写英文字母，因此总共只有 26 个终结符。 2. 共有 $n$ 个非终结符，第 $i$ 个非终结符表示为 "[i]"。 3. 每个产生式的左侧只有一个符号，且它是一个非终结符。 4. 一个非终结符只能出现在产生式的左侧一次，也就是说，文法中总共有 $n$ 个产生式。 5. 每个产生式右侧的第一个字符必须是终结符，即不会出现 "[1] -> [2]a" 这样的情况。 6. 由于学生 Z 没有考虑使用哪个符号作为开始符号，任何非终结符都可能成为文法的开始符号。

然而，由于学生 Z 对文法规则掌握得不够好，文法中存在递归定义（即从一个非终结符推导出自身），因此可能无法最终生成完全由终结符组成的符号串。因此，对于每次最左推导，他最多执行 $100^{100}$ 次推导，以确保最终符号串的前 $100^{100}$ 个字符是终结符。

学生 Z 不关心递归定义，他只想知道最终字符串中第 $y$ 个终结符是什么。并且他每次都会重新选择一个非终结符作为开始符号。

输入格式

第一行输入一个正整数 $T(T \le 10)$，表示数据组数。

对于每组测试数据，第一行输入两个正整数 $n(1 \le n \le 1000)$ 和 $q(1 \le q \le 1000)$，分别表示非终结符的数量和查询的数量。数据保证 $n$ 个产生式的总长度不超过 $100,000$ 个字符。

接下来的 $n$ 行，每行包含一个描述产生式的字符串，数据保证第 $i$ 个产生式的左侧有且仅有第 $i$ 个非终结符。

接下来的 $q$ 行，每行包含两个正整数 $x, y(1 \le x \le n, 1 \le y \le 10^{18})$，表示一个查询，$x$ 表示使用第 $x$ 个非终结符作为开始符号，$y$ 表示查询中终结符的位置。

输出格式

对于每个查询，输出一行，表示第 $y$ 个终结符；如果符号串的总长度小于 $y$，则输出 -1。

样例

输入 1

1
3 4
[1]->have[1]ac
[2]->myname[3]id
[3]->no
2 9
3 2
1 20
3 3

输出 1

i
o
e
-1