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 <iostream>
#include <bits/stdc++.h>

using namespace std;
int n,q,len;
int dep[100005];
int dis[100005];
int anc[100005][30];
int fel[100005],ccnt[100005],csums[100005];
int eul[200005];
vector<pair<int,int>> ct[100005];
vector<int> csum[100005];

struct it{
    int f,s,t;
    it(int ff,int ss,int tt){
        f=ff;s=ss;t=tt;
    }
};

vector<it> rad[100005];
vector<pair<int,int>> cr[100005];

void dfs(int now,int from,int ds)
{

    eul[++len] = now;
    fel[now] = len;
    dis[now] = ds;

    dep[now] = dep[from]+1;
    anc[now][0] = from;

    for(int i=1;i<20;++i)
    {
        anc[now][i] = anc[anc[now][i-1]][i-1];
    }

    for(int i=0;i<rad[now].size();++i)
    {
        if(rad[now][i].f==from) continue;
        ct[rad[now][i].s].push_back(pair<int,int>(len+1,++ccnt[rad[now][i].s]));
        csum[rad[now][i].s].push_back(csums[rad[now][i].s]+=rad[now][i].t);
        dfs(rad[now][i].f,now,ds+rad[now][i].t);
        eul[++len] = now;
        ct[rad[now][i].s].push_back(pair<int,int>(len,--ccnt[rad[now][i].s]));
        csum[rad[now][i].s].push_back(csums[rad[now][i].s]-=rad[now][i].t);
    }
}

int lca(int u,int v)
{
    if(dep[u]<dep[v])swap(u,v);
    int tmp = dep[u] - dep[v];
    for(int j=0;tmp;++j,tmp>>=1)
        if(tmp&1) u = anc[u][j];

    for(int i=19;i>=0&&u!=v;--i)
    {
        if(anc[u][i]!=anc[v][i])
        {
            u = anc[u][i];
            v = anc[v][i];
        }
    }
    if(u!=v)
    return anc[u][0];
    return u;
}

bool cmp(const pair<int,int> a,const pair<int,int> b)
{
    return a.first < b.first;
}

int gcost(int u,int x,int y)
{
    int pos = upper_bound(ct[x].begin(),ct[x].end(),
                          pair<int,int>(fel[u],0),cmp) - ct[x].begin();
    --pos;
    return dis[u] - csum[x][pos] + ct[x][pos].second*y;
}

int main()
{
    scanf("%d%d",&n,&q);
    int a,b,c,d;
    for(int i=1;i<n;++i)
    {
        scanf("%d%d%d%d",&a,&b,&c,&d);
        rad[a].push_back(it(b,c,d));
        rad[b].push_back(it(a,c,d));
    }

    for(int i=0;i<=100002;++i)
    {
        ct[i].push_back(pair<int,int>(-1,0));
        csum[i].push_back(0);
    }

    dfs(1,0,0);

    int x,y,u,v;
    for(int i=0;i<q;++i)
    {
        scanf("%d%d%d%d",&x,&y,&u,&v);
        int l = lca(u,v);
        printf("%d\n",gcost(u,x,y)+gcost(v,x,y)-2*gcost(l,x,y));
    }
    return 0;
}