You are given a one-indexed tree of
Your friend asks you
1 r k
If the root of the tree is node , what is the heaviness of the heaviest subtree in the tree, where the heaviness of a subtree is the sum of all the weights in that subtree?2 r k
If the root of the tree is node , what is the heaviness of the heaviest subtree in the tree, where the heaviness of a subtree is the maximum of all the weights in that subtree?
It is guaranteed that
Can you answer these questions for your friend?
Input Specification
The first line will contain two integers
The next line will contain
The next
The next
Output Specification
For each question, output the heaviness of the
Subtasks
Subtask 1 [14%]
Subtask 2 [39%]
There will only be type 1
queries.
Subtask 3 [47%]
No additional constraints.
Sample Input for Subtask 1
7 5
5 3 -2 4 -1 0 -2
1 2
1 3
2 7
3 4
3 5
5 6
1 1 3
2 1 3
1 4 5
2 5 7
2 7 4
Sample Output for Subtask 1
1
4
0
-2
4
Sample Input for Subtask 2
6 4
-2 -1 5 -3 2 4
1 2
1 3
3 4
4 5
4 6
1 4 5
1 4 1
1 6 2
1 6 6
Sample Output for Subtask 2
-1
5
2
-3
Sample Input for Subtask 3
20 10
13 17 -7 -14 -5 11 -10 3 -4 8 -17 3 5 5 1 6 5 -9 0 -19
2 1
3 2
4 3
5 3
6 2
7 2
8 7
9 6
10 2
11 1
12 2
13 4
14 6
15 1
16 13
17 8
18 11
19 13
20 10
2 13 3
2 13 6
2 1 18
1 16 9
1 11 10
2 1 2
2 6 15
2 12 15
1 5 8
2 4 4
Sample Output for Subtask 3
17
11
-9
-2
1
17
0
0
3
13
Comments