동적 지름

가중치가 있는 무향 트리가 n개의 정점으로 주어지고, q개의 갱신이 주어진다. 각 갱신은 간선 하나의 가중치를 바꾼다. 각 갱신이 끝난 뒤 트리의 지름을 출력하라.

(두 정점 사이의 거리는 두 정점을 잇는 유일한 단순 경로 위 가중치의 합이다. 지름은 그러한 거리 중 가장 큰 값이다.)

첫째 줄에 공백으로 구분된 세 정수 n, q, w가 주어진다 (2 ≤ n ≤ 100, 000, 1 ≤ q ≤ 100, 000, 1 ≤ w ≤ 20, 000, 000, 000, 000). n은 트리의 정점 수, q는 갱신의 수, w는 간선 가중치의 상한이다. 정점은 1부터 n까지 번호가 붙는다.

다음 n − 1개 줄에 초기 트리가 주어진다. 이 중 i번째 줄에는 공백으로 구분된 세 정수 ai, bi, ci가 주어진다 (1 ≤ ai, bi ≤ n, 0 ≤ ci < w). 처음에 정점 ai와 bi 사이에 가중치 ci인 간선이 있다는 뜻이다. 이 n − 1개 줄이 트리를 이룬다.

마지막으로 q개 줄에 질의가 주어진다. 이 중 j번째 줄에는 공백으로 구분된 두 정수 dj, ej가 주어진다 (0 ≤ dj < n − 1, 0 ≤ ej < w). 이 두 정수는 다음 방식으로 변환된다.

• d'j = (dj + last) mod (n − 1)
• e'j = (ej + last) mod w

여기서 last는 직전 질의의 결과이다(처음에는 last = 0). 순서쌍 (d'j , e'j)은 입력에서 d'j + 1번째 간선의 가중치를 e'j로 바꾸는 질의를 나타낸다.

q개 줄을 출력한다. 각 i에 대해 i번째 줄에 i번째 갱신이 끝난 뒤 트리의 지름을 출력한다.

첫 번째 예제는 아래 그림에 나와 있다. 가장 왼쪽 그림은 그래프의 초기 상태를 나타낸다. 그 뒤의 그림은 각각 갱신이 끝난 뒤의 상황을 나타낸다. 갱신된 간선의 가중치는 초록색으로, 지름은 빨간색으로 칠해져 있다.

첫 번째 질의는 3번째 간선, 즉 {2, 4}의 가중치를 1030으로 바꾼다. 임의의 두 정점 사이의 거리 중 가장 큰 값은 3과 4 사이의 거리인 2030이다.

답이 2030이므로 두 번째 질의는

d'2 = (1 + 2030) mod 3 = 0

e'2 = (1020 + 2030) mod 2000 = 1050

가 되어, 간선 {1, 2}의 가중치가 1050으로 바뀐다. 그러면 {1, 4}가 거리가 2080으로 가장 먼 쌍이 된다.

세 번째 질의는

d'3 = (1 + 2080) mod 3 = 2

e'3 = (890 + 2080) mod 2000 = 970

으로 복호화된다. 간선 {2, 4}의 가중치가 970으로 줄어들자 가장 먼 쌍이 갑자기 {1, 3}이 되고, 거리는 2050이다.