P9448 [ICPC 2021 WF] Splitstream

### 题意 有一个有 $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`。