题目描述

A splitstream system is an acyclic network of nodes that processes finite sequences of numbers. There are two types of nodes (illustrated in Figure J.1):

• A split node takes a sequence of numbers as input and distributes them alternatingly to its two outputs. The first number goes to output $1$, the second to output $2$, the third to output $1$, the fourth to output $2$, and so on, in this order.
</li>
• A merge* node takes two sequences of numbers as input and merges them alternatingly to form its single output. The output contains the first number from input $1$, then the first from input $2$, then the second from input $1$, then the second from input $2$, and so on. If one of the input sequences is shorter than the other, then the remaining numbers from the longer sequence are simply transmitted without being merged after the shorter sequence has been exhausted.
</li>

Figure J.1: Illustration of how split and merge nodes work.

The overall network has one input, which is the sequence of positive integers $1, 2, 3, \ldots, m$. Any output of any node can be queried. A query will seek to identify the $k^{th}$ number in the sequence of numbers for a given output and a given $k$. Your task is to implement such queries efficiently.

输入格式

The first line of input contains three integers $m$, $n$, and $q$, where $m$ ($1 \leq m \leq 10^9$) is the length of the input sequence, $n$ ($1 \leq n \leq 10^4$) is the number of nodes, and $q$ ($1 \leq q \leq 10^3$) is the number of queries.

The next $n$ lines describe the network, one node per line. A split node has the format $\texttt{S} \ x \ y \ z$, where $x$, $y$ and $z$ identify its input, first output and second output, respectively. A merge node has the format $\texttt{M} \ x \ y \ z$, where $x$, $y$ and $z$ identify its first input, second input and output, respectively. Identifiers $x$, $y$ and $z$ are distinct positive integers. The overall input is identified by $1$, and the remaining input/output identifiers form a consecutive sequence beginning at $2$. Every input identifier except $1$ appears as exactly one output. Every output identifier appears as the input of at most one node.

Each of the next $q$ lines describes a query. Each query consists of two integers $x$ and $k$, where $x$ ($2 \leq x \leq 10^5$) is a valid output identifier and $k$ ($1 \leq k \leq 10^9$) is the index of the desired number in that sequence. Indexing in a sequence starts with $1$.

输出格式

For each query $x$ and $k$ output one line with the $k^{th}$ number in the output sequence identified by $x$, or $\texttt{none}$ if there is no element with that index number.

题目大意

题意

有一个有 $n$ 个节点的传输数字序列的网络，其中有两种节点：拆分节点和合并节点。拆分节点会将输入序列中的数字交替插入两个输出序列中，合并节点会交替将两个输入序列中的数字插入输出序列中。例如：

$\{1,2,3,4,5\}$ 拆分得 $\{1,3,5\}$ 和 $\{2,4\}$。

$\{2,4\}$ 和 $\{1,3,5\}$ 合并得 $\{2,1,4,3,5\}$。

在网络中，除 $1$ 号外每一个结点的每一个输入端都连接着另一个节点的输出端,$1$ 号节点的输入端为总输入端，每一个输出端不一定连接着另一个节点的输入端。每一个输出端都有着从 $2$ 开始的正整数编号。

将一个数字序列 $\{1,2,\cdots,m\}$ 从 $1$ 号节点的输入端输入网络，你需要求出编号为 $x$ 的输出端输出的序列中的第 $k$ 个数字。

输入格式

第一行三个整数 $n,m,q$。分别表示结点的个数、输入序列为 $\{1,2,\cdots,m\}$、查询的次数。

接下来 $n$ 行，每行一个字母开头，接着是三个整数 $x,y,z$。若字母为 $S$，则表示这是一个拆分节点，$x$ 是它的输入端所连接的输出端编号，$y,z$ 是它的两个输出端的编号；若字母为 $M$，则表示这是一个合并节点，$x,y$ 是它的两个输入端所连接的输出端的编号，$z$ 是它的输出端编号。

再接下来 $q$ 行，每行两个整数 $x,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