题目描述

分流系统是一个由节点组成的无环网络，它可以处理有限的数字序列。有两种类型的节点（如图 J.1）：

• 一个分流节点以一个数字序列作为输入，然后将它们交替分配到两个输出。第一个数字分流到输出 $1$，第二个分流到输出 $2$，第三个分流到输出 $1$，第四个分流到输出 $2$，以此类推。
• 一个汇聚节点以两个数字序列作为输入，并将它们交替合并，形成单一输出。首先输出输入 $1$ 的第一个数字，然后是输入 $2$ 的第一个数字，然后是输入 $1$ 的第二个数字，然后是输入 $2$ 的第二个数字，以此类推。如果其中一个输入序列比另一个短，那么在较短的序列用完后，较长序列中的剩余数字将被直接传送到输出，而不进行合并。

整个网络只有一个输入，是正整数序列 $1,2,3,\ldots,m$。任何节点的输出都是可查询的。一个查询将会给定一个 $k$，确定一个节点输出的第 $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$ 行描述这个网络，每行描述一个节点。一个分流节点用 $\texttt{S}\ x\ y\ z$ 的格式描述，其中 $x,y,z$ 分别指定了这个节点的输入，第一个输出和第二个输出。一个汇聚节点用 $\texttt{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)$ 是想要查询这个输出的第 $k$ 个数。序列的下标从 $1$ 开始。

输出格式

对于每个询问输出一行，表示这个输出的第 $k$ 个数。如果没有下标为 $k$ 的数，输出 none。

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

100
99

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

47
98
49
51
53
100

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

2
none
none