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

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

const int INF=1001001001001001001ll;

int par[20][111111];
int A[111111];

int N;
vint G[111111];

int dep[111111];
int latte[111111];
int dp[20][111111];
vint lis[111111];
void dfs(int v,int p,int d){
    dep[v]=d;
    par[0][v]=p;
    latte[v]=A[v];
    lis[v].pb(0);
    lis[v].pb(0);
    for(auto u:G[v]){
        if(u==p)continue;
        dfs(u,v,d+1);
        latte[v]+=latte[u];
        lis[v].pb(latte[u]);
    }
}

int lca(int a,int b){
    if(dep[a]<dep[b])swap(a,b);
    rep(i,20)if((dep[a]-dep[b])>>i&1)a=par[i][a];
    if(a==b)return a;
    for(int i=19;i>=0;i--)if(par[i][a]!=par[i][b])a=par[i][a],b=par[i][b];
    return par[0][a];
}

signed main(){
    cin>>N;
    rep(i,N)cin>>A[i];
    rep(i,N-1){
        int a,b;
        cin>>a>>b;
        a--;b--;
        G[a].pb(b);G[b].pb(a);
    }

    dfs(0,-1,0);

    rep(i,N){
        sort(all(lis[i]));
        reverse(all(lis[i]));
    }
    for(int i=1;i<N;i++){
        int p=par[0][i];
        if(lis[p][0]==latte[i]){
            dp[0][i]=lis[p][1];
        }
        else{
            dp[0][i]=lis[p][0];
        }
    }


    rep(i,19){
        rep(j,N){
            if(par[i][j]==-1){
                par[i+1][j]=-1;
                dp[i+1][j]=dp[i][j];
            }
            else{
                par[i+1][j]=par[i][par[i][j]];
                dp[i+1][j]=max(dp[i][par[i][j]],dp[i][j]);
            }
        }
    }


    int sumall=accumulate(A,A+N,0ll);


    int Q;cin>>Q;
    while(Q--){
        int a,b;
        cin>>a>>b;a--;b--;
        int p=lca(a,b);
        int ans=0;
        rep(lattemalta,2){
            swap(a,b);
            int x=a;
            if(a==p)continue;
            chmax(ans,lis[a][0]);
            int d=dep[x]-dep[p]-1;
            rep(i,20){
                if(d>>i&1){
                    chmax(ans,dp[i][x]);
                    x=par[i][x];
                }
            }
            a=x;



        }

        {
            bool flaga=false,flagb=false;
            for(auto x:lis[p]){
                if(!flaga&&x==latte[a]){
                    flaga=true;
                    continue;
                }
                if(!flagb&&x==latte[b]){
                    flagb=true;
                    continue;
                }
                chmax(ans,x);
                break;
            }
        }
        chmax(ans,sumall-latte[p]);
        cout<<ans<<endl;
    }
    return 0;
}

