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>

using namespace std;

using int64 = long long;

int N, W[100000], Q;
vector< int > g[100000];
int dep[100000];
int64 sub[100000];
int64 heavy[3][100000];
const int LOG = 18;

int par[LOG][100000];
int64 sz[LOG][100000];

void predfs(int idx, int p, int d) {
  par[0][idx] = p;
  dep[idx] = d;
  sub[idx] += W[idx];
  for(auto &to : g[idx]) {
    if(to == p) continue;
    predfs(to, idx, d + 1);
    sub[idx] += sub[to];
    if(heavy[0][idx] < sub[to]) {
      heavy[2][idx] = heavy[1][idx];
      heavy[1][idx] = heavy[0][idx];
      heavy[0][idx] = sub[to];
    } else if(heavy[1][idx] < sub[to]) {
      heavy[2][idx] = heavy[1][idx];
      heavy[1][idx] = sub[to];
    } else if(heavy[2][idx] < sub[to]) {
      heavy[2][idx] = sub[to];
    }
  }
}

void dfs(int idx, int p) {
  for(auto &to : g[idx]) {
    if(to == p) continue;
    dfs(to, idx);
    sz[0][to] = heavy[heavy[0][idx] == sub[to]][idx];
  }
}

int lca(int x, int y) {
  if(dep[x] > dep[y]) swap(x, y);
  for(int i = LOG - 1; i >= 0; i--) {
    if((dep[y] - dep[x]) >> i & 1) y = par[i][y];
  }
  if(x == y) return x;
  for(int i = LOG - 1; i >= 0; i--) {
    if(par[i][x] != par[i][y]) {
      x = par[i][x];
      y = par[i][y];
    }
  }
  return par[0][x];
}

int main() {
  scanf("%d", &N);
  for(int i = 0; i < N; i++) {
    scanf("%d", &W[i]);
  }
  for(int i = 1; i < N; i++) {
    int x, y;
    scanf("%d %d", &x, &y);
    --x, --y;
    g[x].emplace_back(y);
    g[y].emplace_back(x);
  }
  predfs(0, -1, 0);
  dfs(0, -1);
  for(int i = 0; i + 1 < LOG; i++) {
    for(int j = 0; j < N; j++) {
      if(par[i][j] == -1) par[i + 1][j] = -1;
      else par[i + 1][j] = par[i][par[i][j]];
      if(par[i + 1][j] == -1) continue;
      sz[i + 1][j] = max(sz[i][j], sz[i][par[i][j]]);
    }
  }

  int64 all = accumulate(W, W + N, 0LL);

  scanf("%d", &Q);
  while(Q--) {
    int a, b;
    scanf("%d %d", &a, &b);
    --a, --b;
    if(dep[a] > dep[b]) swap(a, b);
    int p = lca(a, b);

    int64 ret = 0;
    if(p != a) {

      bool ng[3] = {};
      ret = max(ret, heavy[0][a]);
      ret = max(ret, heavy[0][b]);

      for(auto c : {a, b}) {
        int xx = dep[p] + 1;
        for(int i = LOG - 1; i >= 0; i--) {
          if(((dep[c] - xx) >> i) & 1) {
            ret = max(ret, sz[i][c]);
            c = par[i][c];
          }
        }
        for(int i = 0; i < 3; i++) {
          if(ng[i]) continue;
          if(sub[c] == heavy[i][p]) {
            ng[i] = true;
            break;
          }
        }
      }
      for(int i = 0; i < 3; i++) {
        if(ng[i]) continue;
        ret = max(ret, heavy[i][p]);
      }
    } else if(p != b) {
      ret = max(ret, heavy[0][b]);
      int c = b;
      int xx = dep[a] + 1;
      for(int i = LOG - 1; i >= 0; i--) {
        if(((dep[c] - xx) >> i) & 1) {
          ret = max(ret, sz[i][c]);
          c = par[i][c];
        }
      }
      ret = max(ret, sz[0][c]);
    } else {
      ret = max(ret, heavy[0][p]);
    }

    printf("%lld\n", max(ret, all - sub[p]));
  }
}


