There are n villages along a high way, and divided the high way into n-1 segments. Each segment would charge a certain amount of money for being open for one day, and you can open or close an arbitrary segment in an arbitrary day, but you can open or close the segment for just one time, because the workers would be angry if you told them to work multiple period.
We know the transport plan in the next m days, each day there is one cargo need to transport from village $a_i$ to village $b_i$, and you need to guarantee that the segments between $a_i$ and $b_i$ are open in the i-th day. Your boss wants to minimize the total cost of the next m days, and you need to tell him the charge for each day.
(At the beginning, all the segments are closed.)
Multiple test case. For each test case, begins with two integers n, m(1<=n,m<=200000), next line contains n-1 integers. The i-th integer $w_i$(1<=$w_i$<=1000) indicates the charge for the segment between village i and village i+1 being open for one day. Next m lines, each line contains two integers $a_i, b_i(1\leq a_i,b_i<=n, a_i!=b_i)$.
For each test case, output m lines, each line contains the charge for the i-th day.