Un système de bifurcation est un réseau acyclique de nœuds qui traite des suites finies de nombres. Il existe deux types de nœuds (illustrés à la figure J.1) :

• Un nœud de séparation reçoit une suite de nombres en entrée et les répartit alternativement entre ses deux sorties. Le premier nombre va à la sortie 1, le deuxième à la sortie 2, le troisième à la sortie 1, le quatrième à la sortie 2, et ainsi de suite dans cet ordre.
• Un nœud de fusion reçoit deux suites de nombres et les entrelace pour former son unique sortie. Celle-ci contient le premier nombre de l’entrée 1, puis le premier de l’entrée 2, puis le deuxième de l’entrée 1, puis le deuxième de l’entrée 2, et ainsi de suite. Si l’une des suites d’entrée est plus courte que l’autre, une fois la plus courte épuisée, les nombres restants de la plus longue sont simplement transmis sans entrelacement.

Delta de Ganga-Brahmaputra (ESA, CC BY-SA 3.0 IGO)

Figure J.1 : Illustration du fonctionnement des nœuds de séparation et de fusion.

Le réseau entier a une entrée : la suite d’entiers strictement positifs $1,2,3,\ldots,m$. Toute sortie de tout nœud peut faire l’objet d’une requête. Pour une sortie et un entier $k$ donnés, une requête cherche le $k$-ième nombre de la suite correspondante. Votre tâche est de traiter efficacement ces requêtes.

Entrée

La première ligne contient trois entiers $m$, $n$ et $q$, où $m$ ($1 \le m \le 10^9$) est la longueur de la suite d’entrée, $n$ ($1 \le n \le 10^4$) le nombre de nœuds et $q$ ($1 \le q \le 10^3$) le nombre de requêtes.

Les $n$ lignes suivantes décrivent le réseau, à raison d’un nœud par ligne. Un nœud de séparation a le format S x y z, où $x$, $y$ et $z$ identifient respectivement son entrée, sa première sortie et sa deuxième sortie. Un nœud de fusion a le format M x y z, où $x$, $y$ et $z$ identifient respectivement sa première entrée, sa deuxième entrée et sa sortie. Les identifiants $x$, $y$ et $z$ sont des entiers strictement positifs distincts. L’entrée globale porte l’identifiant $1$ et les autres identifiants d’entrée/sortie forment une suite consécutive commençant à $2$. Chaque identifiant d’entrée autre que $1$ apparaît comme exactement une sortie. Chaque identifiant de sortie apparaît comme entrée d’au plus un nœud.

Chacune des $q$ lignes suivantes décrit une requête. Une requête comporte deux entiers $x$ et $k$, où $x$ ($2 \le x \le 10^5$) est un identifiant de sortie valide et $k$ ($1 \le k \le 10^9$) est l’indice du nombre recherché dans cette suite. L’indexation commence à $1$.

Sortie

Pour chaque requête $x$ et $k$, affichez sur une ligne le $k$-ième nombre de la suite de sortie identifiée par $x$, ou none s’il n’existe aucun élément à cet indice.

Exemples

Entrée 1

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

Sortie 1

100
99

Entrée 2

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

Sortie 2

47
98
49
51
53
100

Entrée 3

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

Sortie 3

2
none
none