Jump

Problem Description

You are given a rooted tree with $n$ nodes, each edge of the tree has a weight, the nodes of the tree are numbered from $1$ to $n$, the root of the tree is $rt$. You are also given an array $a$ with $n$ elements. Define $dep(x)$ as the sum of weight of edges on the simple path between $rt$ and $x$. Define $fa(x)$ as the father of node $x$, especially, we define $fa(rt)=rt$. There are $m$ operations of two types: 1 l r: for each $i$ that satisfies $l \le i \le r$, $a_i := fa(a_i)$. 2 l r: for each $i$ that satisfies $l \le i \le r$, output the minimum $dep(a_i)$.

Input

The input contains several test cases, and the first line contains a single integer $T$, the number of test cases. For each test case: The first line contains three integers $n,m,rt$. For the following $n-1$ lines, each line contains three integers $u,v,d$, which means that there is an edge between $u,v$, the weight of which is $d$. The next line contains $n$ integers, the ith integer is $a_i$. For the following $m$ lines, each line contains three integers $opt,l,r$, which means that there is a operation of type $opt$ for $l,r$. $1\le T \le 4$, $1\le n,m\le 2\cdot 10^5$, the weight of edge is an integer in range $[0,10^9]$.

Output

For each operation that $opt=2$, output one line representing the answer.

Sample Input

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

Sample Output

5
0
1
5
5
3

Source

2020 Multi-University Training Contest 9