У Сережи есть массив, состоящий из $n$ целых чисел $a_1, a_2, ..., a_n$. Сережа активный мальчик, поэтому сейчас он собирается выполнить $m$ операций. Каждая из этих операций будет иметь один из трех следующих видов: \begin{itemize} \item Сделать $v_i$-ый элемент массива равным $x_i$. Другими словами, выполнить присвоение $a_{v_i} = x_i$. \item Увеличить каждый элемент массива на $y_i$. Другими словами, выполнить $n$ присвоений $a_i = a_i + y_i~(1 \le i \le n)$. \item Выписать на листок $q_i$-ый элемент массива. То есть элемент $a_{q_i}$. \end{itemize} Помогите Сереже, выполните все его операции. \InputFile В первой строке записаны целые числа $n, m~(1 \le n, m \le 10^5)$. Во второй строке записаны $n$ целых чисел $a_1, a_2, ..., a_n~(1 \le a_i \le 10^9)$ --- исходный массив. Следующие $m$ строк описывают операции, $i$-ая строка описывает $i$-ую операцию. Первое число в $i$-ой строке --- целое число $t_i~(1 \le t_i \le 3)$, которое обозначает тип операции. \begin{itemize} \item Если $t_i = 1$, то далее следуют два целых числа $v_i$ и $x_i~(1 \le v_i \le n, 1 \le x_i \le 10^9)$. \item Если $t_i = 2$, то далее следует целое число $y_i~(1 \le y_i \le 10^4)$. \item Если $t_i = 3$, то далее следует целое число $q_i~(1 \le q_i \le n)$. \end{itemize} \OutputFile Для каждой операции третьего типа выведите значение $a_{q_i}$. Значения выводите в порядке следования соответствующих запросов во входных данных.