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

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read(){
	ll a=0,b=getchar(),c=1;
	while(!isdigit(b))c=b=='-'?-1:1,b=getchar();
	while(isdigit(b))a=a*10+b-'0',b=getchar();
	return a*c;
}
const int N=3e5+5;
struct node{
    int to,x,w;
};
struct no{
    int x,w,y,id;
};
vector<no> e[N];
vector<node> g[N];
int n,q,ans[N],c[N],h[N],d[N],ab[N],b[N],a[N],f[N][20];
void dfs(int x,int y,int z,int &k){
    b[x]=k,ab[k]=x;
    d[k++]=z;
    for(int i=0;i<g[x].size();i++){
        node &t=g[x][i];
        if(t.to==y)continue;
        a[t.to]=a[x]+t.w;
        dfs(t.to,x,z+1,k);
        ab[k]=x,d[k++]=z;
    }
}
void gg(int n){
    for(int i=1;i<=n;i++)
		f[i][0]=i;
    for(int j=1;(1<<j)<=n;j++)
        for(int i=1;i+(1<<j)-1<=n;i++)
            if(d[f[i][j-1]]<d[f[i+(1<<(j-1))][j-1]])
                f[i][j]=f[i][j-1];
            else f[i][j]=f[i+(1<<(j-1))][j-1];
}
int jj(int l,int r){
    int x=0;
    while((1<<(x+1))<=r-l+1)x++;
    if(d[f[l][x]]<d[f[r-(1<<x)+1][x]])
        return f[l][x];
    else return f[r-(1<<x)+1][x];
}
void dfs(int u,int y){
	for(int i=0;i<e[u].size();i++){
		no qu=e[u][i];
        ans[qu.id]+=(a[u]+c[qu.x]*qu.w-h[qu.x])*qu.y;
    }
	for(int i=0;i<g[u].size();i++){
		node p=g[u][i];
        int to=p.to;
        if(to==y)continue;
        c[p.x]++,h[p.x]+=p.w;
        dfs(to,u);
        c[p.x]--,h[p.x]-=p.w;
    }
}
int main(){
	n=read(),q=read();
    for(int i=1;i<n;i++){
        int u=read(),v=read(),c=read(),w=read();
        g[u].push_back(node{v,c,w});
        g[v].push_back(node{u,c,w});
    }
    int k=1;
    dfs(1,-1,0,k);
    gg(2*n-1);
    for(int i=1;i<=q;i++){
        int x=read(),y=read(),u=read(),v=read();
        int fa=ab[jj(min(b[u],b[v]),max(b[u],b[v]))];
        e[u].push_back(no{x,y,1,i});
        e[v].push_back(no{x,y,1,i});
        e[fa].push_back(no{x,y,-2,i});
    }
    dfs(1,-1);
    for(int i=1;i<=q;i++)
        printf("%d\n",ans[i]);
	return 0;
}