408535: GYM103182 D Melon Seeds

Summer is upon us, so Bob started eating watermelons. As everybody knows, spitting the seeds out (on a plate) makes the experience of eating watermelon that much more enjoyable.

Bob noticed on this particular day that the seeds formed a tree. He gave each of them a value and started applying the following queries on the tree:

• $$$0\ x\ y\ k$$$ - rotate the values on the simple path connecting node $$$x$$$ with node $$$y$$$ (i.e $$$p_1=x,\ p_2,\ \dots,\ p_{L - 1},\ p_L=y$$$ in this order, where $$$L$$$ is the length of the path) $$$k$$$ steps clockwise.
• $$$1\ x\ y$$$ - find out the minimum value on the simple path connecting node $$$x$$$ with node $$$y$$$

Your task is to help Bob answer his queries!

The first line of the input contains an integer $$$N$$$ ($$$1 \leq N \leq 2 \cdot 10^5$$$), the size of the tree.

The second line contains $$$N$$$ integers $$$v_1,\ v_2,\dots,\ v_n$$$ ($$$0 \leq v_i \leq 10^9$$$, $$$1 \leq i \leq N$$$), the values corresponding to the nodes in the tree.

The next $$$N-1$$$ lines each contain two integers $$$a$$$ and $$$b$$$ ($$$1\leq a,b \leq N$$$, $$$a \ne b$$$), the description of the tree.

The next line contains an integer $$$Q$$$ ($$$1 \leq Q \leq 2 \cdot 10^5$$$), the number of queries.

The next $$$Q$$$ lines contain the queries in either one of the following formats:

• $$$0\ x\ y\ k$$$ ($$$1 \leq x, y \leq N$$$, $$$0 \leq k \leq 10^9$$$)
• $$$1\ x\ y$$$ ($$$1 \leq x, y \leq N$$$)

The output should contain, on separate lines, the answer for each query of type $$$1$$$.

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

2
0