Sereja and Array

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

Sereja has got an array, consisting of n integers, a₁, a₂, ..., 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:

Make v_i-th array element equal to x_i. In other words, perform the assignment a_{v_i} = x_i.
Increase each array element by y_i. In other words, perform n assignments a_i = a_i + y_i(1 ≤ i ≤ n).
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.

输入描述:

The first line contains integers n, m(1 ≤ n, m ≤ 10⁵). The second line contains n space-separated integers a₁, a₂, ..., a_n(1 ≤ a_i ≤ 10⁹) — 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 ≤ 10⁹). If t_i = 2, then it is followed by integer y_i(1 ≤ y_i ≤ 10⁴). And if t_i = 3, then it is followed by integer q_i(1 ≤ q_i ≤ 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.

示例1

输入

复制

10 11
1 2 3 4 5 6 7 8 9 10
3 2
3 9
2 10
3 1
3 10
1 1 10
2 10
2 10
3 1
3 10
3 9

输出

复制