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 MAX 100005

typedef pair<int, pair<int, int>> pip;
typedef pair<pair<int, int>, pip> ppp;
typedef long long ll;

vector<pip> adj[MAX];
vector<ppp> queries;
vector<ll> dst(MAX, 0);
map<int, int> mct[MAX], mcdt[MAX];
vector<int> req[MAX], ct(MAX, 0), cdt(MAX, 0), intime(MAX), outime(MAX);
vector<vector<int>> dp(MAX, vector<int>(20, 0));
int tmm = 0;

void get(int v, int p){
    dp[v][0] = p;
    intime[v] = tmm++;
    for(auto u : adj[v])
        if( u.first != p )
            get(u.first, v);
    outime[v] = tmm++;
}

bool isAncestor(int u, int v){
    return intime[u] < intime[v] && outime[u] > outime[v];
}

int lca(int u, int v){
    if( isAncestor(u, v) )
        return u;
    if( isAncestor(v, u) )
        return v;
    for(int i = 19; i >= 0; i--)
        if( ! isAncestor(dp[u][i], v) )
            u = dp[u][i];
    return dp[u][0];
}

void dfs(int v, int p){
    for(auto u : adj[v]){
        if( u.first != p ){
            dst[u.first] = dst[v] + u.second.second;
            ct[u.second.first]++;
            cdt[u.second.first] += u.second.second;
            for(auto e : req[u.first]){
                mct[u.first][e] = ct[e];
                mcdt[u.first][e] = cdt[e];
            }
            dfs(u.first, v);
            ct[u.second.first]--;
            cdt[u.second.first] -= u.second.second;
        }
    }
}

int main(){

    int n, q;
    cin >> n >> q;
    int a, b, c, d;
    for(int i = 0; i < n-1; i++){
        cin >> a >> b >> c >> d;
        a--, b--;
        adj[a].push_back(make_pair(b, make_pair(c, d)));
        adj[b].push_back(make_pair(a, make_pair(c, d)));
    }

    get(0, 0);
    for(int i = 1; i < 20; i++)
        for(int j = 0; j < n; j++)
            dp[j][i] = dp[dp[j][i-1]][i-1];

    int x, y, u, v, lc;
    for(int i = 0; i < q; i++){
        cin >> x >> y >> u >> v;
        u--, v--;
        lc = lca(u, v);
        req[u].push_back(x);
        req[v].push_back(x);
        req[lc].push_back(x);
        queries.push_back(make_pair(make_pair(x, y), make_pair(lc, make_pair(u, v))));
    }

    dfs(0, 0);

    for(auto q : queries){
        u = q.second.second.first, v = q.second.second.second, lc = q.second.first;
        x = q.first.first, y = q.first.second;
        ll dd = dst[u] + dst[v] - 2*dst[lc];
        ll cld = mcdt[u][x] + mcdt[v][x] - 2*mcdt[lc][x];
        ll ccn = mct[u][x] + mct[v][x] - 2*mct[lc][x];
        cout << ( dd - cld + y*ccn) << endl;
    }
    return 0;
}