#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second

using namespace std;

const int maxN = 1e5 + 10;

typedef pair<int, int> ii;
struct TEdge{int x, color, w;};
struct Query{int id, color, dist, k;};

int             n, m, root;
int             h[maxN], p[20][maxN], d[maxN], cnt[maxN], res[maxN];
vector<Query>   q[maxN];
vector<TEdge>   adj[maxN];

void dfs1(int u, int par, int d){
    h[u] = d;

    for(auto t : adj[u]){
        int v = t.x;
        if(v == par) continue;
        p[0][v] = u;
        dfs1(v, u, d + 1);
    }
}

int lca(int x, int y){
    for (int k = 19; k >= 0; k--)
        if (h[p[k][x]] >= h[y])
            x = p[k][x];
    for (int k = 19; k >= 0; k--)
        if (h[p[k][y]] >= h[x])
            y = p[k][y];
    for (int k = 19; k >= 0; k--)
        if (p[k][x] != p[k][y]) {
            x = p[k][x];
            y = p[k][y];
        }
    while (x != y) {
        x = p[0][x];
        y = p[0][y];
    }
    return x;
}

void dfs2(int x, int par, int dist)
{
    for(int i = 0; i < q[x].size(); ++i){
        Query tmp = q[x][i];
        res[tmp.id] += tmp.k * (dist - d[tmp.color] + cnt[tmp.color] * tmp.dist);
    }

    for(int i = 0; i < adj[x].size(); ++i){
        TEdge u = adj[x][i];
        if(u.x == par) continue;
        cnt[u.color]++;
        d[u.color] += u.w;
        dfs2(u.x, x, dist + u.w);
        cnt[u.color]--;
        d[u.color] -= u.w;
    }
}

int32_t main()
{
    ios_base::sync_with_stdio(false); cin.tie(); cout.tie();
    //freopen("ColorfulTree.inp", "r", stdin);

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

    dfs1(1, 0, 1);

    for(int k = 1; k <= 19; ++k)
        for(int i = 1; i <= n; ++i)
            p[k][i] = p[k-1][p[k-1][i]];

    for(int i = 1; i <= m; ++i)
    {
        int color, dist, u, v;
        cin >> color >> dist >> u >> v;
        q[u].push_back({i, color, dist, 1});
        q[v].push_back({i, color, dist, 1});
        q[lca(u,v)].push_back({i, color, dist, -2});
    }

    dfs2(1, 0, 0);

    for(int i = 1; i <= m; ++i)
        cout << res[i] << " ";
}

### Prompt

Generate a CPP solution to the following 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

### Response

```cpp
#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second

using namespace std;

const int maxN = 1e5 + 10;

typedef pair<int, int> ii;
struct TEdge{int x, color, w;};
struct Query{int id, color, dist, k;};

int             n, m, root;
int             h[maxN], p[20][maxN], d[maxN], cnt[maxN], res[maxN];
vector<Query>   q[maxN];
vector<TEdge>   adj[maxN];

void dfs1(int u, int par, int d){
    h[u] = d;

    for(auto t : adj[u]){
        int v = t.x;
        if(v == par) continue;
        p[0][v] = u;
        dfs1(v, u, d + 1);
    }
}

int lca(int x, int y){
    for (int k = 19; k >= 0; k--)
        if (h[p[k][x]] >= h[y])
            x = p[k][x];
    for (int k = 19; k >= 0; k--)
        if (h[p[k][y]] >= h[x])
            y = p[k][y];
    for (int k = 19; k >= 0; k--)
        if (p[k][x] != p[k][y]) {
            x = p[k][x];
            y = p[k][y];
        }
    while (x != y) {
        x = p[0][x];
        y = p[0][y];
    }
    return x;
}

void dfs2(int x, int par, int dist)
{
    for(int i = 0; i < q[x].size(); ++i){
        Query tmp = q[x][i];
        res[tmp.id] += tmp.k * (dist - d[tmp.color] + cnt[tmp.color] * tmp.dist);
    }

    for(int i = 0; i < adj[x].size(); ++i){
        TEdge u = adj[x][i];
        if(u.x == par) continue;
        cnt[u.color]++;
        d[u.color] += u.w;
        dfs2(u.x, x, dist + u.w);
        cnt[u.color]--;
        d[u.color] -= u.w;
    }
}

int32_t main()
{
    ios_base::sync_with_stdio(false); cin.tie(); cout.tie();
    //freopen("ColorfulTree.inp", "r", stdin);

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

    dfs1(1, 0, 1);

    for(int k = 1; k <= 19; ++k)
        for(int i = 1; i <= n; ++i)
            p[k][i] = p[k-1][p[k-1][i]];

    for(int i = 1; i <= m; ++i)
    {
        int color, dist, u, v;
        cin >> color >> dist >> u >> v;
        q[u].push_back({i, color, dist, 1});
        q[v].push_back({i, color, dist, 1});
        q[lca(u,v)].push_back({i, color, dist, -2});
    }

    dfs2(1, 0, 0);

    for(int i = 1; i <= m; ++i)
        cout << res[i] << " ";
}

```