#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using E = tuple<int,int,ll>;
const ll inf = numeric_limits<ll>::max()/3;
const ll mod = 1e9 + 7;

int n;
vector<vector<E>> tree;

int depth[100010];
int par[100010][20];

void init_par_depth(int node,int d, int p){
  depth[node] = d;
  par[node][0] = p;
  for(E edge : tree[node]){
    int next,c;
    ll w;
    tie(next,c,w) = edge;
    if(next != p){
      init_par_depth(next,d+1,node);
    }
  }
}

void fill_par(int root){
  init_par_depth(root,0,-1);
  for(int i = 1;i < 20;++i){
    for(int node = 0;node < n;++node){
      if(par[node][i-1] == -1){
        par[node][i] = -1;
      } else {
        par[node][i] = par[par[node][i-1]][i-1];
      }
    }
  }
}

int lca(int a,int b){
  if(depth[b] > depth[a]){
    swap(a,b);
  }
  for(int i = 0;i < 20;++i){
    if((depth[a] - depth[b]) & (1 << i)){
      a = par[a][i];
    }
  }
  assert(depth[a] == depth[b]);
  if(a == b){
    return a;
  }
  for(int i = 19;i >= 0;--i){
    if(par[a][i] != par[b][i]){
      a = par[a][i];
      b = par[b][i];
    }
  }
  return par[a][0];
}

ll ans[100010];
ll cnt[100010];
ll sum[100010];
using Q = tuple<int,ll,int,ll>;
vector<vector<Q>> query;

void calc(int node,int p,ll dist){
  for(Q q : query[node]){
    int id,x;
    ll mult,y;
    tie(id,mult,x,y) = q;
    ans[id] += mult * (dist - sum[x] + cnt[x] * y);
  }

  for(E edge : tree[node]){
    int next,c,w;
    tie(next,c,w) = edge;
    if(next != p){
      cnt[c]++;
      sum[c] += w;
      calc(next,node,dist+w);
      cnt[c]--;
      sum[c] -= w;
    }
  }
}


int main(void){
  int q;
  cin >> n >> q;
  tree = vector<vector<E>>(n);
  for(int i = 0;i < n-1;++i){
    int a,b,c;
    ll w;
    scanf("%d %d %d %lld", &a, &b, &c, &w);
    --a;--b;
    tree[a].push_back(make_tuple(b,c,w));
    tree[b].push_back(make_tuple(a,c,w));
  }
  fill_par(0);

  query = vector<vector<Q>>(n);
  for(int i = 0;i < q;++i){
    int x,u,v;
    ll y;
    scanf("%d %lld %d %d", &x, &y, &u, &v);
    --u;--v;
    int a = lca(u,v);
    query[a].push_back(make_tuple(i,-2LL,x,y));
    query[u].push_back(make_tuple(i,1LL,x,y));
    query[v].push_back(make_tuple(i,1LL,x,y));
  }

  fill(ans,ans+100010,0LL);
  fill(cnt,cnt+100010,0LL);
  fill(sum,sum+100010,0LL);
  calc(0,-1,0);

  for(int i = 0;i < q;++i){
    printf("%lld\n", ans[i]);
  }
  return 0;
}

### Prompt

Please create a solution in CPP to the following problem:

There is a tree with N vertices numbered 1 to N. The i-th edge in this tree connects Vertex a_i and Vertex b_i, and the color and length of that edge are c_i and d_i, respectively. Here the color of each edge is represented by an integer between 1 and N-1 (inclusive). The same integer corresponds to the same color, and different integers correspond to different colors.

Answer the following Q queries:

* Query j (1 \leq j \leq Q): assuming that the length of every edge whose color is x_j is changed to y_j, find the distance between Vertex u_j and Vertex v_j. (The changes of the lengths of edges do not affect the subsequent queries.)

Constraints

* 2 \leq N \leq 10^5
* 1 \leq Q \leq 10^5
* 1 \leq a_i, b_i \leq N
* 1 \leq c_i \leq N-1
* 1 \leq d_i \leq 10^4
* 1 \leq x_j \leq N-1
* 1 \leq y_j \leq 10^4
* 1 \leq u_j < v_j \leq N
* The given graph is a tree.
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N Q
a_1 b_1 c_1 d_1
:
a_{N-1} b_{N-1} c_{N-1} d_{N-1}
x_1 y_1 u_1 v_1
:
x_Q y_Q u_Q v_Q


Output

Print Q lines. The j-th line (1 \leq j \leq Q) should contain the answer to Query j.

Example

Input

5 3
1 2 1 10
1 3 2 20
2 4 4 30
5 2 1 40
1 100 1 4
1 100 1 5
3 1000 3 4


Output

130
200
60

### Response

```cpp
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using E = tuple<int,int,ll>;
const ll inf = numeric_limits<ll>::max()/3;
const ll mod = 1e9 + 7;

int n;
vector<vector<E>> tree;

int depth[100010];
int par[100010][20];

void init_par_depth(int node,int d, int p){
  depth[node] = d;
  par[node][0] = p;
  for(E edge : tree[node]){
    int next,c;
    ll w;
    tie(next,c,w) = edge;
    if(next != p){
      init_par_depth(next,d+1,node);
    }
  }
}

void fill_par(int root){
  init_par_depth(root,0,-1);
  for(int i = 1;i < 20;++i){
    for(int node = 0;node < n;++node){
      if(par[node][i-1] == -1){
        par[node][i] = -1;
      } else {
        par[node][i] = par[par[node][i-1]][i-1];
      }
    }
  }
}

int lca(int a,int b){
  if(depth[b] > depth[a]){
    swap(a,b);
  }
  for(int i = 0;i < 20;++i){
    if((depth[a] - depth[b]) & (1 << i)){
      a = par[a][i];
    }
  }
  assert(depth[a] == depth[b]);
  if(a == b){
    return a;
  }
  for(int i = 19;i >= 0;--i){
    if(par[a][i] != par[b][i]){
      a = par[a][i];
      b = par[b][i];
    }
  }
  return par[a][0];
}

ll ans[100010];
ll cnt[100010];
ll sum[100010];
using Q = tuple<int,ll,int,ll>;
vector<vector<Q>> query;

void calc(int node,int p,ll dist){
  for(Q q : query[node]){
    int id,x;
    ll mult,y;
    tie(id,mult,x,y) = q;
    ans[id] += mult * (dist - sum[x] + cnt[x] * y);
  }

  for(E edge : tree[node]){
    int next,c,w;
    tie(next,c,w) = edge;
    if(next != p){
      cnt[c]++;
      sum[c] += w;
      calc(next,node,dist+w);
      cnt[c]--;
      sum[c] -= w;
    }
  }
}


int main(void){
  int q;
  cin >> n >> q;
  tree = vector<vector<E>>(n);
  for(int i = 0;i < n-1;++i){
    int a,b,c;
    ll w;
    scanf("%d %d %d %lld", &a, &b, &c, &w);
    --a;--b;
    tree[a].push_back(make_tuple(b,c,w));
    tree[b].push_back(make_tuple(a,c,w));
  }
  fill_par(0);

  query = vector<vector<Q>>(n);
  for(int i = 0;i < q;++i){
    int x,u,v;
    ll y;
    scanf("%d %lld %d %d", &x, &y, &u, &v);
    --u;--v;
    int a = lca(u,v);
    query[a].push_back(make_tuple(i,-2LL,x,y));
    query[u].push_back(make_tuple(i,1LL,x,y));
    query[v].push_back(make_tuple(i,1LL,x,y));
  }

  fill(ans,ans+100010,0LL);
  fill(cnt,cnt+100010,0LL);
  fill(sum,sum+100010,0LL);
  calc(0,-1,0);

  for(int i = 0;i < q;++i){
    printf("%lld\n", ans[i]);
  }
  return 0;
}

```