Cho một cây ~N~ đỉnh, ~M~ nhân viên và ~Q~ truy vấn. Nhân viên ~i~ ban đầu ở đỉnh ~a_i~ và có giá trị là ~0~.

• ~1~ ~u~ ~v~: Mọi nhân viên trong nút ~u~ tăng giá trị lên ~v~.
• ~2~ ~L~ ~R~ ~z~: Tất cả nhân viên có chỉ số từ ~L~ đến ~R~ chuyển sang ở đỉnh ~z~, khi một nhân viên đi từ ~u~ sang ~v~, giá trị của nhân viên bị giảm đi ~dis(u, v)~ là số cạnh trên đường đi đơn này.
• ~3~ ~u~: In ra giá trị nhân viên ~u~.

Input

• ~1 \leq N, M, Q \leq 2*10^5~.
• Dãy ~a~ ~(1 \leq a_i \leq N)~
• ~N-1~ dòng mô tả cây: ~1 \leq u, v \leq N~
• ~Q~ truy vấn thuộc một trong ba loại

Output

Đáp án cho truy vấn loại ~3~

Tính điểm

• Subtask 1: ~1 \leq N, M, Q \leq 2000~
• Subtask 2: ~1 \leq N, M, Q \leq 20000~
• Subtask 3: ~1 \leq N, M, Q \leq 200000~

Input

5 3 8
1 3 5
1 2
2 4
3 5
1 3
1 3 3
2 1 3 4
3 1
3 2
1 1 5
3 1
2 1 2 5 
3 3

Output

-2
0
-2
-4