Description

实验室有一排 $n$ 个格子，编号为 $1$ 到 $n$。第 $i$ 个格子一开始有 $a_i$ 单位灰尘。

扫地机器人很努力，但它只会沿着直线工作。现在有 $q$ 次操作，操作分为三种：

1. $\texttt{1 l r x}$：机器人对区间 $[l,r]$ 施法，使其中每个格子的灰尘量都增加 $x$。注意 $x$ 可以为负数，表示扫掉灰尘；
2. $\texttt{2 i}$：询问第 $i$ 个格子的灰尘量；
3. $\texttt{3 l r}$：询问区间 $[l,r]$ 中所有格子的灰尘量之和。

请你回答所有询问。

Format

Input

第一行两个整数 $n,q(1 \le n,q \le 2 \times 10^5)$。

第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n(-10^6 \le a_i,x \le 10^6)$。

接下来 $q$ 行，每行表示一次操作，格式为以下三种之一：

$\texttt{1 l r x}$

$\texttt{2 i}$

$\texttt{3 l r}$

其中 $1 \le l \le r \le n,1 \le i \le n$

Output

对于每次 $2$ 或 $3$ 操作，输出一行一个整数，表示答案。

Samples

5 6
1 2 3 4 5
2 3
1 2 4 10
3 1 5
1 1 5 -1
2 4
3 2 3

3
45
13
23

Note

样例说明：

初始数组为：$[1,2,3,4,5]$ 第一次询问位置 $3$，答案为 $3$。

区间 $[2,4]$ 加 $10$ 后，数组变为：$[1,12,13,14,5]$ 区间 $[1,5]$ 的和为 $45$。

全区间加 $-1$ 后，数组变为：$[0,11,12,13,4]$ 位置 $4$ 的值为 $13$，区间 $[2,3]$ 的和为 $23$。