#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
#define fi first
#define se second
#define pb push_back
#define wzh(x) cerr<<#x<<'='<<x<<endl;
int n,q,ans[N];
vector<pair<int,int>>v[N];
struct uzi{
  int u,v,c,d,i;

  bool operator <(const uzi & t)const{
    return u<t.u;
  }
}p[N],Q[N];
vector<int>ed[N];
int de[N],dep[N];
int fa[N][20];
int L[N],R[N],cnt;
int t1[N],t2[N];
void dfs(int x,int y,int dis=0){
  de[x]=dis;
  dep[x]=dep[y]+1;
  fa[x][0]=y;
  L[x]=++cnt;
  for(int i=1;i<20;i++)fa[x][i]=fa[fa[x][i-1]][i-1];
  for(auto k:v[x]){
    if(k.fi==y)continue;
    dfs(k.fi,x,dis+k.se);
  }
  R[x]=++cnt;
}
int lca(int x,int y){
  if(dep[x]<dep[y])swap(x,y);
  for(int i=19;i>=0;i--)if(dep[fa[x][i]]>=dep[y])x=fa[x][i];
  if(x==y)return x;
  for(int i=19;i>=0;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
  return fa[x][0];
}
void add(int *t,int x,int y){
  for(;x<N;x+=x&-x)t[x]+=y;
}
int get(int *t,int x){
  int y=0;
  for(;x;x-=x&-x)y+=t[x];
  return y;
}
int get_dis(int x,int y){
  return de[x]+de[y]-2*de[lca(x,y)];
}
int get_pre(int x,int y){
  return get(t2,L[x])+get(t2,L[y])-2*get(t2,L[lca(x,y)]);
}
int get_new(int x,int y){
  return get(t1,L[x])+get(t1,L[y])-2*get(t1,L[lca(x,y)]);
}

int main() {
  ios::sync_with_stdio(false);
  cin>>n>>q;
  for(int i=1;i<n;i++){
    cin>>p[i].u>>p[i].v>>p[i].c>>p[i].d;
    v[p[i].u].emplace_back(p[i].v,p[i].d);
    v[p[i].v].emplace_back(p[i].u,p[i].d);
    ed[p[i].c].pb(i);
  }
  dfs(1,0);
  for(int i=1;i<=q;i++){
    cin>>Q[i].u>>Q[i].v>>Q[i].c>>Q[i].d;Q[i].i=i;
  }
  sort(Q+1,Q+1+q);
  for(int l=1,r;l<=q;l=r+1){
    r=l;
    while(r+1<=q&&Q[r+1].u==Q[r].u)r++;
    for(auto k:ed[Q[r].u]){
      int x=p[k].u,y=p[k].v;
      if(dep[x]<dep[y])swap(x,y);
      add(t1,L[x],1);
      add(t1,R[x]+1,-1);
      add(t2,L[x],p[k].d);
      add(t2,R[x]+1,-p[k].d);
    }
    for(int i=l;i<=r;i++){
      ans[Q[i].i]=get_dis(Q[i].c,Q[i].d)-get_pre(Q[i].c,Q[i].d)
                    +get_new(Q[i].c,Q[i].d)*Q[i].v;
    }
    for(auto k:ed[Q[r].u]){
      int x=p[k].u,y=p[k].v;
      if(dep[x]<dep[y])swap(x,y);
      add(t1,L[x],-1);
      add(t1,R[x]+1,1);
      add(t2,L[x],-p[k].d);
      add(t2,R[x]+1,p[k].d);
    }
  }
  for(int i=1;i<=q;i++)cout<<ans[i]<<'\n';
  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
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
#define fi first
#define se second
#define pb push_back
#define wzh(x) cerr<<#x<<'='<<x<<endl;
int n,q,ans[N];
vector<pair<int,int>>v[N];
struct uzi{
  int u,v,c,d,i;

  bool operator <(const uzi & t)const{
    return u<t.u;
  }
}p[N],Q[N];
vector<int>ed[N];
int de[N],dep[N];
int fa[N][20];
int L[N],R[N],cnt;
int t1[N],t2[N];
void dfs(int x,int y,int dis=0){
  de[x]=dis;
  dep[x]=dep[y]+1;
  fa[x][0]=y;
  L[x]=++cnt;
  for(int i=1;i<20;i++)fa[x][i]=fa[fa[x][i-1]][i-1];
  for(auto k:v[x]){
    if(k.fi==y)continue;
    dfs(k.fi,x,dis+k.se);
  }
  R[x]=++cnt;
}
int lca(int x,int y){
  if(dep[x]<dep[y])swap(x,y);
  for(int i=19;i>=0;i--)if(dep[fa[x][i]]>=dep[y])x=fa[x][i];
  if(x==y)return x;
  for(int i=19;i>=0;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
  return fa[x][0];
}
void add(int *t,int x,int y){
  for(;x<N;x+=x&-x)t[x]+=y;
}
int get(int *t,int x){
  int y=0;
  for(;x;x-=x&-x)y+=t[x];
  return y;
}
int get_dis(int x,int y){
  return de[x]+de[y]-2*de[lca(x,y)];
}
int get_pre(int x,int y){
  return get(t2,L[x])+get(t2,L[y])-2*get(t2,L[lca(x,y)]);
}
int get_new(int x,int y){
  return get(t1,L[x])+get(t1,L[y])-2*get(t1,L[lca(x,y)]);
}

int main() {
  ios::sync_with_stdio(false);
  cin>>n>>q;
  for(int i=1;i<n;i++){
    cin>>p[i].u>>p[i].v>>p[i].c>>p[i].d;
    v[p[i].u].emplace_back(p[i].v,p[i].d);
    v[p[i].v].emplace_back(p[i].u,p[i].d);
    ed[p[i].c].pb(i);
  }
  dfs(1,0);
  for(int i=1;i<=q;i++){
    cin>>Q[i].u>>Q[i].v>>Q[i].c>>Q[i].d;Q[i].i=i;
  }
  sort(Q+1,Q+1+q);
  for(int l=1,r;l<=q;l=r+1){
    r=l;
    while(r+1<=q&&Q[r+1].u==Q[r].u)r++;
    for(auto k:ed[Q[r].u]){
      int x=p[k].u,y=p[k].v;
      if(dep[x]<dep[y])swap(x,y);
      add(t1,L[x],1);
      add(t1,R[x]+1,-1);
      add(t2,L[x],p[k].d);
      add(t2,R[x]+1,-p[k].d);
    }
    for(int i=l;i<=r;i++){
      ans[Q[i].i]=get_dis(Q[i].c,Q[i].d)-get_pre(Q[i].c,Q[i].d)
                    +get_new(Q[i].c,Q[i].d)*Q[i].v;
    }
    for(auto k:ed[Q[r].u]){
      int x=p[k].u,y=p[k].v;
      if(dep[x]<dep[y])swap(x,y);
      add(t1,L[x],-1);
      add(t1,R[x]+1,1);
      add(t2,L[x],-p[k].d);
      add(t2,R[x]+1,p[k].d);
    }
  }
  for(int i=1;i<=q;i++)cout<<ans[i]<<'\n';
  return 0;
}
```