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;
#define ll long long
int timer=0;
int l;
const int N=3e5+5;
int up[N][30];
vector<int> adj[N],Want[N];
int in[N],out[N],a[N],b[N],u[N],v[N],c[N],x[N];
ll curcost[N],curcnt[N],y[N],dis[N],d[N];
ll ans[N];
map< pair<int,int> , ll >cnt,cost;
void dfs(int u,int par,ll D)
{
    in[u]=++timer;
    up[u][0]=par;
    dis[u]=D;
    for(int i=1;i<=l;i++)
        up[u][i]=up[up[u][i-1]][i-1];
    for(auto idx:adj[u]){
        int v;
        if(a[idx]==u)
            v=b[idx];
        else v=a[idx];
        if(v!=par)
            dfs(v,u,D+d[idx]);
    }
    out[u]=timer;
}
bool is_ancestor(int u,int v)
{
    return in[u]<=in[v]&&out[u]>=out[v];
}
int LCA(int u,int v)
{
    if(is_ancestor(u,v))
        return u;
    if(is_ancestor(v,u))
        return v;
    for(int i=l;i>=0;i--)
    {
        if(!is_ancestor(up[u][i],v))
            u=up[u][i];
    }
    return up[u][0];
}
void solve(int u,int par)
{
    for(auto v:Want[u])
    {
        cnt[{u,v}]=curcnt[v];
        cost[{u,v}]=curcost[v];
    }
    for(auto idx:adj[u])
    {
        int v;
        if(a[idx]==u)
            v=b[idx];
        else v=a[idx];
        if(v!=par)
        {
            curcnt[c[idx]]++;
            curcost[c[idx]]+=d[idx];
            solve(v,u);
            curcnt[c[idx]]--;
            curcost[c[idx]]-=d[idx];
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n,q;
    l=ceil(log2(n));
    cin>>n>>q;
    for(int i=1;i<n;i++)
    {
        cin>>a[i]>>b[i]>>c[i]>>d[i];
        adj[a[i]].push_back(i);
        adj[b[i]].push_back(i);
    }
    dfs(1,1,0);
    for(int i=0;i<q;i++)
    {
        cin>>x[i]>>y[i]>>u[i]>>v[i];
        ans[i]=dis[u[i]]+dis[v[i]]-2*dis[LCA(u[i],v[i])];
        Want[u[i]].push_back(x[i]);
        Want[v[i]].push_back(x[i]);
        Want[LCA(u[i],v[i])].push_back(x[i]);
    }
    solve(1,1);
    for(int i=0;i<q;i++)
    {
        ans[i]-=(cost[{u[i],x[i]}]+cost[{v[i],x[i]}]-2*cost[{LCA(u[i],v[i]),x[i]}]);
        ans[i]+=(cnt[{u[i],x[i]}]+cnt[{v[i],x[i]}]-2*cnt[{LCA(u[i],v[i]),x[i]}])*y[i];
        cout<<ans[i]<<'\n';
    }
    return 0;
}