Your task is to maintain a colorful tree and process queries.

At the beginning, there is only one vertex numbered with color on the tree. Then there are operations of two types coming in order:

• : Add a new vertex indexed with color to the tree, where is the current number of existing vertices. An edge connecting vertex and with length will also be added to the tree.
• : Change the color of vertex to .

After each operation, you should find a pair of vertices and () withdifferentcolors in the current tree so that the distance between and is as large as possible.

The distance between two vertices and is the length of the shortest path from to on the tree.

输入描述:

There are multiple test cases. The first line of the input contains an integer  indicating the number of test cases. For each test case:
The first line of the input contains two integers  and  (, ) indicating the number of operations and the initial color of vertex .
For the following  lines, each line describes an operation taking place in order with  or  integers.
If the -th line contains  integers , ,  and  (, , ), the -th operation will add a new vertex  with color  to the tree and connect it to vertex  with an edge of length .If the -th line contains  integers ,  and  (, ), the -th operation will change the color of vertex  to .
It's guaranteed that the sum of  of all test cases will not exceed .

输出描述:

For each operation output the maximum distance between two vertices with different colors. If no valid pair exists output  instead.

2
1 1
0 1 1 1
5 1
0 1 1 1
0 1 2 1
0 3 3 1
1 4 1
1 3 1

0
0
2
3
2
0