You are given two trees, both with NN vertices, numbered from 1 to NN.
At the beginning, the weights of edges of both trees and the values of vertices of the first tree are given.
There are QQ operations. In each operation, the value of a vertice of the first tree will be modified. Please output max1≤u<v≤n{T1.dis(u,v)+T2.dis(u,v)+val(u)+val(v)}max1≤u<v≤n{T1.dis(u,v)+T2.dis(u,v)+val(u)+val(v)}after every operation.
Note that the symbol Tid.dis(u,v)Tid.dis(u,v) denotes the distance between vertice uu and vertice vv in the tree idid.
Note that the distance between two vertices in some tree is defined as the sum of the weights in the simple path between the two vertices.
Note that the symbol val(u)val(u) denotes the value of the vertice uu in the first tree.
Input
There are multiple test cases.
Each case starts with a line containing two positive integers N,Q(2≤N≤105,1≤Q≤105)N,Q(2≤N≤105,1≤Q≤105).
The second line contains NN integers a1,a2,...,aN(1≤ai≤109)a1,a2,...,aN(1≤ai≤109) denoting the values of vertices of the first tree.
Then follow N−1N−1 lines. Each line contains three integers u,v,w(1≤u,v≤n,1≤w≤109)u,v,w(1≤u,v≤n,1≤w≤109)describing the first tree. Namely, u,v,wu,v,w means that there is an edge weighted ww between vertice uu and vertice vv.
Then follow N−1N−1 lines. Each line contains three integers u,v,w(1≤u,v≤n,1≤w≤109)u,v,w(1≤u,v≤n,1≤w≤109)describing the second tree.
Then follow QQ lines. Each line contains two integers u,w(1≤u≤n,1≤w≤109)u,w(1≤u≤n,1≤w≤109), denoting the value of vertice uu of the first tree will be modified to ww.
It is guaranteed that the sum of NNs and the sum of QQs in all test cases are both no larger than 2×1052×105.
There is only one test case which contains NN and QQ that are both larger than 2×1042×104.
It is guaranteed that NN and QQ in every other test case are all no larger than 2×1042×104.
Output
For each test case, output QQ lines. Each line contains an integer denoting the answer.