#include <bits/stdc++.h>
#define pb          emplace_back
#define ll          long long
#define fi          first
#define se          second
#define mp          make_pair
#define mt          make_tuple
#define int         int64_t

using namespace std;

typedef pair<int, int> pii;
typedef tuple<int, int, int, int> TEdge;
const int N = int(1e5) + 2;
const int logN = 17;

int p[N][logN + 1], d[N], h[N];
int u, v, x, y, n, Q;
int num[N], sum[N], ans[N];
vector<int> a[N];
vector<pii> q[N];
TEdge e[N];
pii qq[N];

void DFS(int u) {
    for(int i = 1; i <= logN; ++i) p[u][i] = p[p[u][i - 1]][i - 1];
    for(int id: a[u]) {
        int x = get<0>(e[id]), y = get<1>(e[id]);
        x = x ^ y ^ u;
        if(x == p[u][0]) continue;
        h[x] = h[u] + 1, p[x][0] = u;
        d[x] = d[u] + get<3>(e[id]);
        DFS(x);
    }
}

int LCA(int u, int v) {
    if(h[u] < h[v]) swap(u, v);
    for(int i = logN; i >= 0; --i)
        if(h[u] - (1 << i) >= h[v]) u = p[u][i];
    if(u == v) return u;
    for(int i = logN; i >= 0; --i)
        if(p[u][i] != p[v][i]) u = p[u][i], v = p[v][i];
    return p[u][0];
}

void GetAns(int u) {
    for(pii query: q[u]) {
        int id = query.fi, add = query.se;
        int cost = d[u] + num[qq[id].fi] * qq[id].se - sum[qq[id].fi];
        ans[id] += cost * add;
    }
    for(int id: a[u]) {
        int x = get<0>(e[id]), y = get<1>(e[id]);
        x = x ^ y ^ u;
        if(x == p[u][0]) continue;
        ++num[get<2>(e[id])];
        sum[get<2>(e[id])] += get<3>(e[id]);
        GetAns(x);
        --num[get<2>(e[id])];
        sum[get<2>(e[id])] -= get<3>(e[id]);
    }
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    #define Task        "test"
    if(fopen(Task".inp", "r")) {
        freopen(Task".inp", "r", stdin);
        freopen(Task".out", "w", stdout);
    }
    cin >> n >> Q;
    for(int i = 1; i < n; ++i) {
        cin >> u >> v >> x >> y;
        e[i] = mt(u, v, x, y);
        a[u].pb(i); a[v].pb(i);
    }
    p[1][0] = 1; DFS(1);
    for(int i = 1; i <= Q; ++i) {
        cin >> x >> y >> u >> v;
        qq[i] = mp(x, y);
        q[LCA(u, v)].pb(mp(i, -2));
        q[u].pb(i, 1); q[v].pb(i, 1);
    }
    GetAns(1);
    for(int i = 1; i <= Q; ++i) cout << ans[i] << '\n';
}

### Prompt

Develop a solution in CPP to the problem described below:

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

### Response

```cpp
#include <bits/stdc++.h>
#define pb          emplace_back
#define ll          long long
#define fi          first
#define se          second
#define mp          make_pair
#define mt          make_tuple
#define int         int64_t

using namespace std;

typedef pair<int, int> pii;
typedef tuple<int, int, int, int> TEdge;
const int N = int(1e5) + 2;
const int logN = 17;

int p[N][logN + 1], d[N], h[N];
int u, v, x, y, n, Q;
int num[N], sum[N], ans[N];
vector<int> a[N];
vector<pii> q[N];
TEdge e[N];
pii qq[N];

void DFS(int u) {
    for(int i = 1; i <= logN; ++i) p[u][i] = p[p[u][i - 1]][i - 1];
    for(int id: a[u]) {
        int x = get<0>(e[id]), y = get<1>(e[id]);
        x = x ^ y ^ u;
        if(x == p[u][0]) continue;
        h[x] = h[u] + 1, p[x][0] = u;
        d[x] = d[u] + get<3>(e[id]);
        DFS(x);
    }
}

int LCA(int u, int v) {
    if(h[u] < h[v]) swap(u, v);
    for(int i = logN; i >= 0; --i)
        if(h[u] - (1 << i) >= h[v]) u = p[u][i];
    if(u == v) return u;
    for(int i = logN; i >= 0; --i)
        if(p[u][i] != p[v][i]) u = p[u][i], v = p[v][i];
    return p[u][0];
}

void GetAns(int u) {
    for(pii query: q[u]) {
        int id = query.fi, add = query.se;
        int cost = d[u] + num[qq[id].fi] * qq[id].se - sum[qq[id].fi];
        ans[id] += cost * add;
    }
    for(int id: a[u]) {
        int x = get<0>(e[id]), y = get<1>(e[id]);
        x = x ^ y ^ u;
        if(x == p[u][0]) continue;
        ++num[get<2>(e[id])];
        sum[get<2>(e[id])] += get<3>(e[id]);
        GetAns(x);
        --num[get<2>(e[id])];
        sum[get<2>(e[id])] -= get<3>(e[id]);
    }
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    #define Task        "test"
    if(fopen(Task".inp", "r")) {
        freopen(Task".inp", "r", stdin);
        freopen(Task".out", "w", stdout);
    }
    cin >> n >> Q;
    for(int i = 1; i < n; ++i) {
        cin >> u >> v >> x >> y;
        e[i] = mt(u, v, x, y);
        a[u].pb(i); a[v].pb(i);
    }
    p[1][0] = 1; DFS(1);
    for(int i = 1; i <= Q; ++i) {
        cin >> x >> y >> u >> v;
        qq[i] = mp(x, y);
        q[LCA(u, v)].pb(mp(i, -2));
        q[u].pb(i, 1); q[v].pb(i, 1);
    }
    GetAns(1);
    for(int i = 1; i <= Q; ++i) cout << ans[i] << '\n';
}

```