#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i=0; i<(int)(n); ++i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using Graph = vector<vi>;  // vi <=> vl
using vb = vector<bool>;
using boolGraph = vector<vb>;
using P = pair<int, int>;  // int <=> ll
const int MOD = 1e9+7;
const double EPS = 1e-9;

vi dist, node, parent, depth;
vector<unordered_map<int, P>> color;

void dfs(const vector<Graph> &edge, int v, int p, int di, int de) {
  bool branch = edge[v].size() > 2 || p == -1 || color[v].size() > 250;
  if (branch) di = 0;
  de += branch;

  for (auto nv : edge[v]) {
    if (nv[0] == p) continue;

    dist[nv[0]] = di + nv[2];
    node[nv[0]] = branch ? nv[0] : node[v];
    parent[nv[0]] = branch ? v : parent[v];
    depth[nv[0]] = de;

    if (!branch) color[nv[0]] = color[v];
    ++color[nv[0]][nv[1]].first;
    color[nv[0]][nv[1]].second += nv[2];

    dfs(edge, nv[0], v, dist[nv[0]], de);
  }
}

int calc(const int &x, const int &y, int u, int v) {
  int du = dist[u], dv = dist[v];
  if (color[u].count(x)) du += color[u][x].first * y - color[u][x].second;
  if (color[v].count(x)) dv += color[v][x].first * y - color[v][x].second;

  if (node[u] == node[v]) {
    return abs(du - dv);
  }

  if (depth[u] == depth[v]) {
    return du + dv + calc(x, y, parent[u], parent[v]);
  }

  if (depth[u] > depth[v]) {
    dv = 0;
    u = parent[u];
  }
  else {
    du = 0;
    v = parent[v];
  }
  return du + dv + calc(x, y, u, v);
}

int main() {
  int N, Q; cin >> N >> Q;
  vector<Graph> edge(N);
  rep(i,N-1) {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    --a; --b;
    edge[a].push_back({b, c, d});
    edge[b].push_back({a, c, d});
  }

  dist.resize(N);
  node.resize(N);
  parent.resize(N);
  depth.resize(N);
  color.resize(N);

  dist[0] = 0;
  node[0] = 0;
  parent[0] = -1;
  depth[0] = 0;

  dfs(edge, 0, -1, 0, 0);

  rep(i,Q) {
    int x, y, u, v;
    cin >> x >> y >> u >> v;
    --u; --v;

    cout << calc(x, y, u, v) << endl;
  }
  return 0;
}

### Prompt

Please formulate 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>
using namespace std;
#define rep(i,n) for (int i=0; i<(int)(n); ++i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using Graph = vector<vi>;  // vi <=> vl
using vb = vector<bool>;
using boolGraph = vector<vb>;
using P = pair<int, int>;  // int <=> ll
const int MOD = 1e9+7;
const double EPS = 1e-9;

vi dist, node, parent, depth;
vector<unordered_map<int, P>> color;

void dfs(const vector<Graph> &edge, int v, int p, int di, int de) {
  bool branch = edge[v].size() > 2 || p == -1 || color[v].size() > 250;
  if (branch) di = 0;
  de += branch;

  for (auto nv : edge[v]) {
    if (nv[0] == p) continue;

    dist[nv[0]] = di + nv[2];
    node[nv[0]] = branch ? nv[0] : node[v];
    parent[nv[0]] = branch ? v : parent[v];
    depth[nv[0]] = de;

    if (!branch) color[nv[0]] = color[v];
    ++color[nv[0]][nv[1]].first;
    color[nv[0]][nv[1]].second += nv[2];

    dfs(edge, nv[0], v, dist[nv[0]], de);
  }
}

int calc(const int &x, const int &y, int u, int v) {
  int du = dist[u], dv = dist[v];
  if (color[u].count(x)) du += color[u][x].first * y - color[u][x].second;
  if (color[v].count(x)) dv += color[v][x].first * y - color[v][x].second;

  if (node[u] == node[v]) {
    return abs(du - dv);
  }

  if (depth[u] == depth[v]) {
    return du + dv + calc(x, y, parent[u], parent[v]);
  }

  if (depth[u] > depth[v]) {
    dv = 0;
    u = parent[u];
  }
  else {
    du = 0;
    v = parent[v];
  }
  return du + dv + calc(x, y, u, v);
}

int main() {
  int N, Q; cin >> N >> Q;
  vector<Graph> edge(N);
  rep(i,N-1) {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    --a; --b;
    edge[a].push_back({b, c, d});
    edge[b].push_back({a, c, d});
  }

  dist.resize(N);
  node.resize(N);
  parent.resize(N);
  depth.resize(N);
  color.resize(N);

  dist[0] = 0;
  node[0] = 0;
  parent[0] = -1;
  depth[0] = 0;

  dfs(edge, 0, -1, 0, 0);

  rep(i,Q) {
    int x, y, u, v;
    cin >> x >> y >> u >> v;
    --u; --v;

    cout << calc(x, y, u, v) << endl;
  }
  return 0;
}

```