#77. DFS Order IV

DFS Order IV

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 NN vertices, numbered from 11 to NN. The root is at vertex RR. Each vertex has a value, the value of vertex ii is viv_i.

There are MM operations to the tree in 3 types:

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

Input

The first line contains three integers N,MN,M and RR.
The second line contains NN integers v1,v_1, v2,v_2, ,\ldots, vNv_N.
Each of the next N1N-1 lines contains two numbers, representing an edge.
Each of the next MM 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 aa to vertex bb.

Sample

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
16
-37
7
-1
17

Limits And Hints

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