A. Wild Tree
time limit per test
9 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Initially, you are given a tree consisting of a single root vertex numbered $$$1$$$. This vertex contains an integer $$$a_1$$$.

You have to process a sequence of queries, each of which is one of the following three types. Note that the queries must be processed online. The parameters given in the input are encrypted.

Let $$$last$$$ denote the answer to the most recent query of type $$$3$$$. Initially, $$$last = 0$$$. If a type $$$3$$$ query does not find a suitable value (i.e., the answer is -1), then $$$last$$$ becomes $$$0$$$.

The parameters of each query are decoded using the following formulas, where $$$V$$$ is the current number of vertices in the tree before processing the query:

  1. 1 $$$p'$$$ $$$a'$$$ — add a new vertex as a child of an existing vertex.
    • $$$p = ((p' \oplus last) \bmod V) + 1$$$
    • $$$a = ((a' \oplus last) \bmod 10^9) + 1$$$
    The new vertex is automatically assigned the smallest unused positive index, namely $$$V + 1$$$. The value stored in this vertex is $$$a$$$.
  2. 2 $$$v'$$$ $$$a'$$$ — update the value stored in a vertex.
    • $$$v = ((v' \oplus last) \bmod V) + 1$$$
    • $$$a = ((a' \oplus last) \bmod 10^9) + 1$$$
    The value stored in vertex $$$v$$$ is changed to $$$a$$$.
  3. 3 $$$u'$$$ $$$v'$$$ $$$x'$$$ — find the minimum value on a path.
    • $$$u = ((u' \oplus last) \bmod V) + 1$$$
    • $$$v = ((v' \oplus last) \bmod V) + 1$$$
    • $$$x = ((x' \oplus last) \bmod 10^9) + 1$$$
    You have to find the smallest value strictly greater than $$$x$$$ among all values stored in the vertices on the simple path from vertex $$$u$$$ to vertex $$$v$$$ (including both endpoints).

Here, $$$\oplus$$$ denotes the bitwise exclusive OR operation (XOR in C++).

Input

The first line of the input contains two integers $$$a_1$$$ and $$$q$$$ ($$$1 \le a_1 \le 10^9$$$, $$$1 \le q \le 5 \cdot 10^5$$$) — the value written in the root vertex and the number of queries.

The next $$$q$$$ lines contain descriptions of the queries in the encrypted format described in the problem statement.

It is guaranteed that after decryption, all parameters will be valid: $$$1 \le p, v, u \le V$$$, and all values of $$$a$$$ and $$$x$$$ will be in the range from $$$1$$$ to $$$10^9$$$.

Output

For each query of the third type, print a single integer in a separate line — the minimum value on the path that is strictly greater than the decrypted $$$x$$$. If no such number exists on the path, print '-1'.

Example
Input
5 6
1 0 1
1 1 7
3 0 2 2
2 4 6
3 5 7 7
3 4 6 3
Output
5
4
-1