给定一棵包含 $n$ 个顶点的带权无向树以及 $q$ 次更新操作。每次更新会改变其中一条边的权值。任务是在每次更新后输出树的直径。

（两顶点之间的距离定义为连接它们的唯一简单路径上所有边的权值之和。直径即所有这些距离中的最大值。）

输入格式

第一行包含三个空格分隔的整数 $n, q$ 和 $w$ ($2 \le n \le 100,000, 1 \le q \le 100,000, 1 \le w \le 20,000,000,000,000$)，分别表示树的顶点数、更新次数以及边权上限。顶点编号为 $1$ 到 $n$。

接下来 $n-1$ 行描述初始树。第 $i$ 行包含三个空格分隔的整数 $a_i, b_i, c_i$ ($1 \le a_i, b_i \le n, 0 \le c_i < w$)，表示初始时顶点 $a_i$ 和 $b_i$ 之间存在一条权值为 $c_i$ 的边。保证这 $n-1$ 行描述了一棵树。

最后 $q$ 行描述查询。第 $j$ 行包含两个空格分隔的整数 $d_j, e_j$ ($0 \le d_j < n-1, 0 \le e_j < w$)。这两个整数按以下方案进行转换：

• $d'_j = (d_j + last) \pmod{n-1}$
• $e'_j = (e_j + last) \pmod{w}$

其中 $last$ 是上一次查询的结果（初始时 $last = 0$）。元组 $(d'_j, e'_j)$ 表示一次查询，即将输入中第 $d'_j + 1$ 条边的权值修改为 $e'_j$。

输出格式

输出 $q$ 行。对于每个 $i$，第 $i$ 行应包含第 $i$ 次更新后树的直径。

子任务

• 子任务 1（11 分）：$n, q \le 100$ 且 $w \le 10,000$
• 子任务 2（13 分）：$n, q \le 5,000$ 且 $w \le 10,000$
• 子任务 3（7 分）：$w \le 10,000$ 且树的所有边均为 $\{1, i\}$ 形式（即树是以顶点 1 为中心的星形图）
• 子任务 4（18 分）：$w \le 10,000$，且树的所有边均为 $\{i, 2i\}$ 和 $\{i, 2i+1\}$ 形式（即若以顶点 1 为根，则为平衡二叉树）
• 子任务 5（24 分）：保证每次更新后，最长简单路径均经过顶点 1
• 子任务 6（27 分）：无附加限制

样例

样例输入 1

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

样例输出 1

2030
2080
2050

样例输入 2

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

样例输出 2

6164
7812
8385
6737
6738
7205
6641
7062
6581
5155

说明

第一个样例在下图中展示。最左侧的图显示了图的初始状态。随后的每张图展示了更新后的情况。更新后的边权用绿色标出，直径用红色标出。

第一次查询将第 3 条边（即 $\{2, 4\}$）的权值修改为 $1030$。顶点间距离最大的点对是 $3$ 和 $4$，距离为 $2030$。

由于答案为 $2030$，第二次查询解码为： $d'_2 = (1 + 2030) \pmod 3 = 0$ $e'_2 = (1020 + 2030) \pmod{2000} = 1050$

因此边 $\{1, 2\}$ 的权值被修改为 $1050$。这使得点对 $\{1, 4\}$ 成为距离最大的点对，距离为 $2080$。

第三次查询解码为： $d'_3 = (1 + 2080) \pmod 3 = 2$ $e'_3 = (890 + 2080) \pmod{2000} = 970$

随着边 $\{2, 4\}$ 的权值减小到 $970$，距离最远的点对变为 $\{1, 3\}$，距离为 $2050$。