Vương quốc có ~n~ thành phố và ~n-1~ con đường hai chiều, đảm bảo đi lại giữa mọi cặp thành phố. Thành phố x được gọi là quản lý ~y~ nếu ~x~ nằm trên đường đi đơn từ ~y~ đến 1. Sản lượng lương thực tại thành phố ~x~ là ~w_x~. Quốc vương muốn chọn ra một đỉnh để xây dựng kho dự trữ, chi phí vận chuyển lương thực nếu xây dựng kho dự trữ tại ~u~ là ~∑_{v=1}^n {w_v×d(v,u)}~ với ~d(v,u)~ là số cạnh trên đường đi đơn từ ~v~ đến ~u~.

Có ~Q~ thay đổi cho sản lượng được báo cáo, mỗi thay đổi có dạng ~1\ u\ c~ hoặc ~2\ u\ c~ tương ứng là tăng ~w_u~ lên ~c~ đơn vị hoặc tăng ~w_v~ lên ~c~ đơn vị với mọi ~v~ quản lý bởi ~u~. Sau mỗi thay đổi, cần tìm đỉnh ~u~ để xây dựng kho dữ trữ sao cho tổng chi phí vận chuyển lương thực là nhỏ nhất, nếu có nhiều ~u~ như vậy thì chọn ~u~ nhỏ nhất.

Input:

• Dòng đầu chứa hai số nguyên dương ~n~ và ~Q~;
• Dòng thứ hai chứa ~n~ số ~w_1,w_2,...,w_n~;
• Mỗi dòng trong số ~n - 1~ dòng tiếp theo chứa hai số ~u\ v~ mô tả một cạnh của cây;
• Mỗi dòng trong số ~Q~ dòng tiếp theo chứa ba số ~t\ u\ c~ mô tả một thay đổi

Output:

• Ghi ~Q~ dòng là chỉ số của đỉnh được chọn sau thay đổi thứ ~Q~.

Subtasks:

• Trong tất cả các test: ~n,Q ≤ 10^5; 1 ≤ w_i ≤ 10^6; |c| ≤ 10^6.~
• Có ~12 \%~ số test với ~n,Q ≤ 5000~;
• Có ~16 \%~ số test có cạnh nối từ ~x~ đến ~x - 1~ với mọi ~2 ≤ x ≤ n;~
• Có ~16 \%~ số test có cạnh nối từ ~x~ đến ~[x/2]~ với mọi ~2 ≤ x ≤ n;~
• Có ~20 \%~ số test không có thay đổi loại 2;
• Có ~36 \%~ số test với ràng buộc gốc.

Sample Input:

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

Sample Output:

2 
2 
1