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 MAXN 100010
struct edge {
    int to, color; long long dist;
};

vector<edge> v[MAXN];
map<int, pair<int, long long>> m[MAXN];
int parent[20][MAXN];
int height[MAXN];
int colorcnt[MAXN];
long long colordist[MAXN];

void dfs(int curr, int prev) {
    parent[0][curr] = prev;
    height[curr] = height[prev]+1;
    for (auto &e: v[curr]) {
        if (e.to == prev) continue;
        m[e.to][0] = {0, m[curr][0].second + e.dist};
        dfs(e.to, curr);
    }
}

void dfs2(int curr, int prev) {
    for (auto &it: m[curr]) {
        if (it.first == 0) continue;
        m[curr][it.first] = {colorcnt[it.first], colordist[it.first]};
    }
    for (auto &e: v[curr]) {
        if (e.to == prev) continue;
        colorcnt[e.color]++;
        colordist[e.color] += e.dist;
        dfs2(e.to, curr);
        colorcnt[e.color]--;
        colordist[e.color] -= e.dist;
    } 
}

void doubling() {
    for (int k = 0; k < 19; k++) {
        for (int i = 0; i < MAXN; i++) {
            parent[k+1][i] = parent[k][parent[k][i]];
        }
    }
}

int get(int u, int v) {
    if (height[u] > height[v]) swap(u, v);
    int t = height[v] - height[u];
    for (int i = 0; i < 20; i++) {
        if (t & (1 << i)) {
            v = parent[i][v];
        }
    }
    if (u == v) return u;
    for (int i = 19; i >= 0; i--) {
        if (parent[i][u] != parent[i][v]) {
            u = parent[i][u]; v = parent[i][v];
        }
    }
    return parent[0][u];
}

int main() {
    int n, q; cin >> n >> q;
    for (int i = 0; i < n-1; i++) {
        int a, b, c; long long d;
        cin >> a >> b >> c >> d;
        v[a].push_back({b, c, d});
        v[b].push_back({a, c, d});
    }
    dfs(1, 0); doubling();
    vector<int> xq(q), yq(q), uq(q), vq(q);
    for (int qi = 0; qi < q; qi++) {
        int x, y, u, v; cin >> x >> y >> u >> v;
        xq[qi] = x, yq[qi] = y, uq[qi] = u, vq[qi] = v;
        int w = get(u, v);
        m[u][x] = {0, 0}, m[v][x] = {0, 0}, m[w][x] = {0, 0}; 
    }
    dfs2(1, 0);
    for (int qi = 0; qi < q; qi++) {
        int x, y, u, v;
        x = xq[qi], y = yq[qi], u = uq[qi], v = vq[qi];
        int w = get(u, v);
        long long d = m[u][0].second + m[v][0].second - m[w][0].second * 2;
        long long cnt = m[u][x].first + m[v][x].first - m[w][x].first * 2;
        long long sub = m[u][x].second + m[v][x].second - m[w][x].second * 2;
        d += cnt * y - sub;
        cout << d << endl;
    }
    return 0;
}