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>
struct Edge {
  int32_t dst;
  int64_t weight1, weight2;
  Edge() {}
  Edge(int32_t dst_, int64_t weight_, int64_t weight2_) {
    dst = dst_;
    weight1 = weight_;
    weight2 = weight2_;
  }
};
int32_t* depths;
int32_t* parents;
int32_t *tin, *tout;
int32_t timer_ = 0;
void dfs(int32_t vertex, int32_t parent, std::vector<Edge>* tree,
         int32_t depth) {
  depths[vertex] = depth;
  parents[vertex] = parent;
  tin[vertex] = timer_++;
  for (int32_t i = 0; i < tree[vertex].size(); i++)
    if (tree[vertex][i].dst != parent)
      dfs(tree[vertex][i].dst, vertex, tree, depth + 1);
  tout[vertex] = timer_;
}
bool is_ancestor(int32_t v1, int32_t v2) {
  return tin[v1] <= tin[v2] && tout[v1] >= tout[v2];
}
class TransitionsOptimizer {
 private:
  int64_t* sums_to_root;
  int32_t* cdt;
  int32_t n_;
  int64_t* best_per_ancestor;
  void dfs_sums(int32_t vertex, int32_t parent, std::vector<Edge>* tree,
                int64_t sum) {
    sums_to_root[vertex] = sum;
    for (int32_t i = 0; i < tree[vertex].size(); i++)
      if (tree[vertex][i].dst != parent)
        dfs_sums(tree[vertex][i].dst, vertex, tree,
                 sum + tree[vertex][i].weight1 + tree[vertex][i].weight2);
  }
  int32_t lca_f(int32_t v1, int32_t v2) {
    if (is_ancestor(v1, v2)) return v1;
    if (is_ancestor(v2, v1)) return v2;
    for (int32_t i = 29; i >= 0; i--)
      if (ancestors[v1][i] != -1 && !is_ancestor(ancestors[v1][i], v2))
        v1 = ancestors[v1][i];
    return ancestors[v1][1];
  }
  int64_t sum_from_to(int32_t v1, int32_t v2) {
    int32_t lca = lca_f(v1, v2);
    return sums_to_root[v1] + sums_to_root[v2] - sums_to_root[lca] * 2;
  }
  int32_t* subtree_sizes;
  bool* global_colored;
  int32_t dfs_subtree_size(int32_t vertex, std::vector<Edge>* tree,
                           int32_t parent) {
    subtree_sizes[vertex] = 1;
    for (int32_t i = 0; i < tree[vertex].size(); i++)
      if (!global_colored[tree[vertex][i].dst] && tree[vertex][i].dst != parent)
        subtree_sizes[vertex] +=
            dfs_subtree_size(tree[vertex][i].dst, tree, vertex);
    return subtree_sizes[vertex];
  }
  int32_t find_centroid(std::vector<Edge>* tree, int32_t vertex, int32_t parent,
                        int32_t total_size) {
    int32_t fattest_child = 0;
    int32_t fattest_child_size = -1;
    for (int32_t i = 0; i < tree[vertex].size(); i++)
      if (tree[vertex][i].dst != parent && !global_colored[tree[vertex][i].dst])
        if (subtree_sizes[tree[vertex][i].dst] > fattest_child_size) {
          fattest_child = tree[vertex][i].dst;
          fattest_child_size = subtree_sizes[fattest_child];
        }
    if (fattest_child_size <= total_size / 2)
      return vertex;
    else
      return find_centroid(tree, fattest_child, vertex, total_size);
  }
  void build_centroid_decomposition(int32_t vertex, std::vector<Edge>* tree,
                                    int32_t num_vertices,
                                    int32_t centroid_parent) {
    dfs_subtree_size(vertex, tree, -1);
    int32_t centroid = find_centroid(tree, vertex, -1, subtree_sizes[vertex]);
    if (centroid_parent != -1)
      cdt[centroid] = centroid_parent;
    else
      cdt[centroid] = -1;
    global_colored[centroid] = true;
    for (int32_t i = 0; i < tree[centroid].size(); i++)
      if (!global_colored[tree[centroid][i].dst])
        build_centroid_decomposition(tree[centroid][i].dst, tree, num_vertices,
                                     centroid);
  }
  int32_t** ancestors;
  void build_ancestors(int32_t vertex, int32_t parent,
                       std::vector<Edge>* tree) {
    ancestors[vertex] = new int32_t[30];
    ancestors[vertex][0] = vertex;
    ancestors[vertex][1] = parent;
    for (int32_t i = 2; i < 30; i++)
      if (ancestors[vertex][i - 1] == -1)
        ancestors[vertex][i] = -1;
      else
        ancestors[vertex][i] = ancestors[ancestors[vertex][i - 1]][i - 1];
    for (int32_t i = 0; i < tree[vertex].size(); i++)
      if (tree[vertex][i].dst != parent)
        build_ancestors(tree[vertex][i].dst, vertex, tree);
  }

 public:
  void init(int32_t n, std::vector<Edge>* tree) {
    n_ = n;
    sums_to_root = new int64_t[n];
    dfs_sums(0, -1, tree, 0);
    cdt = new int32_t[n];
    subtree_sizes = new int32_t[n];
    global_colored = new bool[n];
    for (int32_t i = 0; i < n; i++) global_colored[i] = false;
    build_centroid_decomposition(0, tree, n, -1);
    ancestors = new int32_t*[n];
    build_ancestors(0, -1, tree);
  }
  void optimize(int64_t* transitions) {
    best_per_ancestor = new int64_t[n_];
    for (int32_t i = 0; i < n_; i++) best_per_ancestor[i] = INT64_MAX;
    for (int32_t i = 0; i < n_; i++) {
      int32_t cur = i;
      while (cur != -1) {
        best_per_ancestor[cur] = std::min(best_per_ancestor[cur],
                                          sum_from_to(i, cur) + transitions[i]);
        cur = cdt[cur];
      }
    }
    for (int32_t i = 0; i < n_; i++) {
      int32_t cur = i;
      while (cur != -1) {
        transitions[i] = std::min(transitions[i],
                                  best_per_ancestor[cur] + sum_from_to(i, cur));
        cur = cdt[cur];
      }
    }
  }
};
struct DoubledDistance {
  int64_t dist11, dist12, dist21, dist22;
  DoubledDistance() {}
  DoubledDistance(int64_t d1, int64_t d2, int64_t d3, int64_t d4) {
    dist11 = d1;
    dist12 = d2;
    dist21 = d3;
    dist22 = d4;
  }
  DoubledDistance combine(DoubledDistance other) {
    return {std::min(dist11 + other.dist11, dist12 + other.dist21),
            std::min(dist12 + other.dist22, dist11 + other.dist12),
            std::min(dist22 + other.dist21, dist21 + other.dist11),
            std::min(dist22 + other.dist22, dist21 + other.dist12)};
  }
  DoubledDistance reverse() { return {dist11, dist21, dist12, dist22}; }
};
class Segtree {
 private:
  int32_t size_;
  DoubledDistance* segtree;
  void build(int32_t node, int32_t left, int32_t right,
             DoubledDistance* parent_distances,
             std::vector<int32_t>& long_path) {
    if (right - left == 1) {
      segtree[node] = parent_distances[long_path[left]];
      return;
    }
    int32_t m = (left + right) / 2;
    build(node * 2 + 1, left, m, parent_distances, long_path);
    build(node * 2 + 2, m, right, parent_distances, long_path);
    segtree[node] = segtree[node * 2 + 2].combine(segtree[node * 2 + 1]);
  }
  DoubledDistance internal_query(int32_t node, int32_t left, int32_t right,
                                 int32_t query_left, int32_t query_right) {
    if (left >= query_right || right <= query_left) return {-1, -1, -1, -1};
    if (left >= query_left && right <= query_right) return segtree[node];
    int32_t m = (left + right) / 2;
    DoubledDistance c1 =
        internal_query(node * 2 + 1, left, m, query_left, query_right);
    DoubledDistance c2 =
        internal_query(node * 2 + 2, m, right, query_left, query_right);
    if (c1.dist11 == -1) return c2;
    if (c2.dist11 == -1) return c1;
    return c2.combine(c1);
  }

 public:
  void init(int32_t size, std::vector<int32_t>& data,
            DoubledDistance* parent_distances) {
    size_ = size;
    segtree = new DoubledDistance[4 * size];
    build(0, 0, size, parent_distances, data);
  }
  DoubledDistance query(int32_t left, int32_t right) {
    return internal_query(0, 0, size_, left, right);
  }
};
void get_lowest_vertex(int32_t vertex, int32_t parent, std::vector<Edge>* tree,
                       int32_t& lowest_vertex) {
  if (lowest_vertex == -1 || depths[vertex] > depths[lowest_vertex])
    lowest_vertex = vertex;
  for (int32_t i = 0; i < tree[vertex].size(); i++)
    if (tree[vertex][i].dst != parent)
      get_lowest_vertex(tree[vertex][i].dst, vertex, tree, lowest_vertex);
}
void compute_lpd(int32_t vertex, int32_t parent, std::vector<Edge>* tree,
                 std::vector<std::vector<int32_t> >& long_paths,
                 int32_t* long_path_indices, std::vector<Segtree>& long_trees,
                 DoubledDistance* parent_distances) {
  int32_t lowest_vertex = -1;
  get_lowest_vertex(vertex, parent, tree, lowest_vertex);
  long_paths.push_back({});
  long_trees.push_back({});
  int32_t long_path_ind = long_paths.size() - 1;
  int32_t cur = lowest_vertex;
  int32_t prev = -1;
  while (cur != parent) {
    long_paths[long_path_ind].push_back(cur);
    long_path_indices[cur] = long_path_ind;
    for (int32_t i = 0; i < tree[cur].size(); i++)
      if (tree[cur][i].dst != parents[cur] && tree[cur][i].dst != prev)
        compute_lpd(tree[cur][i].dst, cur, tree, long_paths, long_path_indices,
                    long_trees, parent_distances);
    prev = cur;
    cur = parents[cur];
  }
  std::reverse(long_paths[long_path_ind].begin(),
               long_paths[long_path_ind].end());
  long_trees[long_path_ind].init(long_paths[long_path_ind].size(),
                                 long_paths[long_path_ind], parent_distances);
}
DoubledDistance get_distance(int32_t vertex, int32_t v2,
                             int32_t* long_path_indices,
                             std::vector<std::vector<int32_t> >& long_paths,
                             int64_t* transition_cost,
                             std::vector<DoubledDistance*>& pref_up,
                             DoubledDistance* parent_distances,
                             std::vector<Segtree>& long_trees) {
  int32_t cur = vertex;
  DoubledDistance res = {0, transition_cost[cur], transition_cost[cur], 0};
  while (!is_ancestor(cur, v2)) {
    int32_t long_path_ind = long_path_indices[cur];
    std::vector<int32_t>& long_path = long_paths[long_path_ind];
    if (is_ancestor(long_path[0], v2)) {
      int32_t left = 0, right = long_path.size() + 1;
      while (right - left > 1) {
        int32_t m = (left + right) / 2;
        if (is_ancestor(long_path[m - 1], v2))
          left = m;
        else
          right = m;
      }
      int32_t lca = long_path[left - 1];
      if (cur != lca) {
        res = res.combine(long_trees[long_path_ind].query(
            depths[lca] + 1 - depths[long_path[0]],
            depths[cur] + 1 - depths[long_path[0]]));
      }
      return res;
    } else {
      if (cur != long_paths[long_path_ind][0]) {
        res = res.combine(
            pref_up[long_path_ind][depths[cur] - depths[long_path[0]]]);
        cur = long_paths[long_path_ind][0];
      }
      res = res.combine(parent_distances[cur]);
      cur = parents[cur];
    }
  }
  return res;
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  std::cout.tie(0);
  int32_t n;
  std::cin >> n;
  int64_t* transition_costs = new int64_t[n];
  for (int32_t i = 0; i < n; i++) std::cin >> transition_costs[i];
  std::vector<Edge>* true_graph = new std::vector<Edge>[2 * n];
  std::vector<Edge>* tree = new std::vector<Edge>[n];
  for (int32_t i = 1; i < n; i++) {
    int32_t src, dst;
    int64_t weight1, weight2;
    std::cin >> src >> dst >> weight1 >> weight2;
    tree[(2 * src - 1) / 2].emplace_back((2 * dst - 1) / 2, weight1, weight2);
    tree[(2 * dst - 1) / 2].emplace_back((2 * src - 1) / 2, weight1, weight2);
    true_graph[2 * src - 2].emplace_back(2 * dst - 2, weight1, 0);
    true_graph[2 * src - 1].emplace_back(2 * dst - 1, weight2, 0);
    true_graph[2 * dst - 2].emplace_back(2 * src - 2, weight1, 0);
    true_graph[2 * dst - 1].emplace_back(2 * src - 1, weight2, 0);
  }
  for (int32_t i = 0; i < n; i++) {
    true_graph[2 * i].emplace_back(2 * i + 1, transition_costs[i], 0);
    true_graph[2 * i + 1].emplace_back(2 * i, transition_costs[i], 0);
  }
  depths = new int32_t[n];
  tin = new int32_t[n];
  tout = new int32_t[n];
  parents = new int32_t[n];
  dfs(0, -1, tree, 0);
  TransitionsOptimizer optimizer;
  optimizer.init(n, tree);
  optimizer.optimize(transition_costs);
  DoubledDistance* parent_distances = new DoubledDistance[n];
  parent_distances[0] = {0, 0, 0, 0};
  for (int32_t i = 1; i < n; i++) {
    Edge parent_edge;
    for (int32_t j = 0; j < tree[i].size(); j++)
      if (tree[i][j].dst == parents[i]) {
        parent_edge = tree[i][j];
        break;
      }
    parent_distances[i] = {
        parent_edge.weight1,
        std::min(parent_edge.weight1 + transition_costs[parents[i]],
                 transition_costs[i] + parent_edge.weight2),
        std::min(parent_edge.weight2 + transition_costs[parents[i]],
                 transition_costs[i] + parent_edge.weight1),
        parent_edge.weight2};
  }
  int32_t* long_path_indices = new int32_t[n];
  std::vector<std::vector<int32_t> > long_paths;
  std::vector<Segtree> long_trees;
  compute_lpd(0, -1, tree, long_paths, long_path_indices, long_trees,
              parent_distances);
  std::vector<DoubledDistance*> pref_ups;
  for (int32_t i = 0; i < long_paths.size(); i++) {
    std::vector<int32_t>& long_path = long_paths[i];
    pref_ups.push_back(new DoubledDistance[long_path.size()]);
    DoubledDistance* prefix_cur = pref_ups[pref_ups.size() - 1];
    prefix_cur[0] = {0, transition_costs[long_path[0]],
                     transition_costs[long_path[0]], 0};
    for (int32_t j = 1; j < long_path.size(); j++)
      prefix_cur[j] = parent_distances[long_path[j]].combine(prefix_cur[j - 1]);
  }
  int32_t num_queries;
  std::cin >> num_queries;
  for (int32_t q = 0; q < num_queries; q++) {
    int32_t src, dst;
    std::cin >> src >> dst;
    src--;
    dst--;
    int32_t v1 = src / 2, v2 = dst / 2;
    DoubledDistance res =
        get_distance(v1, v2, long_path_indices, long_paths, transition_costs,
                     pref_ups, parent_distances, long_trees);
    DoubledDistance res2 =
        get_distance(v2, v1, long_path_indices, long_paths, transition_costs,
                     pref_ups, parent_distances, long_trees);
    DoubledDistance answer = res.combine(res2.reverse());
    int64_t selected_ans;
    if (src % 2 == 0 && dst % 2 == 0) selected_ans = answer.dist11;
    if (src % 2 == 0 && dst % 2 == 1) selected_ans = answer.dist12;
    if (src % 2 == 1 && dst % 2 == 0) selected_ans = answer.dist21;
    if (src % 2 == 1 && dst % 2 == 1) selected_ans = answer.dist22;
    std::cout << selected_ans << "\n";
  }
  return 0;
}