Description

There is a tree with $n$ nodes, and the edges are weighted.

There will be $q$ modifications. Each modification changes the weight of one edge in the tree. After each modification, you need to output the sum of edge weights on the diameter of the tree.

This problem is strictly online.

Input Format

The first line contains three integers $n, q, w$, representing the number of nodes, the number of queries, and the upper bound of edge weights.

The next $n - 1$ lines each contain three integers $a_i, b_i, c_i$, meaning there is an edge between $a_i$ and $b_i$ with weight $c_i$.

The next $q$ lines each contain two encrypted integers $d_j, e_j$.

The decryption method is:

• $d_j'=(d_j+\text{last})\bmod(n-1)$
• $e_j'=(e_j+\text{last})\bmod w$

Here, $\text{last}$ is the answer to the previous query, with initial value $0$.

This means: change the weight of the $(d_j' + 1)$-th edge to $e_j'$.

Output Format

Output $q$ lines. Each line contains one integer. The integer on the $i$-th line is the total weight on the diameter after the $i$-th modification.

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

Hint

Explanation of Sample 1

The decrypted modifications are:

2 1030
0 1050
2 970

The following figure shows how the edge weights in the tree change. The red edge represents the diameter of the tree:

Constraints

For $100\%$ of the testdata, it is guaranteed that $2 \le n \le 10^5$, $1 \le q \le 10^5$, $1 \le w \le 2\times 10^{13}$, $1 \le a_i, b_i \le n$, $0 \le c_i, e_j < w$, and $0 \le d_j < n - 1$.

The detailed subtask constraints and scores are shown in the table below:

Notes

This problem is translated from Central-European Olympiad in Informatics 2019 Day 1 T2 Dynamic Diameter。

Translated by ChatGPT 5