{"raw_statement":[{"iden":"statement","content":"Your task is to maintain a colorful tree and process queries.\n\nAt the beginning, there is only one vertex numbered $1$ with color $C$ on the tree. Then there are $q$ operations of two types coming in order:\n- $0$ $x$ $c$ $d$: Add a new vertex indexed $(n+1)$ with color $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.\n- $1$ $x$ $c$: Change the color of vertex $x$ to $c$.\n\nAfter each operation, you should find a pair of vertices $u$ and $v$ ($1 \\le u, v \\le n$) with $\\textbf{different}$ colors in the current tree so that the distance between $u$ and $v$ is as large as possible.\n\nThe distance between two vertices $u$ and $v$ is the length of the shortest path from $u$ to $v$ on the tree."},{"iden":"input","content":"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:\n\nThe 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 color of vertex $1$.\n\nFor the following $q$ lines, each line describes an operation taking place in order with $3$ or $4$ integers.\n- 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 color $c_i$ to the tree and connect it to vertex $x_i$ with an edge of length $d_i$.\n- 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 color of vertex $x_i$ to $c_i$.\n\nIt's guaranteed that the sum of $q$ of all test cases will not exceed $5 \\times 10^5$."},{"iden":"output","content":"For each operation output the maximum distance between two vertices with different colors. If no valid pair exists output $0$ instead."}],"translated_statement":null,"sample_group":[["2\n1 1\n0 1 1 1\n5 1\n0 1 1 1\n0 1 2 1\n0 3 3 1\n1 4 1\n1 3 1","0\n0\n2\n3\n2\n0"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}