Đường kính

Cho một cây có \(n\) đỉnh và \(n-1\) cạnh, các cạnh đánh số từ \(0\) đến \(n-2\). Mỗi cạnh \(i\) có trọng số ban đầu \(c_i\). Cây được mô tả bởi \(n-1\) cạnh và đảm bảo là một cây liên thông.

Có \(q\) cập nhật, mỗi cập nhật thay đổi trọng số của một cạnh. Sau mỗi lần cập nhật, yêu cầu tính và in ra đường kính của cây.

Đường kính của cây được định nghĩa là khoảng cách lớn nhất giữa hai đỉnh bất kỳ trong cây, với khoảng cách được tính theo trọng số của các cạnh.

Mỗi dòng cập nhật bao gồm hai số nguyên \(d_j\) và \(e_j\), sau đó được chuyển đổi thành \(d'_j\) và \(e'_j\) theo công thức:

• \(d'_j = (d_j + \text{last}) \mod (n - 1)\);
• \(e'_j = (e_j + \text{last}) \mod w\).

Tại đây, last là kết quả của đường kính được tính sau cập nhật trước đó, ban đầu last = 0.

Input

• Dòng đầu tiên chứa ba số nguyên \(n\), \(q\), và \(w\) \((2 \leq n \leq 10^5, 1 \leq q \leq 10^5, 1 \leq w \leq 2 \times 10^{13})\) -- số đỉnh của cây, số lượng cập nhật và giới hạn trọng số của các cạnh.
• \(n-1\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(a_i\), \(b_i\), \(c_i\) \((1 \leq a_i, b_i \leq n, 0 \leq c_i < w)\) -- mô tả một cạnh nối hai đỉnh \(a_i\) và \(b_i\) với trọng số ban đầu \(c_i\).
• \(q\) dòng cuối cùng, mỗi dòng chứa hai số nguyên \(d_j\), \(e_j\) \((0 \leq d_j < n-1, 0 \leq e_j < w)\) -- các truy vấn cập nhật.

Output

• In ra \(q\) dòng, mỗi dòng chứa một số nguyên biểu diễn đường kính của cây sau mỗi cập nhật.

Example

4 3 2000
1 2 100
2 3 1000
2 4 1000
2 1030
1 1020
1 890

2030
2080
2050

10 10 10000
1 9 1241
5 6 1630
10 5 1630
2 6 853
10 1 511
5 3 760
8 3 1076
4 10 1483
7 10 40
8 2051
5 6294
5 4168
7 1861
0 5244
6 5156
3 3001
8 5267
5 3102
8 3623

6164
7812
8385
6737
6738
7205
6641
7062
6581
5155

Scoring

• Subtask 1 (13 điểm): \(n, q \leq 100\) và \(w \leq 10{,}000\).
• Subtask 2 (15 điểm): \(n, q \leq 5{,}000\) và \(w \leq 10{,}000\).
• Subtask 3 (18 điểm): \(w \leq 10{,}000\), và các cạnh của cây chính là tất cả các cạnh hợp lệ dạng \(\{i, 2i\}\) và \(\{i, 2i+1\}\) (tức cây là một cây nhị phân cân bằng nếu gốc tại đỉnh \(1\)).
• Subtask 4 (24 điểm): Đảm bảo rằng sau mỗi lần cập nhật, đường đi đơn dài nhất đi qua đỉnh \(1\).
• Subtask 5 (30 điểm): Không có ràng buộc thêm.