CF315B.Sereja and Array

Sereja has got an array, consisting of n integers, _a_1, _a_2, ..., a__n. Sereja is an active boy, so he is now going to complete m operations. Each operation will have one of the three forms:

1. Make v__i-th array element equal to x__i. In other words, perform the assignment a__v__i = x__i.
2. Increase each array element by y__i. In other words, perform n assignments a__i = a__i + y__i (1 ≤ i ≤ n).
3. Take a piece of paper and write out the q__i-th array element. That is, the element a__q__i.

Help Sereja, complete all his operations.

谢列亚得到了一个由 $n$ 个整数组成的数组：$a_1, a_2, \dots, a_n$。谢列亚是个活跃的男孩，因此他现在要执行 $m$ 个操作。每个操作有以下三种形式之一：

1. 将第 $v_i$ 个数组元素赋值为 $x_i$。即执行赋值操作：$a_{v_i} = x_i$。
2. 将数组中每个元素增加 $y_i$。即执行 $n$ 次赋值操作：$a_i = a_i + y_i$（其中 $1 \le i \le n$）。
3. 在纸上写下第 $q_i$ 个数组元素。即输出元素 $a_{q_i}$。

请帮助谢列亚完成所有这些操作。

The first line contains integers n, m (1 ≤ n, m ≤ 105). The second line contains n space-separated integers _a_1, _a_2, ..., a__n (1 ≤ a__i ≤ 109) — the original array.

Next m lines describe operations, the i-th line describes the i-th operation. The first number in the i-th line is integer t__i (1 ≤ t__i ≤ 3) that represents the operation type. If t__i = 1, then it is followed by two integers v__i and x__i, (1 ≤ v__i ≤ n, 1 ≤ x__i ≤ 109). If t__i = 2, then it is followed by integer y__i (1 ≤ y__i ≤ 104). And if t__i = 3, then it is followed by integer q__i (1 ≤ q__i ≤ n).

第一行包含两个整数 $n$、$m$（$1 \leq n, m \leq 10^5$）。第二行包含 $n$ 个用空格分隔的整数 $a_1, a_2, ..., a_n$（$1 \leq a_i \leq 10^9$）——原始数组。

接下来 $m$ 行描述操作，其中第 $i$ 行描述第 $i$ 个操作。第 $i$ 行的第一个数是整数 $t_i$（$1 \leq t_i \leq 3$），表示操作类型。若 $t_i = 1$，则其后跟两个整数 $v_i$ 和 $x_i$（$1 \leq v_i \leq n$, $1 \leq x_i \leq 10^9$）；若 $t_i = 2$，则其后跟一个整数 $y_i$（$1 \leq y_i \leq 10^4$）；若 $t_i = 3$，则其后跟一个整数 $q_i$（$1 \leq q_i \leq n$）。

For each third type operation print value a__q__i. Print the values in the order, in which the corresponding queries follow in the input.

对于每个第三类操作，输出值 $a_{q_i}$。请按照输入中对应查询出现的顺序输出这些值。