Prom is coming up soon, and Peter doesn't own any good socks!
Requiring the snazziest socks for this occasion, he plans on riding the Snazzy Sock Shopping Bus for days. The Bus has a set of stores it can visit, each with a snazziness value . There is guaranteed to be exactly one path between every pair of stores. In order to keep styles fresh, the Bus will change which store, , it starts at, and which store, , it ends at every day.
Being an impulsive sock-lover, Peter will buy socks at every store he visits, adding to his total snazziness sum for the day's trip. Wanting to stay hip and cool, he ropes you in to decide when to start/stop riding the bus for the maximum snazziness sum. Having limited time, he will only ride for one continuous series of stores. He will also always visit at least one store per day, as he can't go to prom without socks!
Input Specification
The first line contains 2 integers .
The next line contains integers , the snazziness value of store .
The next lines contain 2 integers , indicating there is a street between and .
The next lines contain 2 integers .
Output Specification
For each day, print the maximum snazziness value Peter can achieve on a new line.
Subtasks
Subtask 1 [30%]
Subtask 2 [70%]
No further constraints.
Sample Input
9 10
-7 10 0 3 5 0 6 -9 1
1 6
4 3
7 9
5 9
6 2
9 2
3 6
8 9
1 3
3 4
6 6
3 8
9 6
7 4
6 2
3 5
7 9
1 4
Sample Output
0
3
0
11
11
20
10
16
7
3
Comments