Splitstream 系统是一个处理有限数字序列的无环节点网络。节点有两种类型（如图 J.1 所示）：

• Split（分流）节点：接收一个数字序列作为输入，并将它们交替分配到两个输出端。第一个数字进入输出 1，第二个进入输出 2，第三个进入输出 1，第四个进入输出 2，依此类推。
• Merge（合流）节点：接收两个数字序列作为输入，并将它们交替合并以形成单个输出。输出序列包含来自输入 1 的第一个数字，然后是来自输入 2 的第一个数字，接着是来自输入 1 的第二个数字，然后是来自输入 2 的第二个数字，依此类推。如果其中一个输入序列比另一个短，则在较短的序列耗尽后，较长序列中剩余的数字将直接传输，不再进行合并。

图 J.1：Split 和 Merge 节点工作原理示意图。

整个网络有一个输入，即正整数序列 $1, 2, 3, \dots, m$。可以查询任何节点的任何输出。查询的目标是确定给定输出序列中第 $k$ 个数字。你的任务是高效地实现这些查询。

输入格式

输入的第一行包含三个整数 $m, n$ 和 $q$，其中 $m$ ($1 \le m \le 10^9$) 是输入序列的长度，$n$ ($1 \le n \le 10^4$) 是节点数量，$q$ ($1 \le q \le 10^3$) 是查询数量。

接下来的 $n$ 行描述网络，每行一个节点。Split 节点格式为 S x y z，其中 $x, y$ 和 $z$ 分别标识其输入、第一个输出和第二个输出。Merge 节点格式为 M x y z，其中 $x, y$ 和 $z$ 分别标识其第一个输入、第二个输入和输出。标识符 $x, y$ 和 $z$ 是不同的正整数。总输入标识为 $1$，其余输入/输出标识符构成从 $2$ 开始的连续序列。除 $1$ 以外的每个输入标识符恰好作为某一个节点的输出出现一次。每个输出标识符最多作为某一个节点的输入出现一次。

接下来的 $q$ 行，每行描述一个查询。每个查询包含两个整数 $x$ 和 $k$，其中 $x$ ($2 \le x \le 10^5$) 是一个有效的输出标识符，$k$ ($1 \le k \le 10^9$) 是该序列中目标数字的索引。序列索引从 $1$ 开始。

输出格式

对于每个查询 $x$ 和 $k$，输出一行，包含由 $x$ 标识的输出序列中的第 $k$ 个数字；如果该索引处没有元素，则输出 none。

样例

输入格式 1

200 2 2
S 1 2 3
M 3 2 4
4 99
4 100

输出格式 1

100
99

输入格式 2

100 3 6
S 1 4 2
S 2 3 5
M 3 4 6
6 48
6 49
6 50
6 51
6 52
5 25

输出格式 2

47
98
49
51
53
100

输入格式 3

2 3 3
S 1 2 3
S 3 4 5
M 5 2 6
3 1
5 1
6 2

输出格式 3

2
none
none