Problems
Sereja and Array
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:
\begin{itemize}
\item Make $v_i$-th array element equal to $x_i$. In other words, perform the assignment $a_{v_i} = x_i$.
\item Increase each array element by $y_i$. In other words, perform $n$ assignments $a_i = a_i + y_i~(1 \le i \le n)$.
\item Take a piece of paper and write out the $q_i$-th array element. That is, the element $a_{q_i}$.
\end{itemize}
Help Sereja, complete all his operations.
\InputFile
The first line contains integers $n, m~(1 \le n, m \le 10^5)$. The second line contains $n$ integers $a_1, a_2, ..., a_n~(1 \le a_i \le 10^9)$ --- 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 \le t_i \le 3)$, that represents the operation type.
\begin{itemize}
\item If $t_i = 1$, then it is followed by two integers $v_i$ and $x_i~(1 \le v_i \le n, 1 \le x_i \le 10^9)$.
\item If $t_i = 2$, then it is followed by integer $y_i~(1 \le y_i \le 10^4)$.
\item If $t_i = 3$, then it is followed by integer $q_i~(1 \le q_i \le n)$.
\end{itemize}
\OutputFile
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.
Input example #1
5 6 1 2 3 4 5 3 1 2 10 1 1 5 3 1 2 10 3 1
Output example #1
1 5 15
Input example #2
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
Output example #2
2 9 11 20 30 40 39