Household Ledger (Easy)

Interview

Time limit1sMemory limit512 MB

Summary

Maintain a ledger over N days with point additions and range-sum queries, printing the sum of entries from day p to day q.

Level: Easy3 of 10
Topics: Prefix sum, Array
Solved: No attempts yet

Problem

Wolgok writes down every bit of income and spending by date. Managing that money matters a lot to him. He tried a ledger app on his phone, but he has lived so long that the app took forever to give him the number he wanted. Re-entering a record he had forgotten and recomputing was slow too, and Wolgok, who has no patience, smashed the phone. Write the program that helps him.

The program handles two operations. The first adds one income or spending entry on day $p$ of Wolgok's life. Income arrives as a positive number and spending as a negative number. The second computes and prints how much the balance changed from day $p$ through day $q$ . Wolgok may be in debt, so the balance on some day $i$ can be negative.

Input

The first line contains the number of days $N$ that Wolgok has lived and the number of queries $Q$ . ( $1 \le N \le 10^4$ , $1 \le Q \le 10^3$ )

Each of the next $Q$ lines holds a query in one of these two forms.

1 p x : add $x$ on day $p$ . ( $1 \le p \le N$ , $-2 \times 10^9 \le x \le 2 \times 10^9$ )
2 p q : print the total change from day $p$ through day $q$ . ( $1 \le p \le q \le N$ )

Output

For each 2 query, print the computed value on its own line, in the order the queries are given.

Examples6

Example 1

Input

Expected output

2000
27000

Example 2
Input
```
1 3
2 1 1
1 1 -7
2 1 1
```
Expected output
```
0
-7
```

Example 3

Input

Expected output

Example 4

Input

10000 6
1 1 2000000000
1 2 2000000000
1 3 2000000000
2 1 10000
1 10000 -2000000000
2 1 10000

Expected output

6000000000
4000000000

Example 5

Input

6 7
1 1 -2000000000
1 6 -2000000000
2 1 6
2 2 5
1 3 1
2 3 3
2 1 3

Expected output

-4000000000
0
1
-1999999999

Example 6

Input

Expected output