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à \(\sum_{v=1}^n w_v \cdot 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à:

• Loại \(1\): Tăng \(w_u\) lên \(c\) đơn vị.
• Loại \(2\): 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ố nguyên \(w_1, w_2, \dots, 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 mỗi thay đổi.

Constraints

• \(n, Q \le 10^5\)
• \(1 \le w_i \le 10^6\)
• \(|c| \le 10^6\)

Scoring

• Subtask \(1\) (\(12\%\) số điểm): \(n, Q \le 5000\).
• Subtask \(2\) (\(16\%\) số điểm): Có cạnh nối từ \(x\) đến \(x - 1\) với mọi \(2 \le x \le n\).
• Subtask \(3\) (\(16\%\) số điểm): Có cạnh nối từ \(x\) đến \(\lfloor x/2 \rfloor\) với mọi \(2 \le x \le n\).
• Subtask \(4\) (\(20\%\) số điểm): Không có thay đổi loại \(2\).
• Subtask \(5\) (\(36\%\) số điểm): Không có ràng buộc gì thêm.

Example

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

2 
2 
1