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.

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

5
0
1
5
5
3