Lelei La Lalena has been studying competitive programming in our world. Today, she decides to do a contest on DMOJ to prove her skill! Confident, Lelei opens the sixth problem of the October 2015 DMOPC and finds a really abstract problem with no story. So she decides to make one up and tell FatalEagle to add it to the problem. Anyway, here's the original problem:
Rory is playing with an array consisting of integer elements indexed from to and a positive integer . Rory will perform operations. Each operation is either type 1 or type 2.
Type 1 operation is in the form . You should add to each element in .
Type 2 operation is in the form . You should output the sum .
Lelei is confident she can solve this problem, so she tells you that she doesn't need your help, as she can solve it faster than you. Seeing this as a challenge, you obviously want to show Lelei that she could have a better time penalty, if only she asked for your help. Can you prove her wrong?
The first line of input will contain three integers , , and .
The second line of input will contain elements, the original elements of array in the order .
The next lines of input will contain an operation, either in the form for an operation of type 1 or for an operation of type 2.
For all subtasks:
for all valid .
Subtask 1 [15%]
Subtask 2 [15%]
Subtask 3 [15%]
Subtask 4 [15%]
Subtask 5 [40%]
For each operation of type 2, output the answer on a new line.
2 5 3 1 2 3 4 5 2 1 4 1 2 5 7 2 1 5
For the first operation, , and .
For the second operation, the array is now .
For the third operation, and