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 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?

#### Input Specification

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.

#### Constraints

For all subtasks:

for all valid .

##### Subtask 1 [15%]

##### Subtask 2 [15%]

##### Subtask 3 [15%]

##### Subtask 4 [15%]

##### Subtask 5 [40%]

#### Output Specification

For each operation of type 2, output the answer on a new line.

#### Sample Input

```
2 5 3
1 2 3 4 5
2 1 4
1 2 5 7
2 1 5
```

#### Sample Output

```
0
1
```

#### Explanation

For the first operation, , and .

For the second operation, the array is now .

For the third operation, and .

## Comments

How come the author doesn't mention M as prime ?

Because maybe thats something you can observe yourself?

This comment is hidden due to too much negative feedback. Show it anyway.

No comment, reread the problem statement.

The problem statement only specifies that M is a positive integer.

A link that will take you to the exact same web page?

A comment that will take you to the same comment? Mind = blown!