Under construction

Still being built. Things may change

Splitstream

Interview

Time limit3sMemory limit1024 MB

Summary
Given a network of split and merge nodes fed by 1 to m, answer queries for the kth number on any output node.
Level

Medium5 of 10

Topics
Recursion, Simulation, Implementation
Solved
No attempts yet

Problem

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

A split node takes a sequence as input and distributes its numbers alternately to two outputs. The first number goes to output 1, the second to output 2, the third to output 1, and so on.

A merge node takes two sequences as input and merges them alternately into one output. The output contains the first number from input 1, then the first number from input 2, then the second number from input 1, then the second from input 2, and so on. If one input is shorter, the remaining numbers from the longer sequence are passed through unmerged after the shorter sequence runs out.

Figure J.1: How split and merge nodes work.

The overall network has one input, the sequence of positive integers 1, 2, 3, ..., m. Any output of any node can be queried. A query asks for the kth number in the sequence of a given output. Your task is to answer these queries efficiently.

Input

The first line contains three integers m, n, and q. m (1≤m≤1091 \le m \le 10^9) is the length of the input sequence, n (1≤n≤1041 \le n \le 10^4) is the number of nodes, and q (1≤q≤1031 \le q \le 10^3) is the number of queries.

The next n lines describe the nodes, one per line. A split node has the format S x y z, where x is its input, y is its first output, and z is its second output. A merge node has the format M x y z, where x is its first input, y is its second input, and z is its output. The identifiers x, y, and z are distinct positive integers. The overall input is identified by 1, and the remaining input and output identifiers form a consecutive sequence starting 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 contains a query with two integers x and k. x (2≤x≤1052 \le x \le 10^5) is a valid output identifier, and k (1≤k≤1091 \le k \le 10^9) is the index of the desired number in that sequence. Indexing starts at 1.

Output

For each query x and k, print on its own line the kth number in the sequence for output x. If that sequence has no kth element, print none.

Examples3

  1. Example 1

    Input
    200 2 2
S 1 2 3
M 3 2 4
4 99
4 100
    Expected output
    100
99

  2. Example 2

    Input
    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
    Expected output
    47
98
49
51
53
100

  3. Example 3

    Input
    2 3 3
S 1 2 3
S 3 4 5
M 5 2 6
3 1
5 1
6 2
    Expected output
    2
none
none