In HackerLand, there are N provinces connected by \(N-1\) roads. All provinces are connected.

For every visit of province i each tourist has to pay \(A_i\) travel tickets.

People in HackerLand are kind: they want to give the tourists some free travel tickets. More specifically, at the road i, each tourist will receive \(c_i\) free tickets for his or her first visit there.

M tourists are planning to travel in HackerLand. The i-th tourist wants to start his journey from the province \(u_i\) and finish in the province \(v_i\). Every tourist from the province x can go only to provinces which are directly connected by road with the province x. They also do not have much time; therefore, they will visit as few provinces as possible during their journey.

Find the minimum number of travel tickets each of the tourists needs to buy beforehand.

Input
The first line contains two space-separated integers N and M.
The second line contains N space-separated integers, the i-th of which is \(A_i\).
The i-th of the following \(N-1\) lines contains three space-separated integers \(a_i\), \(b_i\), and \(c_i\), meaning that there is a road directly connecting provinces \(a_i\) and \(b_i\) that gives \(c_i\) free travel tickets for each tourist's first visit.
The i-th of the following M lines contains two integers \(u_i\) and \(v_i\), denoting the plan of the i-th tourist to travel to province \(v_i\) starting from province \(u_i\).

Output
Print M lines, the i-th of which contains one integer that denotes the number of travel tickets the i-th tourist needs.

Constraints
\(1 \le N, M \le 300,000\)
\(0 \le A_i, c_i \le 300,000\)
\(1 \le a_i, b_i, u_i, v_i \le N\)
It is guaranteed that the road network forms a tree.