2023 Winter Waterloo Local Contest, Problem E

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

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

• 0 x c d: Add a new vertex indexed ~n+1~ with colour ~c~ to the tree, where ~n~ is the current number of existing vertices. An edge connecting vertex ~x~ and ~(n+ 1)~ with length ~d~ will also be added to the tree.
• 1 x c: Change the colour of vertex ~x~ to ~c~.
• After each operation, you should find a pair of vertices ~u~ and ~v~ ~(1 \le u, v \le n)~ with different colours in the current tree so that the distance between ~u~ and ~v~ is as large as possible.

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

Input Specification

There are multiple test cases. The first line of the input contains an integer ~T~ indicating the number of test cases. For each test case:

The first line of the input contains two integers ~q~ and ~C~ ~(1 \le q \le 5 \times 10^5, 1 \le C \le q)~ indicating the number of operations and the initial colour of vertex ~1~.

For the following ~q~ lines, each line describes an operation taking place in order with ~3~ or ~4~ integers.

• If the ~i~-th line contains ~4~ integers ~0~, ~x_i~, ~c_i~ and ~d_i~ ~(1 \le x_i \le n, 1 \le c_i \le q, 1 \le d \le 10^9)~, the ~i~-th operation will add a new vertex ~n+1~ with colour ~c_i~ to the tree and connect it to vertex ~x_i~ with an edge of length ~d_i~.
• If the ~i~-th line contains ~3~ integers ~1~, ~x_i~ and ~c_i~ ~(1 \le x_i \le n, 1 \le c_i \le q)~, the ~i~-th operation will change the colour of vertex ~x_i~ to ~c_i~.
• It's guaranteed that the sum of ~q~ of all test cases will not exceed ~5 \times 10^5~.

Output Specification

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

Please, DO NOT output extra spaces at the end of each line, or your answer may be considered incorrect!

Sample Input

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

Sample Output

0
0
2
3
2
0