Humanity's Last Code Exam / 2021_J / Splitstream

## Problem Statement

A splitstream system is an acyclic network of nodes that processes finite sequences of numbers. There are two types of nodes:

- **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.

- **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 input sequence is shorter than the other, the remaining numbers from the longer sequence are transmitted without merging after the shorter sequence is exhausted.

The overall network has one input, which is the sequence of positive integers 1,2,3,…,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.

## Input

The first line of input contains three integers m, n, and q, where m (1≤m≤10⁹) is the length of the input sequence, n (1≤n≤10⁴) is the number of nodes, and q (1≤q≤10³) is the number of queries.

The next n lines describe the network, one node per line. A split node has the format `S x y z`, where x, y, and z identify its input, first output, and second output, respectively. A merge node has the format `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≤x≤10⁵) is a valid output identifier and k (1≤k≤10⁹) is the index of the desired number in that sequence. Indexing in a sequence starts with 1.

## Output

For each query x and k, output one line with the k-th number in the output sequence identified by x, or `none` if there is no element with that index number.

## Sample Input 1

## Problem Statement

A splitstream system is an acyclic network of nodes that processes finite sequences of numbers. There are two types of nodes:

- **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.

- **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 input sequence is shorter than the other, the remaining numbers from the longer sequence are transmitted without merging after the shorter sequence is exhausted.

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.

## Input

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 `S x y z`, where \(x\), \(y\), and \(z\) identify its input, first output, and second output, respectively. A merge node has the format `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.

## Output

For each query \(x\) and \(k\), output one line with the \(k\)-th number in the output sequence identified by \(x\), or `none` if there is no element with that index number.

## Sample Input 1