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.*;
import java.util.*;

public class A {
	public static void main (String[] args) { new A(); }

	int n;
	long[] vals;
	ArrayList<Edge>[] adj;
	int[] size, idxOfParent;
	long[][] dp;
	
	int log;
	int[] depth;
	int[][] lift;
	long[][] sumEdges, sumDP;
	
	public A() {
		FastScanner fs = new FastScanner();
		PrintWriter out = new PrintWriter(System.out);
		System.err.println("");

		n = fs.nextInt();
		int q = fs.nextInt();
		
		vals = new long[n];
		for(int i = 0; i < n; i++) vals[i] = fs.nextLong();
		
		adj = new ArrayList[n];
		for(int i = 0; i < n; i++) adj[i] = new ArrayList<>();
		
		for(int i = 0; i < n-1; i++) {
			int u = fs.nextInt()-1;
			int v = fs.nextInt()-1;
			int we = fs.nextInt();
			adj[u].add(new Edge(v, we));
			adj[v].add(new Edge(u, we));
		}
		
		size = new int[n];
		for(int i = 0; i < n; i++) size[i] = adj[i].size();
		
		dp = new long[n][];
		for(int i = 0; i < n; i++)
			dp[i] = new long[size[i] + 1];
		
		idxOfParent = new int[n];
		Arrays.fill(idxOfParent, -1);
		
		dfs(0, -1);
		dfs2(0, -1, -1);

//		for(int i = 0; i < n; i++) {
//			System.out.printf("Idx: %d -- %s\n", i + 1, Arrays.toString(dp[i]));
//		}
		
		log = Integer.numberOfTrailingZeros(Integer.highestOneBit(n))+1;
		depth = new int[n];
		lift = new int[log][n];
		sumDP = new long[log][n];
		sumEdges = new long[log][n];
		
		for(int[] x : lift) Arrays.fill(x, -1);
		
		dfs3(0, -1, -1);
		
		for(int lg = 1; lg < log; lg++) {
			for(int i = 0; i < n; i++) {
				if(lift[lg-1][i] == -1) continue;
				int p = lift[lg-1][i];
				if(lift[lg-1][p] == -1) continue;
				
				lift[lg][i] = lift[lg - 1][p];
				sumDP[lg][i] = sumDP[lg-1][i] + sumDP[lg-1][p];
				sumEdges[lg][i] = sumEdges[lg-1][i] + sumEdges[lg-1][p];
			}
		}
		
		for(int qq = 0; qq < q; qq++) {
			int u = fs.nextInt()-1, v = fs.nextInt()-1;
			if(u == v) {
				out.println(dp[u][size[u]] + vals[u]);
				continue;
			}
			
			int L = LCA(u, v);
			long res;
			if(L == u) {
				res = solve1Path(v, u);
			}
			else if(L == v) {
				res = solve1Path(u, v);
			}
			else {
				res = solveLCA(u, v);
			}
			
			out.println(res);
		}
		
		out.close();
	}
	
	//if LCA(u, v) != u or v
	long solveLCA(int u, int v) {
		if(depth[v] > depth[u]) return solveLCA(v, u);
		int L = LCA(u, v);
		
		long res = 0;
		Edge fromU = adj[u].get(idxOfParent[u]);
		res += dp[u][idxOfParent[u]] + 2 * fromU.we;
		Edge fromV = adj[v].get(idxOfParent[v]);
		res += dp[v][idxOfParent[v]] + 2 * fromV.we;
		
		for(int lg = log - 1; lg >= 0; lg--) {
			if(lift[lg][u] == -1) continue;
			int to = lift[lg][u];
			
			if(depth[to] < depth[v]) continue;
			
			res += sumDP[lg][u] + sumEdges[lg][u];
			u = to;
		}
		
		for(int lg = log-1; lg >= 0; lg--) {
			if(lift[lg][u] == -1) continue;
			int to = lift[lg][u];
			if(depth[to] <= depth[L]) continue;
			
			res += sumDP[lg][u] + sumEdges[lg][u];
			res += sumDP[lg][v] + sumEdges[lg][v];
			
			u = lift[lg][u];
			v = lift[lg][v];
		}
		
		int idxU = -1, idxV = -1;
		for(int i = 0; i < size[L]; i++) {
			if(adj[L].get(i).v == u) {
				idxU = i;
			}
			if(adj[L].get(i).v == v) {
				idxV = i;
			}
		}
		
		long finAdd = dp[L][size[L]];
		finAdd -= Math.max(0, dp[v][idxOfParent[v]]);
		finAdd -= Math.max(0, dp[u][idxOfParent[u]]);
		finAdd += vals[L];
		finAdd -= adj[L].get(idxU).we;
		finAdd -= adj[L].get(idxV).we;

		res += finAdd;
		return res;
	}
	
	//ONLY if LCA(u, v) = v.
	long solve1Path(int u, int v) {
		long res = 0;
		Edge inc = adj[u].get(idxOfParent[u]);
		res += dp[u][idxOfParent[u]] + 2 * inc.we;
		
		for(int lg = log-1; lg >= 0; lg--) {
			if(lift[lg][u] == -1) continue;
			int to = lift[lg][u];
			
			if(depth[to] >= depth[v]+1) {
				res += sumDP[lg][u] + sumEdges[lg][u];
				u = to;
			}
		}
		
		//lift[0][u] = v
		int idx = -1;
		for(int i = 0; i < size[v]; i++) {
			if(adj[v].get(i).v == u) {
				idx = i;
			}
		}
		
		res += dp[v][idx] + adj[v].get(idx).we;
		
		return res;
	}
	
	int LCA(int u, int v) {
		if(depth[v] > depth[u]) return LCA(v, u);
		for(int lg = log-1; lg >= 0; lg--) {
			if(lift[lg][u] < 0) continue;
			int to = lift[lg][u];
			if(depth[to] >= depth[v]) {
				u = to;
			}
		}
		
		if(u == v) return u;
		
		for(int lg = log-1; lg >= 0; lg--) {
			if(lift[lg][u] != lift[lg][v]) {
				u = lift[lg][u];
				v = lift[lg][v];
			}
		}
		
		return lift[0][v];
	}
	
	//binary lifting stuff
	void dfs3(int u, int p, int idxIn) {
		for(int i = 0; i < size[u]; i++) {
			Edge e = adj[u].get(i);
			if(e.v == p) continue;
			
			depth[e.v] = 1+depth[u];
			lift[0][e.v] = u;
			sumEdges[0][e.v] = e.we;
			
			long val = dp[u][i];
			if(idxIn != -1) val -= Math.max(0, dp[p][idxIn]);
			
			sumDP[0][e.v] = val;
			
			dfs3(e.v, u, i);
		}
	}
	
	//tree re-rooting
	//idxIn = the index of u in adj[p]
	void dfs2(int u, int p, int idxIn) {
		int idx = size[u];
		Edge incoming = null;
		if(p != -1) {
			for(int i = 0; i < size[u]; i++)
				if(adj[u].get(i).v == p) {
					idx = i;
					incoming = adj[u].get(i);
				}
			
			long cur = dp[u][idx] - vals[u] + 2 * incoming.we;
			if(dp[p][idxIn] > 0) cur += dp[p][idxIn];
			
			dp[u][size[u]] = cur; //cost of being root
		}
		
		for(int i = 0; i < size[u]; i++) {
			Edge e = adj[u].get(i);
			if(e.v == p) continue;
			
			long cur = dp[u][size[u]];
			cur -= Math.max(0, dp[e.v][ idxOfParent[e.v] ]);
			cur += vals[u] - 2 * e.we;
			
			dp[u][i] = cur;
		}
		
		for(int i = 0; i < size[u]; i++) {
			Edge e = adj[u].get(i);
			if(e.v == p) continue;
			
			dfs2(e.v, u, i);
		}
	}
	
	int dfs(int u, int p) {
		int idx = size[u];
		Edge incoming = null;
		
		if(p != -1) {
			for(int i = 0; i < size[u]; i++) {
				if(adj[u].get(i).v == p) {
					idx = i;
					incoming = adj[u].get(i);
				}
			}
			idxOfParent[u] = idx;
		}
		
		if(p != -1) dp[u][idx] = vals[u] - 2 * incoming.we;
		
		for(int i = 0; i < size[u]; i++) {
			Edge now = adj[u].get(i);
			if(now.v == p) continue;
			int id = dfs(now.v, u);
			
			if(dp[now.v][id] > 0) {
				dp[u][idx] += dp[now.v][id];
			}
		}
		
		return idx;
	}
	
	class Edge {
		int v;
		long we;
		Edge(int vv, int ww) {
			v = vv;
			we = ww;
		}
		public String toString() {
			return String.format("u --> %d WE = %d", v, we);
		}
	}
	
	class FastScanner {
		public int BS = 1<<16;
		public char NC = (char)0;
		byte[] buf = new byte[BS];
		int bId = 0, size = 0;
		char c = NC;
		double num = 1;
		BufferedInputStream in;

		public FastScanner() {
			in = new BufferedInputStream(System.in, BS);
		}

		public FastScanner(String s) {
			try {
				in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
			}
			catch (Exception e) {
				in = new BufferedInputStream(System.in, BS);
			}
		}

		public char nextChar(){
			while(bId==size) {
				try {
					size = in.read(buf);
				}catch(Exception e) {
					return NC;
				}                
				if(size==-1)return NC;
				bId=0;
			}
			return (char)buf[bId++];
		}

		public int nextInt() {
			return (int)nextLong();
		}

		public long nextLong() {
			num=1;
			boolean neg = false;
			if(c==NC)c=nextChar();
			for(;(c<'0' || c>'9'); c = nextChar()) {
				if(c=='-')neg=true;
			}
			long res = 0;
			for(; c>='0' && c <='9'; c=nextChar()) {
				res = (res<<3)+(res<<1)+c-'0';
				num*=10;
			}
			return neg?-res:res;
		}

		public double nextDouble() {
			double cur = nextLong();
			return c!='.' ? cur:cur+nextLong()/num;
		}

		public String next() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c>32) {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}

		public String nextLine() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c!='\n') {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}

		public boolean hasNext() {
			if(c>32)return true;
			while(true) {
				c=nextChar();
				if(c==NC)return false;
				else if(c>32)return true;
			}
		}
		
		public int[] nextIntArray(int n) {
			int[] res = new int[n];
			for(int i = 0; i < n; i++) res[i] = nextInt();
			return res;
		}
		
	}

}