You are given a weighted undirected tree on n vertices and a list of q updates. Each update changes the weight of one edge. The task is to output the diameter of the tree after each update.

(The distance between two vertices is the sum of the weights on the unique simple path that connects them. The diameter is the largest of all those distances.)

Input

The first line contains three space-separated integers n, q and w (2 ≤ n ≤ 100,000, 1 ≤ q ≤ 100,000, 1 ≤ w ≤ 20,000,000,000,000) – the number of vertices in the tree, the number of updates and the limit on the weights of edges. The vertices are numbered 1 through n.

Next, n-1 lines describing the initial tree follow. The i-th of these lines contains three space-separated integers a_i, b_i, c_i (1 ≤ a_i, b_i ≤ n, 0 ≤ c_i < w) meaning that initially, there is an edge between vertices a_i and b_i with weight c_i. It is guaranteed that these n-1 lines describe a tree.

Finally, q lines describing queries follow. The j-th of these lines contains two space-separated integers d_j, e_j (0 ≤ d_j < n - 1, 0 ≤ e_j < w). These two integers are then transformed according to the following scheme: 

  * d'_j = (d_j + last) mod (n - 1) 
  * e'_j = (e_j + last) mod w 

where last is the result of the last query (initially last=0). Tuple (d'_j, e'_j) represents a query which takes the d'_j+1-th edge from the input and sets its weight to e'_j.

Output

Output q lines. For each i, line i should contain the diameter of the tree after the i-th update.

Scoring

Subtask 1 (11 points): n,q ≤ 100 and w ≤ 10,000

Subtask 2 (13 points): n,q ≤ 5,000 and w ≤ 10,000

Subtask 3 (7 points): w ≤ 10,000 and the edges of the tree are exactly all valid edges of the form \{1, i\} (Hence, the tree is a star centered at vertex 1.)

Subtask 4 (18 points): w ≤ 10,000, and the edges of the tree are exactly all valid edges of the forms \\{i, 2i\} and \\{i, 2i+1\} (Hence, if we were to root the tree at vertex 1, it would be a balanced binary tree.)

Subtask 5 (24 points): it is guaranteed that after each update a longest simple path goes through vertex 1

Subtask 6 (27 points): no additional constraints

Examples

Input


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


Output


2030
2080
2050


Input


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


Output


6164
7812
8385
6737
6738
7205
6641
7062
6581
5155

Note

The first sample is depicted in the figure below. The left-most picture shows the initial state of the graph. Each following picture depicts the situation after an update. The weight of the updated edge is painted green, and the diameter is red.

<image>

The first query changes the weight of the 3rd edge, i.e. \{2, 4\}, to 1030. The largest distance between any pair of vertices is 2030 – the distance between 3 and 4.

As the answer is 2030, the second query is $$$d'_2 = (1 + 2030) mod 3 = 0 e'_2 = (1020 + 2030) mod 2000 = 1050 Hence the weight of the edge \\{1, 2\\} is changed to 1050. This causes the pair \\{1, 4\\} to be the pair with the greatest distance, namely 2080$$$.

The third query is decoded as $$$d'_3 = (1 + 2080) mod 3 = 2 e'_3 = (890 + 2080) mod 2000 = 970 As the weight of the edge \\{2, 4\\} decreases to 970, the most distant pair is suddenly \\{1, 3\\} with 2050$$$.
#include <bits/stdc++.h>
using namespace std;
inline void read(int &first) {
  register int c = getchar();
  first = 0;
  int neg = 0;
  for (; ((c < 48 || c > 57) && c != '-'); c = getchar())
    ;
  if (c == '-') {
    neg = 1;
    c = getchar();
  }
  for (; c > 47 && c < 58; c = getchar()) {
    first = (first << 1) + (first << 3) + c - 48;
  }
  if (neg) first = -first;
}
inline void read(long long &first) {
  register int c = getchar();
  first = 0;
  int neg = 0;
  for (; ((c < 48 || c > 57) && c != '-'); c = getchar())
    ;
  if (c == '-') {
    neg = 1;
    c = getchar();
  }
  for (; c > 47 && c < 58; c = getchar()) {
    first = (first << 1) + (first << 3) + c - 48;
  }
  if (neg) first = -first;
}
inline void writeln(long long first) {
  char buffor[21];
  register int i = 0;
  int neg = 0;
  if (first < 0) {
    neg = 1;
    first = -first;
  }
  do {
    buffor[i++] = (first % 10) + '0';
    first /= 10;
  } while (first);
  i--;
  if (neg) putchar('-');
  while (i >= 0) putchar(buffor[i--]);
  putchar('\n');
}
inline void write(long long first) {
  char buffor[21];
  register int i = 0;
  int neg = 0;
  if (first < 0) {
    neg = 1;
    first = -first;
  }
  do {
    buffor[i++] = (first % 10) + '0';
    first /= 10;
  } while (first);
  i--;
  if (neg) putchar('-');
  while (i >= 0) putchar(buffor[i--]);
  putchar(' ');
}
const int N = 2e5 + 7;
const long long oo = (long long)1e18 + 7;
int n, q, Time;
int st[N], ft[N], h[N];
long long W;
long long depthAt[N];
vector<pair<int, long long> > adj[N];
struct node {
  long long mn, mx;
  long long pre, suf;
  long long tot;
};
const node nullNode = {0, 0, 0, 0, 0};
struct segTree {
  node tree[4 * N];
  long long lazy[4 * N];
  node merge(node a, node b) {
    node res;
    res.mn = min(a.mn, b.mn);
    res.mx = max(a.mx, b.mx);
    res.pre = max(max(a.pre, b.pre), a.mx - 2 * b.mn);
    res.suf = max(max(a.suf, b.suf), b.mx - 2 * a.mn);
    res.tot = max(max(a.tot, b.tot), max(a.pre + b.mx, a.mx + b.suf));
    return res;
  }
  void Build(int first, int low, int high) {
    if (low == high) {
      long long val = depthAt[low];
      tree[first] = {val, val, -val, -val, 0};
    } else {
      int mid = low + high >> 1;
      Build(2 * first, low, mid);
      Build(2 * first + 1, mid + 1, high);
      tree[first] = merge(tree[2 * first], tree[2 * first + 1]);
    }
  }
  void Lazy(int first, bool isLeaf) {
    tree[first].mn += lazy[first];
    tree[first].mx += lazy[first];
    tree[first].pre -= lazy[first];
    tree[first].suf -= lazy[first];
    if (!isLeaf) {
      lazy[2 * first] += lazy[first];
      lazy[2 * first + 1] += lazy[first];
    }
    lazy[first] = 0;
  }
  void Update(int first, int l, int r, int i, int j, long long val) {
    Lazy(first, (l == r));
    if (l > j || r < i) return;
    if (l >= i && r <= j) {
      tree[first].mn += val;
      tree[first].mx += val;
      tree[first].pre -= val;
      tree[first].suf -= val;
      if (l != r) {
        lazy[2 * first] += val;
        lazy[2 * first + 1] += val;
      }
      return;
    }
    int mid = l + r >> 1;
    Update(2 * first, l, mid, i, j, val);
    Update(2 * first + 1, mid + 1, r, i, j, val);
    tree[first] = merge(tree[2 * first], tree[2 * first + 1]);
  }
} IT;
struct edge {
  int u, v;
  long long w;
  edge() {}
  edge(int u, int v, long long w) : u(u), v(v), w(w) {}
} e[N];
void dfs(int u, long long curDepth) {
  depthAt[++Time] = curDepth;
  st[u] = Time;
  for (auto nxt : adj[u]) {
    int v = nxt.first;
    long long w = nxt.second;
    if (!st[v]) {
      h[v] = h[u] + 1;
      dfs(v, curDepth + w);
      depthAt[++Time] = curDepth;
    }
    ft[u] = Time;
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  if (fopen("test.inp", "r"))
    freopen("test.inp", "r", stdin), freopen("test.out", "w", stdout);
  read(n);
  read(q);
  read(W);
  for (int i = 1; i < n; i++) {
    int u, v;
    long long w;
    read(u);
    read(v);
    read(w);
    adj[u].push_back(pair<int, long long>(v, w));
    adj[v].push_back(pair<int, long long>(u, w));
    e[i] = {u, v, w};
  }
  h[1] = 1;
  dfs(1, 0);
  for (int i = 1; i < n; i++)
    if (h[e[i].u] > h[e[i].v]) swap(e[i].u, e[i].v);
  long long last = 0;
  IT.Build(1, 1, Time);
  for (int i = 1; i <= q; i++) {
    int id;
    long long w;
    read(id);
    read(w);
    id = (id + last) % (n - 1) + 1;
    w = (w + last) % W;
    int u = e[id].v;
    long long delta = w - e[id].w;
    IT.Update(1, 1, Time, st[u], ft[u], delta);
    IT.Lazy(1, 0);
    last = IT.tree[1].tot;
    e[id].w = w;
    writeln(last);
  }
}
