Description

Given a sequence of length $n(0\leq n\leq 10^5)$ whose initial values are all $0$, perform $x(0\leq x\leq 10^5)$ modifications on some positions, adding a number each time, and during this process ask $y(0\leq y\leq 10^5)$ queries to find the sum of each interval.

Input Format

The first line contains $1$ integer, the length of the sequence $n$.

The second line contains $1$ integer, the number of operations $w(0\leq w\leq 2\times 10^5)$.

Then follow $w$ lines, each representing an add or a query operation.

Here, add is denoted by x, and query is denoted by y.

The format of $x$ is x a b, meaning add $b$ to the $a$-th number in the sequence. It is guaranteed that $1 \leq a \leq n$, $1 \leq b \leq 10^9$.

The format of $y$ is y a b, meaning query the sum over the interval from $a$ to $b$. It is guaranteed that $1 \leq a \leq b \leq n$.

Output Format

Each line contains a positive integer, which is the result of each query.

5
4
x 3 8
y 1 3
x 4 9
y 3 4

8
17

Hint

Translated by ChatGPT 5