Problem Statement

There is a weighted undirected graph $G$ with $N$ vertices and $0$ edges, and a variable $X$. The vertices of the graph are numbered from $0$ to $N-1$ .
The variable $X$ is initially set to $ X_{0} $.
Define the distance ${\rm dist} (u, v) $ between two vertices $u$, $v$ in the graph $G$ as follows (the sum of the weights of all edges contained in the simple path from the former vertex to the latter).
$$ {\rm dist} (u, v) = 頂点\ u\ から頂点\ v\ への単純パスに含まれる辺すべての重みの総和 $$ The distance at the same vertex is ${\rm dist}(v, v) = 0$.
You are given $Q$ queries of the following forms. Process them in order on the graph $G$ and the variable $X$.

• 1 v w: Connect vertex $v$ and vertex $X$ with an edge of weight $w$. It is guaranteed that in the given input this operation does not create a cycle in the graph $G$.
• 2 u v: If vertex $u$ and vertex $v$ are not connected, output -1. If they are connected, output ${\rm dist} (u, v) $ and add ${\rm dist} (u, v) $ to $X$.
  Then, replace $X$ with its remainder when divided by $N$.
• 3 v: Output the maximum distance over all pairs of vertices contained in the same connected component as vertex $v$. (That is, output the diameter of the tree containing vertex $v$.)
  If there is only $1$ vertex connected to vertex $v$ (only vertex $v$ itself), output 0.
• 4 value: Add the value ${\rm value}$ to $X$. Then, replace $X$ with its remainder when divided by $N$.

Input

$N\ X_{0}\ Q$
${\rm Query}_{1}$
${\rm Query}_{2}$
${\rm Query}_{3}$
$\ \ \ \ \vdots$
${\rm Query}_{i}$
$\ \ \ \ \vdots$
${\rm Query}_{Q}$

• $1 \leq N \leq 2 \times 10^{5}$
• $1 \leq Q \leq 3 \times 10^{5}$
• $0 \leq X_{0} < N$
• For ${\rm Query}_{i}$:
  
  For a type 1 query

  $1\ v_{i}\ w_{i}$

  For a type 2 query

  $2\ u_{i}\ v_{i}$

  For a type 3 query

  $3\ v_{i}$

  For a type 4 query

  $4\ {\rm value}_{i}$

  ・$0 \leq u_{i}, v_{i}, {\rm value}_{i} < N$
  ・$0 \leq w_{i} \leq 10^{9}$
  ・It is guaranteed that type 1 queries do not create a cycle in the graph $G$.


• All inputs are integers.

Output

Suppose a total of $K$ queries of type 2 and type 3 are given. On the $i\ (1 \leq i \leq K)$-th line, output the answer to the corresponding query on one line. Print a newline at the end.

Sample

Sample 1

Input

5 1 10
1 0 1
2 0 1
1 3 5
1 1 3
3 0
1 4 6
2 4 0
2 4 3
2 3 1
3 3

Output

1
9
10
11
8
11

Show the explanation of Sample 1 (click to expand)

Initially, the graph has $N$ vertices and $0$ edges, and the variable is initialized to $X = 1$.

• 1 0 1: In the 1st query, connect vertex $0$ and vertex $X = 1$ with an edge of weight $1$. (b)
• 2 0 1: In the 2nd query, output ${\rm dist}(0, 1) = 1$. As a result, the variable becomes $X = 1 + 1 = 2$. (c)
• 1 3 5: In the 3rd query, connect vertex $3$ and vertex $X = 2$ with an edge of weight $5$. (d)
• 1 1 3: In the 4th query, connect vertex $1$ and vertex $X = 2$ with an edge of weight $3$. (d)
• 3 0: In the 5th query, output the diameter of the tree of the connected component to which vertex $0$ belongs. This is ${\rm dist}(0, 3) = 9$.
• 1 4 6: In the 6th query, connect vertex $4$ and vertex $X = 2$ with an edge of weight $6$. (e)
• 2 4 0: In the 7th query, output ${\rm dist}(4, 0) = 10$. As a result, the variable becomes $X = (2 + 10) \bmod\ 5 = 1$. (f)
• 2 4 3: In the 8th query, output ${\rm dist}(4, 3) = 11$. As a result, the variable becomes $X = (2 + 11) \bmod\ 5 = 3$. (g)
• 2 3 1: In the 9th query, output ${\rm dist}(3, 1) = 8$. As a result, the variable becomes $X = (3 + 8) \bmod\ 5 = 1$. (h)
• 3 3: In the 10th query, output the diameter of the tree of the connected component to which vertex $3$ belongs. This is ${\rm dist}(3, 4) = 11$.

200000 0 9
2 0 1
1 1 1000000000
4 1
1 2 1000000000
4 1
1 3 1000000000
4 1
1 4 1000000000
3 1

-1
4000000000

200000 0 8
1 1 3
2 0 1
1 2 5
2 2 3
2 3 2
1 1 40
1 2 40
2 3 0

3
5
5
88

200000 1 12
1 0 1000000000
1 2 1000000000
4 2
1 2 1000000000
1 4 1000000000
4 2
1 4 1000000000
1 6 1000000000
2 0 6
4 2
1 6 1000000000
2 0 7

6000000000
7000000000