CAPITAL

Vương quốc có $n$ thành phố (đánh số từ $1$ đến $n$) và $n-1$ con đường hai chiều, đảm bảo đi lại được giữa mọi cặp thành phố. Thành phố $x$ được gọi là quản lý thành phố $y$ nếu $x$ nằm trên đường đi đơn từ $y$ đến $1$ (kể cả hai đầu mút, nên mỗi thành phố quản lý chính nó và thành phố $1$ quản lý mọi thành phố). 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 thành phố để 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\times 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 $1uc$ hoặc $2uc$, 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 thành phố $v$ được quản lý bởi $u$. Giá trị $c$ có thể âm (khi đó sản lượng giảm đi $|c|$ đơn vị).

Yêu cầu: Sau mỗi thay đổi, cần tìm thành phố $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.

Dữ liệu vào

• 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ố nguyên $uv$ mô tả một con đường nối hai thành phố $u$ và $v$;
• Mỗi dòng trong số $Q$ dòng tiếp theo chứa ba số nguyên $tuc$ ($t\in \{1,2\}$, $1\le u\le n$) mô tả một thay đổi.

Dữ liệu ra

Gồm $Q$ dòng, dòng thứ $i$ là chỉ số của thành phố được chọn sau thay đổi thứ $i$.

Ràng buộc

• $1\le n,Q\le {10}^5$;
• $1\le w_i\le {10}^6$;
• $|c|\le {10}^6$;
• Dữ liệu đảm bảo sau mỗi thay đổi, sản lượng của mọi thành phố vẫn là số nguyên dương ($w_v\ge 1$ với mọi $v$).

Subtasks

• Có $12\%$ số test với $n,Q\le 5000$;
• Có $16\%$ số test có cạnh nối từ $x$ đến $x-1$ với mọi $2\le x\le n$;
• Có $16\%$ số test có cạnh nối từ $x$ đến $\lfloor x/2\rfloor$ với mọi $2\le x\le 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.

Ví dụ