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;
using ll=long long;
#define fr(i,n) for(int i=0;i<(n);++i)
#define Fr(i,n) for(int i=1;i<=(n);++i)
#define ifr(i,n) for(int i=(n)-1;i>=0;--i)
#define iFr(i,n) for(int i=(n);i>0;--i)

struct LCA{
    size_t n,r,m,md;
    vector<vector<int>> e;
    vector<int> pa,d;
    vector<vector<int>> lc;
    explicit LCA(int n_){
        n=n_;
        e.resize(n);
    }
    void add(int a,int b){
        e[a].emplace_back(b);
        e[b].emplace_back(a);
    }
    void r_dfs(int i,int p=-1,int D=0){
        pa[i]=p;d[i]=D;md=max(md,(size_t)D);++D;
        for(auto j:e[i]) if(j!=p) r_dfs(j,i,D);
    }
    void r_i(int r_){
        pa.resize(n);d.resize(n);r=r_;md=0;
        r_dfs(r);
    }
    void b_lca(int r_){
        r_i(r_);
        m=32-__builtin_clz(md);
        lc.clear();
        lc.resize(m,vector<int>(n,-1));
        fr(i,n) lc[0][i]=pa[i];
        fr(i,m-1) fr(j,n) if(lc[i][j]!=-1) lc[i+1][j]=lc[i][lc[i][j]];
    }
    int lca(int a,int b){
        if(a==b) return a;
        if(d[a]>d[b]) swap(a,b);
        for(int i=m-1;i>=0&&d[a]!=d[b];--i) if(lc[i][b]!=-1&&d[a]<=d[lc[i][b]]) b=lc[i][b];
        if(a==b) return a;
        ifr(i,m) if(lc[i][a]!=lc[i][b]) a=lc[i][a],b=lc[i][b];
        if(a!=b) a=pa[a];
        return a;
    }
};

struct edge{
    int to,c,d;
    edge(int to,int c,int d):to(to),c(c),d(d){}
};

struct que{
    int i,x,y;
    que(int i,int x,int y):i(i),x(x),y(y){}
};

vector<vector<edge>> e;
vector<vector<que>> vq;
int D{};
vector<int> num,sum;
vector<int> ans;

void rec(int i=0,int p=-1){
    for(auto q:vq[i]){
        if(q.i<0) ans[-q.i-1]-=2*(D-sum[q.x]+q.y*num[q.x]);
        else ans[q.i]+=D-sum[q.x]+q.y*num[q.x];
    }
    for(auto a:e[i]){
        if(a.to==p) continue;
        D+=a.d;
        ++num[a.c];
        sum[a.c]+=a.d;
        rec(a.to,i);
        D-=a.d;
        --num[a.c];
        sum[a.c]-=a.d;
    }
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    istream& in(cin);
    ostream& out(cout);
    int n,q;
    in>>n>>q;
    LCA t(n);
    int a,b,c,d;
    e.resize(n);
    fr(i,n-1){
        in>>a>>b>>c>>d;
        t.add(--a,--b);
        e[a].emplace_back(b,c,d);
        e[b].emplace_back(a,c,d);
    }
    t.b_lca(0);
    int x,y,u,v;
    vq.resize(n);
    fr(i,q){
        in>>x>>y>>u>>v;
        vq[--u].emplace_back(i,x,y);
        vq[--v].emplace_back(i,x,y);
        vq[t.lca(u,v)].emplace_back(-i-1,x,y);
    }
    num.resize(n);
    sum.resize(n);
    ans.resize(q);
    rec();
    fr(i,q) cout<<ans[i]<<endl;
}