Problem

Ai-chan has a tree $ T $ consisting of $ N $ vertices and $ N-1 $ edges. Each vertex has a number from $ 1 $ to $ N $ and a positive integer weight.

Answer the following $ Q $ queries in order.

* $ 1 \ le a_i, b_i \ le N $ ($ a_i \ ne b_i $) is given, so you can remove the vertices on the $ a_i $-$ b_i $ path of $ T $ and the edges that connect to them. Among the connected components, the weight of the connected component having the maximum weight is output. If there is no such connected component, 0 is output.



However, the weight of the connected component is defined by the sum of the weights of the vertices included in the connected component.

Ouput

For each query, 0 or the weight of the connected component with the maximum weight is output on one line.

Constraints

The input satisfies the following conditions.

* $ 2 \ le N \ le 10 ^ 5 $
* $ 1 \ le Q \ le 10 ^ 5 $
* $ 1 \ le w_i \ le 10 ^ 8 $ ($ 1 \ le i \ le N $)
* $ 1 \ le u_i, v_i \ le N $ ($ 1 \ le i \ le N-1 $)
* $ u_i \ ne v_i $
* $ i \ ne j $ is $ (u_i, v_i) \ ne (u_j, v_j) $ and $ (u_i, v_i) \ ne (v_j, u_j) $
* $ 1 \ le a_i, b_i \ le N $ ($ 1 \ le i \ le Q $)
* $ a_i \ ne b_i $

Input

The input is given in the following format.


$ N $
$ w_1 $ $ w_2 $ ... $ w_N $
$ u_1 $ $ v_1 $
$ u_2 $ $ v_2 $
...
$ u_ {N-1} $ $ v_ {N-1} $
$ Q $
$ a_1 $ $ b_1 $
$ a_2 $ $ b_2 $
...
$ a_Q $ $ b_Q $


All inputs are given as integers.

The number of vertices $ N $ of $ T $ is given in the first line.
On the second line, the weight $ w_i $ of the vertex $ i $ ($ 1 \ le i \ le N $) is given, separated by blanks.
The end points $ u_i and v_i $ of the edge $ _i $ ($ 1 \ le i \ le N-1 $) are given in the third and subsequent lines of $ N $ -1 separated by blanks.
The number of queries $ Q $ is given on the second line of $ N $ +.
$ A_i, b_i $ representing the query $ _i $ ($ 1 \ le i \ le Q $) are given in the $ Q $ line after the $ N $ + 3rd line, separated by blanks.

Examples

Input

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


Output

13
27
12


Input

5
1 2 3 4 5
1 2
2 3
3 4
4 5
3
1 2
1 5
2 4


Output

12
0
5


Input

15
3 8 4 2 6 5 1 2 10 3 4 2 6 1 1
1 2
2 3
3 4
3 5
2 6
6 7
6 8
1 9
9 10
10 11
10 12
9 13
13 14
13 15
5
1 1
2 7
6 10
1 15
3 4


Output

28
30
12
28
46
#include <bits/stdc++.h>
#define REP(i, a, n) for(ll i = ((ll) a); i < ((ll) n); i++)
using namespace std;
typedef long long ll;

ll N, Q;
ll W[100000], U[100000], V[100000], A[100000], B[100000];
vector<ll> E[100000];
ll x[100000][3], y[100000];
ll depth[100000], parent[20][100000], mx[20][100000];

void dfs(ll v, ll p, ll d) {
  parent[0][v] = p;
  depth[v] = d;
  for(ll u : E[v]) if(u != p) dfs(u, v, d + 1);
}

ll subtree_size(ll v, ll p) {
  vector<ll> child;
  for(ll u : E[v]) if(u != p) child.push_back(subtree_size(u, v));
  sort(child.begin(), child.end(), greater<ll>());
  REP(i, 0, 3) x[v][i] = i < child.size() ? child[i] : 0;
  for(ll u : E[v]) if(u != p) mx[0][u] = x[v][0] != y[u] ? x[v][0] : x[v][1];
  y[v] = W[v];
  REP(i, 0, child.size()) y[v] += child[i];
  return y[v];
}

ll query(ll u, ll v) {
  if(depth[u] > depth[v]) swap(u, v);
  REP(i, 0, 20) if(((depth[v] - depth[u]) >> i) & 1) v = parent[i][v];
  if(u == v) return u;
  for(ll i = 19; i >= 0; i--) if(parent[i][u] != parent[i][v]) {
    u = parent[i][u];
    v = parent[i][v];
  }
  return parent[0][u];
}

int main(void) {
  cin >> N;
  REP(i, 0, N) cin >> W[i];
  REP(i, 0, N - 1) {
    cin >> U[i] >> V[i]; U[i]--; V[i]--;
    E[U[i]].push_back(V[i]);
    E[V[i]].push_back(U[i]);
  }
  cin >> Q;
  REP(i, 0, Q) { cin >> A[i] >> B[i]; A[i]--; B[i]--; }

  dfs(0, -1, 0);
  subtree_size(0, -1);
  REP(i, 0, 19) REP(j, 0, N) parent[i + 1][j] = parent[i][j] >= 0 ? parent[i][parent[i][j]] : -1;
  REP(i, 0, 19) REP(j, 0, N) if(parent[i][j] >= 0) mx[i + 1][j] = max(mx[i][j], mx[i][parent[i][j]]);

  REP(q, 0, Q) {
    ll a = A[q], b = B[q], lca = query(a, b);
    ll ans = 0;
    if(lca == a || lca == b) {
      if(lca == b) swap(a, b);
      ans = max(ans, x[b][0]);
      for(ll i = 19; i >= 0; i--) {
        if(parent[i][b] >= 0 && depth[parent[i][b]] >= depth[lca]) {
          ans = max(ans, mx[i][b]);
          b = parent[i][b];
        }
      }
      ans = max(ans, y[0] - y[lca]);
    } else {
      ans = max(ans, x[a][0]);
      ans = max(ans, x[b][0]);
      for(ll i = 19; i >= 0; i--) {
        if(parent[i][a] >= 0 && depth[parent[i][a]] > depth[lca]) {
          ans = max(ans, mx[i][a]);
          a = parent[i][a];
        }
      }
      for(ll i = 19; i >= 0; i--) {
        if(parent[i][b] >= 0 && depth[parent[i][b]] > depth[lca]) {
          ans = max(ans, mx[i][b]);
          b = parent[i][b];
        }
      }
      vector<ll> r;
      r.push_back(y[a]);
      r.push_back(y[b]);
      r.push_back(-1);
      sort(r.begin(), r.end(), greater<ll>());
      REP(i, 0, 3) if(r[i] != x[lca][i]) ans = max(ans, x[lca][i]);
      ans = max(ans, y[0] - y[lca]);
    }
    cout << ans << endl;
  }
}

