LibreOJ

147 DFS Order IV

内存限制：384 MB 时间限制：2500 ms

Description

This is a templete problem.

Warning: Large IO data. Please use fast IO, and use Tarjan Algorithm or HLD to find LCA.

Given a rooted tree with $N$ vertices, numbered from $1$ to $N$. The root is at vertex $R$. Each vertex has a value, the value of vertex $i$ is $v_i$.

There are $M$ operations to the tree in 3 types:

  • 1 a x, add $x$ to the value of vertex $a$;
  • 2 a x，add $x$ to each value in subtree $a$;
  • 3 a b，output the sum of values in the simple path from vertex $a$ to vertex $b$.

Input

The first line contains three integers $N,M$ and $R$.
The second line contains $N$ integers $v_1,$ $v_2,$ $\ldots,$ $v_N$.
Each of the next $N-1$ lines contains two numbers, representing an edge.
Each of the next $M$ contains an operation.

Output

For each 3 a b operation, output a single integer, representing the sum of values in the simple path from vertex $a$ to vertex $b$.

Sample

Limits And Hints

$40\%$ of the test cases do not have any 2 a x operation.
All test cases satisfies $1\leqslant N, M\leqslant 10^6,$ $1\leqslant R\leqslant N,$ $-10^6\leqslant v_i, x\leqslant 10^6$.

Samples

Input 1

10 13 5
-2 -7 0 2 -9 -2 -4 9 8 -1
9 8
9 4
9 2
4 10
10 7
10 6
2 1
8 3
7 5
3 8 6
1 7 -8
1 5 -9
1 5 -4
1 4 -2
1 2 -1
3 5 1
1 7 1
3 1 3
1 1 -3
3 10 2
1 1 -8
3 8 4

Output 1

16
-37
7
-1
17

Input 2

10 16 4
-13 -11 5 4 18 13 14 -8 -8 14
4 1
4 10
10 2
2 8
4 7
1 6
8 5
1 3
2 9
3 5 10
1 5 -5
2 9 -4
3 8 6
1 5 -8
2 8 -5
3 8 7
1 9 0
2 10 -3
3 7 6
2 9 -4
2 8 2
3 4 4
2 1 8
1 6 5
3 8 3

Output 2

13
-1
8
18
4
-5