K. Easy Homework
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

After data structure class in Sinoey's dream, Awson gave Sinoey a simple segment operation problem as his homework. Sinoey has $$$5$$$ hours to solve it before he wakes up.

There is a set $$$S$$$ containing all integers. Initially, the value of each element in $$$S$$$ is $$$0$$$. In this problem, Sinoey is given an integer sequence $$$a$$$ of length $$$n$$$, the $$$i$$$-th element of which is $$$a_i$$$, and he has to do the following two types of operations:

  • R l r w. Let $$$T=\{a_i\mid l\le i\le r\}$$$. For each element $$$x$$$ in $$$T$$$, add $$$S_x$$$ by $$$w$$$. $$$(1\le l\le r\le n,\ |w| \lt 2^{31})$$$
  • A x. Output the value of $$$x$$$ in $$$S$$$. $$$(|x| \lt 2^{31})$$$
Input

The first line contains two integers $$$n\ (1\le n\le 10^5)$$$ and $$$q\ (1\le q\le 10^5)$$$, the length of sequence and the number of operations respectively.

The next line contains $$$n$$$ integers representing the sequence. For each element $$$a_i$$$ in the sequence, $$$|a_i| \lt 2^{31}$$$ is guaranteed.

Each of the next $$$q$$$ lines indicates an operation. The formats and constraints are introduced above.

Output

For each query, print the answer in a line.

Scoring

The problem contains several subtasks. You can get the corresponding score only if you have passed all test cases in a subtask.

  • Subtask 1 ($$$20$$$ points): $$$n\le 100$$$.
  • Subtask 2 ($$$80$$$ points): no additional constraints.
Example
Input
4 5
1 2 1 3
R 1 3 1
A 1
R 2 4 1
A 1
A 3
Output
1
2
1
Note

The interval in the first operation contains two different elements: $$$1$$$ and $$$2$$$, so $$$S_1$$$ and $$$S_2$$$ will increase by one after the first operation.