Problem: You are given a weighted tree (undirected connected graph with no cycles, loops or multiple edges) with n vertices. The edge \\{u_j, v_j\} has weight w_j. Also each vertex i has its own value a_i assigned to it.

Let's call a path starting in vertex u and ending in vertex v, where each edge can appear no more than twice (regardless of direction), a 2-path. Vertices can appear in the 2-path multiple times (even start and end vertices).

For some 2-path p profit Pr(p) = ∑_{v ∈ distinct vertices in  p}{a_v} - ∑_{e ∈ distinct edges in  p}{k_e ⋅ w_e}, where k_e is the number of times edge e appears in p. That is, vertices are counted once, but edges are counted the number of times they appear in p.

You are about to answer m queries. Each query is a pair of vertices (qu, qv). For each query find 2-path p from qu to qv with maximal profit Pr(p).

Input

The first line contains two integers n and q (2 ≤ n ≤ 3 ⋅ 10^5, 1 ≤ q ≤ 4 ⋅ 10^5) — the number of vertices in the tree and the number of queries.

The second line contains n space-separated integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^9) — the values of the vertices.

Next n - 1 lines contain descriptions of edges: each line contains three space separated integers u_i, v_i and w_i (1 ≤ u_i, v_i ≤ n, u_i ≠ v_i, 1 ≤ w_i ≤ 10^9) — there is edge \\{u_i, v_i\} with weight w_i in the tree.

Next q lines contain queries (one per line). Each query contains two integers qu_i and qv_i (1 ≤ qu_i, qv_i ≤ n) — endpoints of the 2-path you need to find.

Output

For each query print one integer per line — maximal profit Pr(p) of the some 2-path p with the corresponding endpoints.

Example

Input

7 6
6 5 5 3 2 1 2
1 2 2
2 3 2
2 4 1
4 5 1
6 4 2
7 3 25
1 1
4 4
5 6
6 4
3 4
3 7


Output

9
9
9
8
12
-14

Note

Explanation of queries: 

  1. (1, 1) — one of the optimal 2-paths is the following: 1 → 2 → 4 → 5 → 4 → 2 → 3 → 2 → 1. Pr(p) = (a_1 + a_2 + a_3 + a_4 + a_5) - (2 ⋅ w(1,2) + 2 ⋅ w(2,3) + 2 ⋅ w(2,4) + 2 ⋅ w(4,5)) = 21 - 2 ⋅ 12 = 9. 
  2. (4, 4): 4 → 2 → 1 → 2 → 3 → 2 → 4. Pr(p) = (a_1 + a_2 + a_3 + a_4) - 2 ⋅ (w(1,2) + w(2,3) + w(2,4)) = 19 - 2 ⋅ 10 = 9. 
  3. (5, 6): 5 → 4 → 2 → 3 → 2 → 1 → 2 → 4 → 6. 
  4. (6, 4): 6 → 4 → 2 → 1 → 2 → 3 → 2 → 4. 
  5. (3, 4): 3 → 2 → 1 → 2 → 4. 
  6. (3, 7): 3 → 2 → 1 → 2 → 4 → 5 → 4 → 2 → 3 → 7. 

Solution (in JAVA):

Solution:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author kessido
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskG solver = new TaskG();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskG {
        int[][] g;
        int n;
        int[] a;
        int[][] edges;
        int[] edgeWeight;
        int[] parEdge;
        long[] dp;
        long[] dpPathToRootWithDetours;
        int time = 0;
        int[] appearance;
        int[] firstAppearance;
        int[] depth;

        void dfs(int i, int parE) {
            firstAppearance[i] = time;
            appearance[time++] = i;
            parEdge[i] = parE;
            dp[i] = a[i];
            for (int eIndex : g[i]) {
                if (eIndex == parE) continue;
                int child = edges[eIndex][0];
                if (child == i) {
                    child = edges[eIndex][1];
                }
                dfs(child, eIndex);
                appearance[time++] = i;
                dp[i] += Math.max(dp[child] - edgeWeight[eIndex] * 2, 0);
            }
        }

        void dfs2(int i) {
            if (i == 0) {
                dpPathToRootWithDetours[i] = dp[i];
            } else {
                int parE = parEdge[i];
                int par = edges[parE][0];
                if (par == i) par = edges[parE][1];
                depth[i] = depth[par] + 1;
                dpPathToRootWithDetours[i] = dpPathToRootWithDetours[par] - Math.max(0, dp[i] - edgeWeight[parE] * 2);
                dpPathToRootWithDetours[i] -= edgeWeight[parE];
                dpPathToRootWithDetours[i] += dp[i];

                long myPathWeight = Math.max(dp[i] - edgeWeight[parEdge[i]] * 2, 0);
                long change = dp[par] - myPathWeight - edgeWeight[parEdge[i]] * 2;
                change = Math.max(change, 0);
                dp[i] += change;
            }
            for (int eIndex : g[i]) {
                if (eIndex == parEdge[i]) continue;
                dfs2(edges[eIndex][0] != i ? edges[eIndex][0] : edges[eIndex][1]);
            }
        }

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            n = in.NextInt();
            int q = in.NextInt();
            a = in.NextIntArray(n);
            edges = new int[n - 1][2];
            edgeWeight = new int[n - 1];
            for (int i = 0; i < n - 1; i++) {
                for (int j = 0; j < 2; j++) {
                    edges[i][j] = in.NextInt() - 1;
                }
                edgeWeight[i] = in.NextInt();
            }
            {
                long[] count = new long[n];
                for (int i = 0; i < n - 1; i++) {
                    for (int j = 0; j < 2; j++) {
                        count[edges[i][j]]++;
                    }
                }
                g = new int[n][];
                for (int i = 0; i < n; i++) {
                    g[i] = new int[(int) count[i]];
                }
                for (int i = 0; i < n - 1; i++) {
                    for (int j = 0; j < 2; j++) {
                        g[edges[i][j]][(int) --count[edges[i][j]]] = i;
                    }
                }
            }
            dp = new long[n];
            dpPathToRootWithDetours = new long[n];
            parEdge = new int[n];
            depth = new int[n];
            firstAppearance = new int[n];
            appearance = new int[(n - 1) * 2 + 1];
            dfs(0, -1);
            dfs2(0);
            GraphLowestCommonAncestor.LCA lca = GraphLowestCommonAncestor.createLCA(appearance, firstAppearance, depth);
            for (int i = 0; i < q; i++) {
                int u = in.NextInt() - 1;
                int v = in.NextInt() - 1;
                int lcaI = lca.getLCA(u, v);
                long res = dpPathToRootWithDetours[u] + dpPathToRootWithDetours[v] - 2 * dpPathToRootWithDetours[lcaI] + dp[lcaI];
                out.println(res);
            }
        }

    }

    static class Pair<T1, T2> {
        public T1 first;
        public T2 second;

        public Pair(T1 f, T2 s) {
            first = f;
            second = s;
        }

    }

    static class MinRangeSparseTable implements ISearchInRange {
        private final int[][] sparseTables;
        private final long[] array;
        private final boolean reverseOrdered;

        public MinRangeSparseTable(long[] array, boolean reverseOrdered) {
            this.reverseOrdered = reverseOrdered;
            this.array = array;
            int LCALength = IntegerExtension.getNumberOfBits(array.length);
            sparseTables = new int[LCALength][];
            sparseTables[0] = new int[array.length];
            for (int i = 0; i < array.length; i++) {
                sparseTables[0][i] = i;
            }
            for (int i = 1; i < LCALength; i++) {
                int size = 1 << i;
                int jumpSize = 1 << (i - 1);
                sparseTables[i] = new int[sparseTables[0].length - size + 1];
                for (int j = 0; j < sparseTables[i].length; j++) {
                    sparseTables[i][j] = min(sparseTables[i - 1][j], sparseTables[i - 1][j + jumpSize]);
                }
            }
        }

        private int min(int a, int b) {
            return ((array[a] < array[b]) ^ reverseOrdered) ? a : b;
        }


        public Pair<Long, Long> queryIndexValueInRange(long l, long r) {
            int size = (int) (r - l + 1);
            int LCAIndex = IntegerExtension.getNumberOfBits(size) - 1;
            int sizeNeeded = 1 << LCAIndex;
            int res = min(sparseTables[LCAIndex][(int) l], sparseTables[LCAIndex][(int) (r - sizeNeeded + 1)]);
            return new Pair<>((long) res, array[res]);
        }

        public MinRangeSparseTable(long[] array) {
            this(array, false);
        }

    }

    static interface ISearchInRange {
    }

    static class IntegerExtension {
        public static int getNumberOfBits(long i) {
            return 64 - Long.numberOfLeadingZeros(i);
        }

    }

    static class InputReader {
        BufferedReader reader;
        StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine(), " \t\n\r\f,");
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int NextInt() {
            return Integer.parseInt(next());
        }

        public int[] NextIntArray(int n) {
            return NextIntArray(n, 0);
        }

        public int[] NextIntArray(int n, int offset) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = NextInt() + offset;
            }
            return a;
        }

    }

    static class GraphLowestCommonAncestor {
        public static GraphLowestCommonAncestor.LCA createLCA(int[] appearances, final int[] firstAppearance, final int[] depth) {
            return new GraphLowestCommonAncestor.LCA_MinRangeSparseTable(appearances, firstAppearance, depth);
        }

        public interface LCA {
            int getLCA(int a, int b);

        }

        private static class LCA_MinRangeSparseTable implements GraphLowestCommonAncestor.LCA {
            private final MinRangeSparseTable minRangeSparseTable;
            private final int[] firstAppearance;
            private final int[] indexToNode;

            public LCA_MinRangeSparseTable(int[] appearances, final int[] firstAppearance, final int[] depth) {
                this.firstAppearance = firstAppearance;
                this.indexToNode = appearances;
                long[] depthOrder = new long[appearances.length];
                for (int i = 0; i < depthOrder.length; i++) {
                    depthOrder[i] = depth[appearances[i]];
                }
                minRangeSparseTable = new MinRangeSparseTable(depthOrder);
            }


            public int getLCA(int a, int b) {
                a = firstAppearance[a];
                b = firstAppearance[b];
                int l = Math.min(a, b), r = Math.max(a, b);
                return indexToNode[(int) (long) minRangeSparseTable.queryIndexValueInRange(l, r).first];
            }

        }

    }
}