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<iomanip>
#include<vector>
#include<string>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<climits>
#include<fstream>

#define MOD (1000000007)

using namespace std;

typedef long long int Int;

constexpr Int TEN(int n) { return n == 0 ? 1 : 10 * TEN(n-1); }

const int max_n = 100000+19;

int N,q;
typedef struct M {
    int to;
    int color;
    int dist;
}Node;

vector<Node> G[max_n];
vector<Node> Q[max_n];
int par[max_n][20];
int ans[max_n];
int height[max_n];
int dist[max_n];
int num[max_n];
int sum[max_n];

void get(int p) {
    height[p] = height[par[p][0]]+1;
    for(auto u: G[p]) {
        if(u.to != par[p][0]) {
            par[u.to][0] = p;
            dist[u.to] = dist[p]+u.dist;
            get(u.to);
        }
    }

    return;
}

int lca(int x,int y) {
    if(height[x] > height[y])
        swap(x,y);
    int t = height[y] - height[x];
    for(int i = 0;i < 18;i++) {
        if(t&(1<<i))
            y = par[y][i];
    }
    if(x == y)
        return x;
    for(int i = 17;i >= 0;i--) {
        if(par[x][i] != par[y][i]) {
            x = par[x][i];
            y = par[y][i];
        }
    }

    return par[x][0];
}

void dfs(int p) {
    for(auto u: Q[p]) {
        if(u.to > 0) { //each node
            ans[u.to] += dist[p]+num[u.color]*u.dist-sum[u.color];
        } else { //ancestor
            ans[-u.to] -= 2*(dist[p]+num[u.color]*u.dist-sum[u.color]);
        }
    }

    for(auto u: G[p]) {
        if(u.to == par[p][0])
            continue;
        num[u.color]++;
        sum[u.color] += u.dist;
        dfs(u.to);
        num[u.color]--;
        sum[u.color] -= u.dist;
    }

    return;
}

int main(void) {
    cin>>N>>q;
    for(int i = 1;i < N;i++) {
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        G[a].push_back({b,c,d});
        G[b].push_back({a,c,d});
    }

    get(1);
    for(int i = 1;i <= 18;i++) {
        for(int v = 1;v <= N;v++) {
            par[v][i] = par[par[v][i-1]][i-1];
        }
    }

    for(int i = 1;i <= q;i++) {
        int x,y,u,v;
        cin>>x>>y>>u>>v;
        Q[u].push_back({i,x, y});
        Q[v].push_back({i, x, y});
        Q[lca(u,v)].push_back({-i, x, y});
    }

    dfs(1);
    for(int i = 1;i <= q;i++) {
        cout<<ans[i]<<endl;
    }

    return 0;
}