Sereja and Array#853
Sergey has an array consisting of integers a_1, a_2, \dots, a_n.
Sergey is an active boy, so he is going to perform operations. Each operation is of one of the following three types:
Assign the value x_i to the v_i-th element of the array. In other words, perform a_{v_i} = x_i.
Increase every element of the array by y_i. That is, perform assignments a_i = a_i + y_i \ (1 \le i \le n).
Write down the value of the q_i-th element of the array, i.e., a_{q_i}.
Your task is to help Sergey perform all his operations.
The first line contains two integers and (1 \le n, m \le 10^5).
The second line contains integers a_1, a_2, \dots, a_n (1 \le a_i \le 10^9) — the initial array.
The next lines describe the operations. The -th line describes the -th operation. The first number in the line is an integer t_i~(1 \le t_i \le 3) denoting the type of the operation.
If t_i = 1, then two integers v_i and x_i (1 \le v_i \le n, \ 1 \le x_i \le 10^9) follow.
If t_i = 2, then one integer y_i~(1 \le y_i \le 10^4) follows.
If t_i = 3, then one integer q_i~(1 \le q_i \le n) follows.
For each operation of the third type, print the value of a_{q_i} in the order in which the corresponding queries appear in the input.
Example 1
Example 2