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;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcount

#define INF 1e16
#define mod 1000000007

ll n,q;
ll w[100001];
vector<ll> g[100001];
ll d[100001];
ll p[20][100001];
vector<ll> s[100001];
ll br[20][100001];

void dfs(ll v,ll pre,ll dist){
  p[0][v]=pre;
  d[v]=dist;
  for(ll nv : g[v]){
    if(nv==pre)continue;
    dfs(nv,v,dist+1);
    w[v]+=w[nv];
    if(s[v].size()>=3&&s[v].back()<w[nv]){
      s[v].pop_back();
      s[v].push_back(w[nv]);
      sort(all(s[v]));
      reverse(all(s[v]));
    }else if(s[v].size()<=2){
      s[v].push_back(w[nv]);
      sort(all(s[v]));
      reverse(all(s[v]));
    }
  }
}

int lca(int u,int v){
  if(d[u]>d[v])swap(u,v);
  for(int k=0;k<20;k++){
    if((d[v]-d[u])>>k&1){
      v=p[k][v];
    }
  }
  if(u==v)return u;
  for(int k=20-1;k>=0;k--){
    if(p[k][u]!=p[k][v]){
      u=p[k][u];
      v=p[k][v];
    }
  }
  return p[0][u];
}

int main(){
  cin>>n;
  rep(i,n)cin>>w[i];
  rep(i,n-1){
    ll a,b;
    cin>>a>>b;
    a--;b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  dfs(0,-1,0);

  rep(v,n){
    for(ll ch : g[v]){
      if(d[ch]<d[v])continue;
      if(w[ch]==s[v][0]){
        if(s[v].size()>=2)br[0][ch]=s[v][1];
        else br[0][ch]=-INF;
      }else{
        if(s[v].size()>=1)br[0][ch]=s[v][0];
        else br[0][ch]=-INF;
      }
    }
  }

  rep(k,19){
    rep(i,n){
      if(p[k][i]!=-1) p[k+1][i]=p[k][p[k][i]];
      else p[k+1][i]=-1;
    }
  }

  rep(k,19){
    rep(i,n){
      if(p[k][i]!=-1) br[k+1][i]=max(br[k][i],br[k][p[k][i]]);
      else br[k+1][i]=-INF;
    }
  }

  cin>>q;
  while(q--){
    ll a,b;
    cin>>a>>b;
    a--;b--;
    if(d[a]>d[b])swap(a,b);
    ll lc=lca(a,b);
    ll res=w[0]-w[lc];

    if(lc==a){
      ll nb=b,pb=b;
      while(p[0][pb]!=lc&&pb!=lc){
        ll i=0;
        while(p[i][pb]!=-1&&d[p[i][pb]]>d[lc])i++;
        i--;
        pb=p[i][pb];
      }
      while(nb!=lc){
        ll i=0;
        while(p[i][nb]!=-1&&d[p[i][nb]]>=d[lc])i++;
        i--;
        maxch(res,br[i][nb]);
        nb=p[i][nb];
      }

      if(s[b].size()>0)maxch(res,s[b][0]);

      multiset<ll> rest;
      rep(k,s[a].size())rest.insert(s[a][k]);
      if(rest.find(w[pb])!=rest.end())rest.erase(rest.find(w[pb]));
      if(rest.size()>0)maxch(res,*rest.rbegin());
    }else{
      ll na=a,pa=a;
      while(p[0][pa]!=lc){
        ll i=0;
        while(p[i][pa]!=-1&&d[p[i][pa]]>d[lc])i++;
        i--;
        pa=p[i][pa];
      }
      while(na!=pa){
        ll i=0;
        while(p[i][na]!=-1&&d[p[i][na]]>=d[pa])i++;
        i--;
        maxch(res,br[i][na]);
        na=p[i][na];
      }

      ll nb=b,pb=b;
      while(p[0][pb]!=lc){
        ll i=0;
        while(p[i][pb]!=-1&&d[p[i][pb]]>d[lc])i++;
        i--;
        pb=p[i][pb];
      }
      while(nb!=pb){
        ll i=0;
        while(p[i][nb]!=-1&&d[p[i][nb]]>=d[pb])i++;
        i--;
        maxch(res,br[i][nb]);
        nb=p[i][nb];
      }

      if(s[a].size()>0)maxch(res,s[a][0]);
      if(s[b].size()>0)maxch(res,s[b][0]);
      multiset<ll> rest;
      rep(k,s[lc].size())rest.insert(s[lc][k]);
      if(rest.find(w[pa])!=rest.end())rest.erase(rest.find(w[pa]));
      if(rest.find(w[pb])!=rest.end())rest.erase(rest.find(w[pb]));
      if(rest.size()>0)maxch(res,*rest.rbegin());
    }
    cout<<res<<endl;
  }

  return 0;
}

