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.