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\).

Scoring

• 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. uộc gốc

Sample Input 1

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 1

2 
2 
1