Household Ledger

Wolgok keeps a ledger of income and spending by day, and wants to check how much the balance moved over a chosen period of days. The ledger application on the phone recomputed everything from scratch on every new entry, so it was too slow, and filling in an entry that had been missed earlier was just as slow. Write a program that handles the two operations below quickly.

The first operation adds an amount $x$ to the entry for day $p$ of Wolgok's life. Income is given as a positive number and spending as a negative number. The same day can be added to more than once, and the amounts accumulate.

The second operation reports the sum of the amounts recorded from day $p$ through day $q$, which is the net change of the balance over that period. Wolgok can be in debt, so this value can be negative.

At the start no day has any record, so the amount on every day is $0$.

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

Each of the next $Q$ lines contains a query in one of the two forms below.

• 1 p x : add $x$ to the entry for day $p$. ($1 \le p \le N$, $-2 \times 10^9 \le x \le 2 \times 10^9$)
• 2 p q : print the net change from day $p$ through day $q$. ($1 \le p \le q \le N$)

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