Read problems statements in mandarin chinese, russian and vietnamese as well.

Chef has teamed up with Batman and Jim Gordon to save Gotham from Joker's plan.

There are initially N police stations each having a unique id and an encryption key.
All stations are connected, using telephone lines, directly or indirectly, to Gordon's police station
(the one with id R).
In order to provide better protection for all people in Gotham, Batman and Chef have paid for some
new police stations and come up a smart algorithm to test the security of a particular police station.

There are Q queries that the two of them perform on Gotham's infrastructure each being either an addition of a new police station or
a security test, on a particular station, using a key generated by Chef.

Your task is to help our three heroes to perform all the queries succesfully and defeat Joker.

------ Input ------

There is only one test case in each test file.
The first line contains two numbers, N and Q, denoting the number of police stations and
the number of queries respectively.
The second line contains two numbers, R and key, denoting the main station's id and
its encryption key.
Each of the next N-1 lines contains three numbers: u, v, k which represent that there is a
telephone line from v to u and that u's encryption key is k.
Each of the next Q lines contains a query of form:
0 v u k: A new station with id u and encryption key k is added and connected by
a telephone line to v
1 v k: The security test needs two encryption keys a and b such that a minimizes the value of a xor k and b that
maximizes the value of b xor k. a and b are encryption keys that correspond to some nodes that lie on the path, formed by telephone lines,
from police station v to Gordon's police station, R.
The problem requires an online solution. Each query will be encoded using the xor between its real values and the value of the last answer. Please see the note section at the end of the statement to see a piece of code that
shows how the input should be read.

------ Output ------

For each operation of type 1, output a single line containing the two requested values (min-value and max-value) separated by a single space.

------ Constraints ------

$1 ≤ N ≤ 100,000$
$1 ≤ Q ≤ 200,000$
$1 ≤ R, u_{i}, v_{i}, key, k_{i} ≤ 2^{31}− 1$
$All ids are unique (there aren't at any time two police stations with the same id).$
$Whenever you have to connect a node u to another one v, it is guaranteed that v is already connected, directly of indirectly, to R.
$
------ Subtasks ------

Subtask #1 (30 points):
$1 ≤ N ≤ 5000$
$1 ≤ Q ≤ 5000$

Subtask #2 (70 points):
$Original constraints$

----- Sample Input 1 ------
6 4

1 2

5 1 3

2 1 4

3 2 5

4 2 1

6 3 3

1 4 2

6 0 12 0

7 12 7

4 0 7
----- Sample Output 1 ------
0 6

2 7

0 1
----- explanation 1 ------

Initially, there are 6 police stations in Gotham and our heroes have 4 operations to perform
Gordon's station is the one that has id 1 and key 2.

First query: The values on the path from 4 to 1 are 1 xor 2 = 3, 4 xor 2 = 6 and 2 xor 2 = 0. The answer is 0 6.
Second query: The values on the path from 10 to 1 are 6 xor 1 = 7, 3 xor 1 = 2, 5 xor 1 = 4, 4 xor 1 = 5 and 2 xor 1 = 3. The answer is 2 7.
Third query: The values on the path from 5 to 1 are 3 xor 2 = 1 and 2 xor 2 = 0. The answer is 0 1.

The decoded version of all operations is:

1 4 2 (t v k)
0 6 10 6 (t v u k)
1 10 1 (t v k)
1 5 2 (t v k)

Note

cin >> N >> Q;
cin >> R >> key;

for (i = 0; i < N - 1; i++)
{
cin >> u >> v >> k;
}

int last_{answer} = 0;

for (i = 0; i < Q; i++)
{
cin >> t;

// find real value of t
t ^= last_{answer};

if (t == 0)
{
cin >> v >> u >> k;

// find real values for u, v, and k
u ^= last_{answer};
v ^= last_{answer};
k ^= last_{answer};
}
else
{
cin >> v >> k;

// find real values for v, and k
v ^= last_{answer};
k ^= last_{answer};

// compute the requested values
int min_{answer} = ...
int max_{answer} = ...

// update last_{answer}
last_{answer} = min_{answer} ^ max_{answer};
}
}

见题面

见题面