Type: Default 2000ms 512MiB

扫地机器人不会拐弯

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

实验室有一排 nn 个格子,编号为 11 到 nn。第 ii 个格子一开始有 aia_i 单位灰尘。

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

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

请你回答所有询问。

Format

Input

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

第二行 nn 个整数 a1,a2,…,an(−106≤ai,x≤106)a_1,a_2,\ldots,a_n(-10^6 \le a_i,x \le 10^6)。

接下来 qq 行,每行表示一次操作,格式为以下三种之一:

1 l r x\texttt{1 l r x}

2 i\texttt{2 i}

3 l r\texttt{3 l r}

其中 1≤l≤r≤n,1≤i≤n1 \le l \le r \le n,1 \le i \le n

Output

对于每次 22 或 33 操作,输出一行一个整数,表示答案。

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][1,2,3,4,5] 第一次询问位置 33,答案为 33。

区间 [2,4][2,4] 加 1010 后,数组变为:[1,12,13,14,5][1,12,13,14,5] 区间 [1,5][1,5] 的和为 4545。

全区间加 −1-1 后,数组变为:[0,11,12,13,4][0,11,12,13,4] 位置 44 的值为 1313,区间 [2,3][2,3] 的和为 2323。