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 <cstdio>
#include <vector>
#include <algorithm>
#include <functional>
#include <map>
#include <set>
#include <string>
#include <iostream>
#include <cassert>
#include <cmath>
using namespace std;

struct LCA {
        const int LOGM = 30;
        vector<int> depth;
        vector<vector<int>> parent;
        vector<pair<int, long long>> pare;
        vector<vector<long long>> parmax;
        LCA(int root, const vector<vector<int>> &g, const vector<pair<int, long long>> &pare) : pare(pare) {
                int n = g.size();
                depth.resize(n);
                parent.resize(LOGM);
                parmax.resize(LOGM);
                for (int i = 0; i < LOGM; i ++) { 
                        parent[i].resize(n);
                        parmax[i].resize(n);
                }
                function<void (int, int, int)> dfs = [&](int u, int prev, int d) {
                        parent[0][u] = prev;
                        parmax[0][u] = pare[u].second;
                        depth[u] = d;
                        for (auto v : g[u]) if (v != prev) dfs(v, u, d + 1);
                };
                dfs(root, -1, 0);
                for (int k = 0; k < LOGM - 1; k ++) {
                        for (int i = 0; i < n; i ++) {
                                if (parent[k][i] < 0) { 
                                        parent[k + 1][i] = -1;
                                } else { 
                                        parent[k + 1][i] = parent[k][parent[k][i]];
                                        if (parent[k + 1][i] >= 0) {
                                                parmax[k + 1][i] = max(parmax[k][i], parmax[k][parent[k][i]]);
                                        }
                                }
                        }
                }
        }
        int lca(int u, int v) { 
                if (depth[u] > depth[v]) swap(u, v);
                for (int k = 0; k < LOGM; k ++) {
                        if ((depth[v] - depth[u]) >> k & 1) { 
                                v = parent[k][v];
                        }
                }
                if (u == v) return u;
                for (int k = LOGM - 1; k >= 0; k --) {
                        if (parent[k][u] != parent[k][v]) {
                                u = parent[k][u];
                                v = parent[k][v];
                        }
                }
                return parent[0][u];
        }
        pair<int, long long> get(int a, int l) {
                long long res = 0;
                int d = depth[a] - depth[l] - 1;
                if (d <= 0) return { a, 0 };
                for (int k = 0; k < LOGM; k ++) {
                        if ((d >> k) & 1) {
                                res = max(res, parmax[k][a]);
                                a = parent[k][a];
                        }
                }
                return {a, res};
        }
        int dist(int u, int v) {
                return depth[u] + depth[v] - 2 * depth[lca(u, v)];
        }
};

int main() {
        int n;
        scanf("%d", &n);
        vector<int> w(n);
        vector<vector<int>> g(n);
        long long tot = 0;
        for (int i = 0; i < n; i ++) {
                scanf("%d", &w[i]);
                tot += w[i];
        }
        for (int i = 0; i < n - 1; i ++) {
                int a, b;
                scanf("%d%d", &a, &b);
                a --, b --;
                g[a].push_back(b);
                g[b].push_back(a);
        }
        vector<long long> sum(n);
        vector<long long> maxx(n);
        vector<pair<int, long long>> pare(n);
        function<void (int, int)> dfs = [&](int u, int prev) {
                pare[u].first = prev;
                sum[u] = w[u];
                vector<pair<long long, int>> val;
                int cnt = 0;
                for (auto v : g[u]) if (v != prev) {
                        dfs(v, u);
                        sum[u] += sum[v];
                        val.emplace_back(sum[v], v);
                        maxx[u] = max(maxx[u], sum[v]);
                        cnt ++;
                }
                sort(val.rbegin(), val.rend());
                if (cnt >= 2) {
                        for (auto v : g[u]) if (v != prev) {
                                if (val[0].second != v) {
                                        pare[v].second = val[0].first;
                                } else {
                                        pare[v].second = val[1].first;
                                }
                        }
                }
        };
        dfs(0, -1);
        vector<vector<pair<long long, int>>> ma(n);
        for (int i = 0; i < n; i ++) {
                for (auto v : g[i]) if (v != pare[i].first) {
                        ma[i].emplace_back(sum[v], v);
                }
                sort(ma[i].rbegin(), ma[i].rend());
        }
        LCA lca(0, g, pare);
        /*
        for (int i = 0; i < n; i ++) {
                for (int k = 0; k < 30; k ++) {
                        cerr << lca.parmax[k][i] << ' ';
                }
                cerr << endl;
        }
        */
        int q;
        scanf("%d", &q);
        while (q --) {
                int a, b;
                scanf("%d%d", &a, &b);
                a --, b --;
                int l = lca.lca(a, b);
                long long ans = tot - sum[l];

                if (a == l && b == l) { 
                        ans = max(ans, maxx[l]);
                        printf("%lld\n", ans);
                        continue;
                }

                if (a == l || b == l) {
                        if (a == l) swap(a, b);
                        ans = max(ans, maxx[a]);
                        auto geta = lca.get(a, l);
                        int va = geta.first;
                        ans = max(ans, geta.second);
                        ans = max(ans, pare[va].second);
                        printf("%lld\n", ans);
                        continue;
                }
                ans = max(ans, maxx[a]);
                ans = max(ans, maxx[b]);
                auto geta = lca.get(a, l);
                auto getb = lca.get(b, l);
                int va = geta.first;
                int vb = getb.first;
                ans = max(ans, geta.second);
                ans = max(ans, getb.second);
                int top1 = ma[l][0].second;
                int top2 = ma[l][1].second;
                if ((int) g[l].size() >= 4 || ((int) g[l].size() >= 3 && l == 0)) {
                        if (top1 == va) {
                                if (top2 == vb) {
                                        ans = max(ans, ma[l][2].first);
                                } else {
                                        ans = max(ans, ma[l][1].first);
                                }
                        } else if (top1 == vb) {
                                if (top2 == va) {
                                        ans = max(ans, ma[l][2].first);
                                } else {
                                        ans = max(ans, ma[l][1].first);
                                }
                        } else {
                                ans = max(ans, ma[l][0].first);
                        }
                }
                printf("%lld\n", ans);
        }
        return 0;
}

