Problem: You are given a special undirected graph. It consists of 2n vertices numbered from 1 to 2n. The following properties hold for the graph:

  * there are exactly 3n-2 edges in the graph: n edges connect vertices having odd numbers with vertices having even numbers, n - 1 edges connect vertices having odd numbers with each other, and n - 1 edges connect vertices having even numbers with each other; 
  * for each edge (u, v) between a pair of vertices with odd numbers, there exists an edge (u + 1, v + 1), and vice versa; 
  * for each odd number u ∈ [1, 2n - 1], there exists an edge (u, u + 1); 
  * the graph is connected; moreover, if we delete all vertices with even numbers from it, and all edges incident to them, the graph will become a tree (the same applies to deleting odd vertices).



So, the graph can be represented as two trees having the same structure, and n edges connecting each vertex of the first tree to the corresponding vertex of the second tree.

Edges of the graph are weighted. The length of some simple path in the graph is the sum of weights of traversed edges.

You are given q queries to this graph; in each query, you are asked to compute the length of the shortest path between some pair of vertices in this graph. Can you answer all of the queries?

Input

The first line of the input contains one integer n (2 ≤ n ≤ 3 ⋅ 10^5).

The second line contains n integers w_{1, 2}, w_{3,4}, ..., w_{2n - 1, 2n} (1 ≤ w_{i, i + 1} ≤ 10^{12}). These integers describe the weights of the edges connecting odd vertices with even ones.

Then n-1 lines follow. i-th line contains four integers x_i, y_i, w_{i, 1} and w_{i, 2} (1 ≤ x_i, y_i ≤ n, x_i ≠ y_i, 1 ≤ w_{i, j} ≤ 10^{12}); it describes two edges: one connecting 2x_i - 1 with 2y_i - 1 and having weight w_{i, 1}; another connecting 2x_i with 2y_i and having weight w_{i, 2}.

The next line contains one integer q (1 ≤ q ≤ 6 ⋅ 10^5) — the number of queries.

Then q lines follow, i-th line contains two integers u_i and v_i (1 ≤ u_i, v_i ≤ 2n, u_i ≠ v_i), describing a query "compute the length of the shortest path between vertices u_i and v_i".

Output

Print q integers, i-th integer should be equal to the answer to the i-th query.

Example

Input


5
3 6 15 4 8
1 2 5 4
2 3 5 7
1 4 1 5
1 5 2 1
3
1 2
5 6
1 10


Output


3
15
4

Note

The graph in the first test looks like that:

<image>

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const long long MAXN = 600007;
const long long INF = 1e18;
const long long LOGN = 20;
long long wside[MAXN], dst[MAXN];
vector<pair<long long, long long> > rasta[MAXN];
long long n;
long long baba[MAXN], bcost[MAXN];
void filldst(long long u, long long p) {
  for (pair<long long, long long> pr : rasta[u]) {
    if (pr.first == p) continue;
    dst[pr.first] = dst[u] + pr.second;
    baba[pr.first] = u;
    bcost[pr.first] = pr.second;
    filldst(pr.first, u);
  }
}
struct SNode {
  long long mn, lazy;
  SNode() : mn(INF), lazy(0) {}
};
SNode combineSNode(const SNode &s1, const SNode &s2) {
  SNode rt;
  rt.mn = min(s1.mn, s2.mn);
  return rt;
}
struct SegTreeLazy {
  long long n;
  vector<long long> ar;
  vector<SNode> tr;
  SegTreeLazy(long long n) : n(n), ar(n + 7), tr(4 * n + 7) {}
  void build(long long u, long long l, long long r) {
    if (l == r) {
      tr[u].mn = ar[l];
      return;
    }
    long long mid = (l + r) / 2;
    build(u * 2, l, mid);
    build(u * 2 + 1, mid + 1, r);
    tr[u] = combineSNode(tr[u * 2], tr[u * 2 + 1]);
  }
  void propagate(long long u, long long l, long long r) {
    if (tr[u].lazy) {
      tr[u].mn += tr[u].lazy;
      if (l != r) {
        tr[u * 2].lazy += tr[u].lazy;
        tr[u * 2 + 1].lazy += tr[u].lazy;
      }
      tr[u].lazy = 0;
    }
  }
  void update(long long u, long long l, long long r, long long x, long long y,
              long long v) {
    propagate(u, l, r);
    if (r < x || y < l) return;
    if (x <= l && r <= y) {
      tr[u].lazy += v;
      propagate(u, l, r);
      return;
    }
    long long mid = (l + r) / 2;
    update(u * 2, l, mid, x, y, v);
    update(u * 2 + 1, mid + 1, r, x, y, v);
    tr[u] = combineSNode(tr[u * 2], tr[u * 2 + 1]);
  }
  SNode query(long long u, long long l, long long r, long long x, long long y) {
    propagate(u, l, r);
    if (r < x || y < l) return SNode();
    if (x <= l && r <= y) return tr[u];
    long long mid = (l + r) / 2;
    return combineSNode(query(u * 2, l, mid, x, y),
                        query(u * 2 + 1, mid + 1, r, x, y));
  }
};
SegTreeLazy *stree;
long long project(long long u) { return (u + 1) / 2; }
vector<long long> edg[MAXN];
long long shuru[MAXN], shesh[MAXN];
long long tym0;
void euler(long long u, long long p) {
  shuru[u] = ++tym0;
  for (long long v : edg[u]) {
    if (v == p) continue;
    euler(v, u);
  }
  shesh[u] = tym0;
}
void rootRerouting(long long u, long long p) {
  wside[u] = stree->query(1, 1, n, 1, n).mn;
  for (long long i = 0; i < edg[u].size(); i++) {
    long long v = edg[u][i];
    if (v == p) continue;
    long long cst = rasta[u * 2 - 1][i].second + rasta[u * 2][i].second;
    stree->update(1, 1, n, 1, n, cst);
    stree->update(1, 1, n, shuru[v], shesh[v], -2 * cst);
    rootRerouting(v, u);
    stree->update(1, 1, n, 1, n, -cst);
    stree->update(1, 1, n, shuru[v], shesh[v], 2 * cst);
  }
}
long long sbtr[MAXN], lvl[MAXN], pr[MAXN][LOGN];
long long chainIdx[MAXN], chainHead[MAXN], flatIdx[MAXN], flat[MAXN];
long long chainCnt, flatCnt;
void dfs(long long u, long long p) {
  lvl[u] = lvl[p] + 1;
  pr[u][0] = p;
  for (long long k = 1; k < LOGN; k++) {
    pr[u][k] = pr[pr[u][k - 1]][k - 1];
  }
  sbtr[u] = 1;
  for (long long v : edg[u]) {
    if (v == p) continue;
    dfs(v, u);
    sbtr[u] += sbtr[v];
  }
}
long long getLCA(long long u, long long v) {
  if (lvl[u] < lvl[v]) swap(u, v);
  for (long long k = LOGN - 1; k >= 0; k--) {
    if (lvl[u] - (1LL << k) >= lvl[v]) {
      u = pr[u][k];
    }
  }
  if (u == v) return u;
  for (long long k = LOGN - 1; k >= 0; k--) {
    if (pr[u][k] != pr[v][k]) {
      u = pr[u][k];
      v = pr[v][k];
    }
  }
  return pr[u][0];
}
void HLD(long long u, long long p) {
  chainIdx[u] = chainCnt;
  flatIdx[u] = flatCnt;
  flat[flatCnt] = u;
  flatCnt++;
  long long biggie = -1, mx = 0;
  for (long long v : edg[u]) {
    if (v == p) continue;
    if (mx < sbtr[v]) {
      mx = sbtr[v];
      biggie = v;
    }
  }
  if (biggie == -1) return;
  HLD(biggie, u);
  for (long long v : edg[u]) {
    if (v == p || v == biggie) continue;
    chainCnt++;
    chainHead[chainCnt] = v;
    HLD(v, u);
  }
}
void performHLD(long long root) {
  dfs(root, 0);
  chainCnt = 0;
  flatCnt = 0;
  chainHead[0] = root;
  HLD(root, 0);
}
struct info {
  long long xx, xy, yx, yy;
  info() {}
  info(long long xx, long long xy, long long yx, long long yy)
      : xx(xx), xy(xy), yx(yx), yy(yy) {}
};
ostream &operator<<(ostream &out, const info &i) {
  return out << "(" << i.xx << "," << i.xy << "," << i.yx << "," << i.yy << ")";
}
info combineInfo(const info &i1, const info &i2) {
  return info(
      min(i1.xx + i2.xx, i1.xy + i2.yx), min(i1.xx + i2.xy, i1.xy + i2.yy),
      min(i1.yy + i2.yx, i1.yx + i2.xx), min(i1.yy + i2.yy, i1.yx + i2.xy));
}
info withParent[MAXN];
info tr[4 * MAXN + 7];
void init(long long u, long long l, long long r) {
  if (l == r) {
    tr[u] = withParent[l];
    return;
  }
  long long mid = (l + r) / 2;
  init(u * 2, l, mid);
  init(u * 2 + 1, mid + 1, r);
  tr[u] = combineInfo(tr[u * 2 + 1], tr[u * 2]);
}
info query(long long u, long long l, long long r, long long x, long long y) {
  if (x <= l && r <= y) return tr[u];
  long long mid = (l + r) / 2;
  if (y <= mid) return query(u * 2, l, mid, x, y);
  if (mid < x) return query(u * 2 + 1, mid + 1, r, x, y);
  return combineInfo(query(u * 2 + 1, mid + 1, r, x, y),
                     query(u * 2, l, mid, x, y));
}
void prepareSegHLD() {
  for (long long i = 1; i <= n; i++) {
    long long u = 2 * i - 1;
    long long p = baba[u];
    long long x = flatIdx[i];
    withParent[x].xx =
        min(bcost[u], wside[i] + bcost[u + 1] + wside[project(p)]);
    withParent[x].yy =
        min(bcost[u + 1], wside[i] + bcost[u] + wside[project(p)]);
    withParent[x].xy =
        min(bcost[u] + wside[project(p)], wside[i] + bcost[u + 1]);
    withParent[x].yx =
        min(bcost[u + 1] + wside[project(p)], wside[i] + bcost[u]);
  }
  init(1, 0, n - 1);
}
void upSegments(long long l, long long u,
                vector<pair<long long, long long> > &vp) {
  while (chainIdx[l] != chainIdx[u]) {
    long long uhead = chainHead[chainIdx[u]];
    vp.push_back(pair<long long, long long>(flatIdx[uhead], flatIdx[u]));
    u = pr[uhead][0];
  }
  if (l != u) {
    vp.push_back(pair<long long, long long>(flatIdx[l] + 1, flatIdx[u]));
  }
}
void manage(long long x, long long y, long long goLow, info &duh) {
  info qr = query(1, 0, n - 1, x, y);
  if (goLow) swap(qr.xy, qr.yx);
  duh = combineInfo(duh, qr);
}
info solveChain(long long u, long long v) {
  long long l = getLCA(u, v);
  info duh(0, wside[u], wside[u], 0);
  if (u == v) return duh;
  vector<pair<long long, long long> > rt;
  upSegments(l, u, rt);
  for (pair<long long, long long> pr : rt) manage(pr.first, pr.second, 0, duh);
  rt.clear();
  upSegments(l, v, rt);
  reverse(rt.begin(), rt.end());
  for (pair<long long, long long> pr : rt) manage(pr.first, pr.second, 1, duh);
  return duh;
}
long long answer(long long u, long long v) {
  long long x = project(u), y = project(v);
  info duh = solveChain(x, y);
  if (u % 2 == 1 && v % 2 == 1)
    return duh.xx;
  else if (u % 2 == 1 && v % 2 == 0)
    return duh.xy;
  else if (u % 2 == 0 && v % 2 == 1)
    return duh.yx;
  else if (u % 2 == 0 && v % 2 == 0)
    return duh.yy;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n;
  for (long long i = 1; i <= n; i++) cin >> wside[i];
  for (long long i = 1; i < n; i++) {
    long long x, y, w1, w2;
    cin >> x >> y >> w1 >> w2;
    edg[x].push_back(y);
    edg[y].push_back(x);
    x = x * 2 - 1;
    y = y * 2 - 1;
    rasta[x].emplace_back(y, w1);
    rasta[y].emplace_back(x, w1);
    x++;
    y++;
    rasta[x].emplace_back(y, w2);
    rasta[y].emplace_back(x, w2);
  }
  euler(1, 0);
  filldst(1, 0);
  filldst(2, 0);
  stree = new SegTreeLazy(n);
  for (long long i = 1; i <= n; i++) {
    stree->ar[shuru[i]] = dst[2 * i - 1] + dst[2 * i] + wside[i];
  }
  stree->build(1, 1, n);
  rootRerouting(1, 0);
  performHLD(1);
  prepareSegHLD();
  long long q;
  cin >> q;
  while (q--) {
    long long u, v;
    cin >> u >> v;
    cout << answer(u, v) << "\n";
  }
  return 0;
}