题目描述

解决了助教给出的第一个问题后，小陶对数据结构的兴趣被点燃了，他央求助教给他出了第二个问题：

给出一个有 $n$ 个元素的序列 $a$（$n\le 200 000$），进行 $m$（$m\le 10 000$）次操作，操作有两种类型：

• $1\ x\ y\ c$：给 $a_x,a_{x+1},\cdots ,a_{y−1},a_y$ 都加上 $c$。
• $2\ x$：输出 $a_x$ 的值。

输入格式

第一行两个整数 $n,m$。

第二行 $n$ 个整数表示序列中元素的大小。

接下来 $m$ 行，每行 $2$ 个或 $4$ 个整数，表示一个操作，格式见题面。

输出格式

对于每个操作 $2$，输出对应的结果。

样例输入输出

5 5
1 5 4 2 3
1 2 4 2
2 3
1 1 5 -1
1 3 5 7
2 4

6
10

说明

对于 $10 \%$ 的数据， $n \leq 10, m \leq 20$；

对于 $30 \%$ 的数据： $n \leq 4000, m \leq 5000$ ；

对于 $60 \%$ 的数据: $n \leq 20000, m \leq 30000$ ；

对于 $100 \%$ 的数据: $ 2 \leq n \leq 100000,1 \leq m \leq 200000,1 \leq x \leq y \leq n, 0 \leq c \leq 10^{9} $ 。