Đất nước XYZ có ~N~ thành phố được đánh số từ ~1~ đến ~N~, thủ đô được đánh số ~1~. Mạng lưới điện ở XYZ bao gồm ~N-1~ đường dây truyền tải được đánh số từ ~1~ đến ~N-1~. Đường dây thứ ~i~ kết nối hai thành phố ~u_i~ với thành phố ~v_i~ và có độ dài là ~w_i~. Mạng lưới đảm bảo rằng điện có thể được truyển tải giữa bất kì cặp thành phố nào một cách trực tiếp hoặc gián tiếp qua các thành phố khác. Người ta ước tính rằng thành phố ~u~ cần được cung cấp một lượng điện là ~a_u~ đơn vị. Lượng điện thất thoát khi truyền tải được tính theo công thức ~A=X\cdot d~, với X và ~d~ là lượng điện và khoảng cách đã truyền tải.

Chính quyền đang có kế hoạch xây dựng một số nhà máy điện ở một trong ~N~ thành phố. Để tiết kiệm chi phí, chính quyền cần tìm thành phố ~u~ sao cho tối thiểu hóa tổng lượng điện thất thoát ~S=\displaystyle\sum_{v=1}^N a(v)\cdot d(u,v)~ với ~d(u,v)~ là khoảng cách từ thành phố ~u~ đến thành phố ~v~.

Để tìm vị trí xây nhà máy điện tối ưu, chính quyền sẽ quan sát nhu cầu điện của ~N~ thành phố. Có một dãy ~Q~ các thay đổi trong nhu cầu, mỗi thay đổi nằm trong bốn loại sau:

• 1 u k: Nhu cầu của thành phố ~u~ tăng lên ~k~ đơn vị.

• 2 u k: Nhu cầu của thành phố ~u~ giảm xuống ~k~ đơn vị.

• 3 u k: Với mỗi thành phố ~v~ được quản lý bởi ~u~, nhu cầu của ~v~ tăng lên ~k~ đơn vị.

• 4 u k: Với mỗi thành phố ~v~ được quản lý bởi ~u~, nhu cầu của ~v~ giảm đi ~k~ đơn vị.

Ở đây ta nói ~v~ được quản lý bởi ~u~ nếu đường đi từ ~v~ đến thủ đô phải đi qua ~u~.

Yêu cầu: Sau mỗi thay đổi, hãy tìm thành phố tối ưu để xây nhà máy điện.

Input

• Dòng đầu tiên gồm hai số nguyên ~N~ và ~Q~ (~1\le N,Q\le 2\cdot 10^5~).

• ~N-1~ dòng tiếp theo mô tả ~N-1~ đường dây truyền tải với ba số nguyên ~u_i,v_i,w_i~ (~w_i\le 10^7~).

• Dòng tiếp theo gồm ~n~ số nguyên ~a_1,a_2,\ldots,a_n~ (~0\le a_i\le 10^7~).

• ~Q~ dòng cuối cùng mô tả thông tin về ~Q~ sự thay đổi thuộc 1 trong 4 loại đã nêu với ba số nguyên ~t_j,u_j,k_j~ (~1\le t_j\le 4, k_j\le 10^7~). Dữ liệu đảm bảo nhu cầu của mỗi thành phố luôn không âm sau mỗi thay đổi.

Output

• Với mỗi sự thay đổi in ra thành phố tối ưu trên một dòng. Nếu có nhiều đáp án, bạn có thể đưa ra bất kì trong số chúng.

Subtask

• ~6\%~ số test thỏa mãn ~N\le 100, Q\le 5000~.

• ~10\%~ số test thỏa mãn ~N\le 5000, Q\le 5000~.

• ~12\%~ số test thỏa mãn mạng lưới điện có dạng đường thẳng.

• ~16\%~ số test thỏa mãn chỉ có các sự thay đổi loại ~1~.

• ~20\%~ số test thỏa mãn chỉ có các sự thay đổi loại ~1~ và ~2~.

• ~36\%~ số test không có điều kiện gì thêm.

Sample Input 1

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

Sample Output 1

1
2
1