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.