题目描述

给定长度为 $\red N$ 的数列 $\red A$，然后输入 $\red M$ 行操作指令。

第一类指令形如“C l r d”，表示把数列中第 $\red{l\sim r}$ 个数都加 $\red d$。

第二类指令形如“Q X”，表示询问数列中第 $\red x$ 个数的值。

对于每个询问，输出一个整数表示答案。

输入格式

第一行包含两个整数 $\red N$ 和 $\red M$。

第二行包含 $\red N$ 个整数 $\red{A[i]}$。

接下来 $\red M$ 行表示 $\red M$条指令，每条指令的格式如题目描述所示。

输出格式

对于每个询问，输出一个整数表示答案。

每个答案占一行。

样例

输入样例

10 5
1 2 3 4 5 6 7 8 9 10
Q 4
Q 1
Q 2
C 1 6 3
Q 2

输出样例

4
1
2
5

提示

$\red{1\le N,M\le 10^5}$,

$\red{|d|\le 10000}$,

$\red{|A[i]|\le 1000000000}$