Given a tree with $n$ nodes and weighted edges, and a sequence $a$ of length $n$.

Define the parent of node $x$ as $fa(x)$, and the root $rt$ satisfies $fa(rt)=rt$.

Define the depth $dep(x)$ of node $x$ as the sum of edge weights on the simple path from $x$ to the root.

There are $m$ operations:

1 l r: For $l \le i \le r$, update $a_i := fa(a_i)$.

2 l r: Query the minimum $dep(a_i)$ for $l \le i \le r$.

Input

The first line contains three space-separated integers $n$, $m$, and $rt$, where $rt$ is the index of the root node.

The next $n-1$ lines each contain three space-separated integers $u, v, w$, representing an edge between $u$ and $v$ with weight $w$.

The next line contains $n$ space-separated integers representing the sequence.

The next $m$ lines each contain three space-separated integers, representing an operation.

Output

For each operation of type 2, output one integer per line representing the answer.

Examples

Input 1

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

Output 1

2
2
0
0

Subtasks

Idea: yummy, Solution: nzhtl1477&memset0, Code: nzhtl1477, Data: nzhtl1477

For $100\%$ of the data, $1\le n,m\le 2\cdot 10^5$, $1\le a_i\le n$, and edge weights are in the range $[0, 10^9]$.