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;

#define int long long

const int MAX_N = 100010;
const int LOG_N = 22;

using Pi = pair<int, int>;
using vint = vector<int>;

int N, Q;
int w[MAX_N];
vint graph[MAX_N];

int subsz[MAX_N];
int depth[MAX_N];
vector<Pi> chdat[MAX_N];

int par[LOG_N][MAX_N];
int mxw[LOG_N][MAX_N];

int getchw(int u, int ch1 = -1, int ch2 = -1) {
  for(Pi p : chdat[u]) {
    if(p.second != ch1 && p.second != ch2) return p.first;
  }
  return 0;
}

void init() {
  memset(par, -1, sizeof(par));
  function<void(int, int, int)> dfs = [&dfs](int u, int p, int d) {
    par[0][u] = p;
    depth[u] = d;
    subsz[u] = w[u];
    for(int v : graph[u]) {
      if(v == p) continue;
      dfs(v, u, d+1);
      subsz[u] += subsz[v];
      chdat[u].emplace_back(subsz[v], v);
    }
    sort(chdat[u].rbegin(), chdat[u].rend());
  };
  dfs(0, -1, 0);
  for(int i = 1; i < N; ++i) {
    int p = par[0][i];
    mxw[0][i] = getchw(p, i);
  }
  for(int i = 0; i+1 < LOG_N; ++i) {
    for(int v = 0; v < N; ++v) {
      if(par[i][v] == -1) {
	par[i+1][v] = -1;
	mxw[i+1][v] = -1;
      } else {
	par[i+1][v] = par[i][par[i][v]];
	mxw[i+1][v] = max(mxw[i][par[i][v]], mxw[i][v]);
      }
    }
  }
}

int ask(int u, int v) {
  if(depth[u] > depth[v]) swap(u, v);
  int res = getchw(v);
  for(int i = 0; i < LOG_N; ++i) {
    if(((depth[v]-depth[u])>>i)&1) {
      res = max(res, mxw[i][v]);
      v = par[i][v];
    }
  }
  if(u == v) return max(res, subsz[0]-subsz[u]);

  res = max(res, getchw(u));
  for(int i = LOG_N-1; i >= 0; --i) {
    if(par[i][u] != par[i][v]) {
      res = max(res, mxw[i][u]);
      res = max(res, mxw[i][v]);
      u = par[i][u];
      v = par[i][v];
    }
  }

  int lca = par[0][u];
  return max({res, subsz[0]-subsz[lca], getchw(lca, u, v)});
}

signed main() {
  scanf("%lld", &N);
  for(int i = 0; i < N; ++i) scanf("%lld", &w[i]);
  for(int i = 0; i < N-1; ++i) {
    int u, v;
    scanf("%lld %lld", &u, &v);
    --u, --v;
    graph[u].push_back(v);
    graph[v].push_back(u);
  }
  init();
  scanf("%lld", &Q);
  for(int i = 0; i < Q; ++i) {
    int a, b;
    scanf("%lld %lld", &a, &b);
    --a, --b;
    printf("%lld\n", ask(a, b));
  }
  return 0;
}

