Capoo on tree

Problem Description

Bugcat Capoo planted an apple tree at his doorstep, which has a total of $n$ nodes, and on the $i$-th node, an apple of size $a_i$ grows. Capoo observes and records the growth of the apples every day. He discovers that: On the $i$-th day, if it's raining, all apples of size $x_i$ on the chain from node $u_i$ to node $v_i$ on the tree would grow by $1$ unit; If it's cloudy, all apples of size $x_i$ on the chain from node $u_i$ to node $v_i$ on the tree would shrink by $1$ unit; If it's sunny, then Capoo goes out to check the quality of the apples on the tree. Capoo believes that only apples exceeding size $y_i$ are up to standard apples. He would climb from node $u_i$ to node $v_i$ on the tree, checking all the apples along the path. When Capoo continuously encounters $l_i$ qualifying apples, he gets very happy and records the distance from the starting position $p_i$ to the starting node $u_i$, then stops checking. Otherwise, if there is no set of $l_i$ consecutive up-standard apples on the entire path, Capoo gets disappointed and creates a scene. However, Capoo inadvertently lost all the records of $p_i$. Now, he comes to you with growth records of a total of $m$ days, hoping to find out the distance $dis_i$ from the recorded position $p_i$ to the starting point that he recorded each sunny day he went out to inspect, or to confirm if such a position does not exist. Formally speaking, for an unrooted tree $(V, E)$ of size $n$ with node $i$ having a weight of $a_i$, you need to support the following operations: If we represent the path from $u_i$ to $v_i$ on the tree as

$$path_T(u_i, v_i) = \{p_0, p_1, \cdots, p_k| p_0 = u, p_k = v, (p_i, p_{i + 1})\in E\} $$

That is, we use $p_i$ to represent the $i$-th point on the path, then operations can be expressed as:

• $1$ $u_i$ $v_i$ $x_i$, for each point $p_j$ satisfying $a_{p_j}=x_i$, update $a_{p_j}$ to $a_{p_j} + 1$
• $2$ $u_i$ $v_i$ $x_i$, for each point $p_j$ satisfying $a_{p_j}=x_i$, update $a_{p_j}$ to $a_{p_j} - 1$
• $3$ $u_i$ $v_i$ $l_i$ $y_i$, seek the minimum $j$ that satisfies $\forall k \in [0, l_i), a_{p_{j + k}} \geq y_i$

Input

The first line contains a positive integer $T(1\leq T \leq 100)$, indicating the number of test cases. For each of the next $T$ test cases, the format is: The first line contains two positive integers $n(2\leq n \leq 5*10^5), m(1\leq m \leq 5*10^5)$, which represent the total number of nodes on the tree and the number of operations, respectively. The next line contains $n$ integers, where the $i$-th integer $a_i\ (1\leq a_i\leq n)$ represents the weight of node $i$. The next $n-1$ lines consist of two integers $u_i, v_i(1\leq u_i, v_i \leq n)$ each, indicating an edge on the tree. The following $m$ lines represent $m$ operations, where the first integer $op(1\leq op \leq 3)$ of each line indicates the type of operation.

• If $op=1$, then the next three integers $u_i,v_i,x_i(1\leq u_i, v_i \leq n, 1\leq x_i < n)$ represent increasing the weight of all nodes with value $x_i$ on the path from $u_i$ to $v_i$ by one.
• If $op=2$, then the next three integers $u_i,v_i,x_i(1\leq u_i, v_i \leq n, 1 < x_i \leq n)$ represent decreasing the weight of all nodes with value $x_i$ on the path from $u_i$ to $v_i$ by one.
• If $op=3$, then the next four integers $u_i,v_i,l_i,y_i(1\leq u_i, v_i, l_i, y_i \leq n$) ask for the distance from node $u_i$ to the closest chain with a length of $l_i$ and node weights greater than or equal to $y_i$ on the path from $u_i$ to $v_i$. It is guaranteed that $\sum n \leq 10^6,\sum m \leq 10^6$.

Output

For each query, output a line with a positive integer $dis$ indicating the calculated distance. If the corresponding chain does not exist, output -1.

Sample Input

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

Sample Output

-1
0
-1
3

Source

2023“钉耙编程”中国大学生算法设计超级联赛（9）