Một công ty có ~N~ phòng, kết nối với nhau bằng ~N-1~ hành lang nội bộ có thể di chuyển theo hai chiều sao cho một hành lang nối trực tiếp hai phòng và giữa hai phòng bất kỳ luôn có đường đi đến nhau.

Công ty có ~M~ nhân viên, ban đầu mỗi nhân viên làm việc tại một phòng nhất định. Một phòng có thể có nhiều nhân viên. Phòng, hành lang và nhân viên đều được đánh chỉ số bằng các số nguyên liên tiếp nhau, bắt đầu từ ~1~.

Mỗi nhân viên có một chỉ số hiệu suất cá nhân, ban đầu bằng ~0~.

Khi phòng ~X~ được bổ sung tiện ích, hiệu suất của tất cả nhân viên hiện đang làm việc tại phòng ~X~ tăng thêm ~V~ đơn vị.

Khi một nhân viên bị điều chuyển từ phòng ~A~ qua phòng ~B~, hiệu suất của nhân viên đó giảm đi ~K~ đơn vị, với ~K~ là độ dài quãng đường ngắn nhất từ phòng ~A~ đến phòng ~B~ (tính bằng số hành lang).

Hãy cho biết hiệu suất làm việc của một nhân viên trong quá trình công ty thực hiện việc trang bị tiện ích cho các phòng và điều chuyển nhân viên giữa các phòng.

Input

Vào từ file văn bản HSNV.INP:

• Dòng đầu gồm ba số nguyên ~N~, ~M~, ~Q~ (~2 \le N \le 2 \cdot 10^5~, ~1 \le M, Q \le 2 \cdot 10^5~) lần lượt là số phòng, số nhân viên, số yêu cầu.
• Dòng thứ hai gồm ~M~ số nguyên ~a_1, a_2, \ldots, a_M~, trong đó ~a_i~ là phòng mà nhân viên ~i~ ban đầu làm việc (~1 \le a_i \le N~).
• ~N-1~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~u, v~ (~1 \le u, v \le N~, ~u \ne v~), cho biết có một hành lang nối trực tiếp giữa phòng ~u~ và phòng ~v~.
• ~Q~ dòng tiếp theo mô tả các yêu cầu, thuộc một trong ba dạng sau:
  • e X V: phòng ~X~ được bổ sung tiện ích, tăng thêm ~V~ đơn vị hiệu suất cho tất cả nhân viên hiện đang làm việc tại phòng đó (~1 \le X \le N~, ~0 \le V \le 10^9~).
  • t L R Z: tất cả nhân viên có chỉ số từ ~L~ đến ~R~ đồng loạt được chuyển về phòng ~Z~ (~1 \le L \le R \le M~, ~1 \le Z \le N~).
  • q K: truy vấn hiệu suất hiện tại của nhân viên ~K~ (~1 \le K \le M~).

Đảm bảo có ít nhất một yêu cầu dạng q.

Output

Ghi ra file văn bản HSNV.OUT:

• Với mỗi yêu cầu dạng q K, in ra một số nguyên trên một dòng là hiệu suất hiện tại của nhân viên ~K~.

Scoring

Sample Input 1

3 2 5
1 2
1 2
2 3
q 1
e 2 5
q 2
t 1 1 3
q 1

Sample Output 1

0
5
-2