Сережа и массив

Очень простая

Ограничение по времени выполнения 1 секунда

Ограничение по использованию памяти 128 мегабайт

У Сережи есть массив, состоящий из $n$ целых чисел $a_{1}, a_{2}, ..., a_{n}$ . Сережа активный мальчик, поэтому сейчас он собирается выполнить $m$ операций. Каждая из этих операций будет иметь один из трех следующих видов:

Сделать $v_{i}$ -ый элемент массива равным $x_{i}$ . Другими словами, выполнить присвоение $a_{v_{i}} = x_{i}$ .
Увеличить каждый элемент массива на $y_{i}$ . Другими словами, выполнить $n$ присвоений $a_{i} = a_{i} + y_{i} (1 \leq i \leq n)$ .
Выписать на листок $q_{i}$ -ый элемент массива. То есть элемент $a_{q_{i}}$ .

Помогите Сереже, выполните все его операции.

Входные данные

В первой строке записаны целые числа $n, m (1 \leq n, m \leq 1 0^{5})$ . Во второй строке записаны $n$ целых чисел $a_{1}, a_{2}, ..., a_{n} (1 \leq a_{i} \leq 1 0^{9})$ — исходный массив.

Следующие $m$ строк описывают операции, $i$ -ая строка описывает $i$ -ую операцию. Первое число в $i$ -ой строке — целое число $t_{i} (1 \leq t_{i} \leq 3)$ , которое обозначает тип операции.

Если $t_{i} = 1$ , то далее следуют два целых числа $v_{i}$ и $x_{i} (1 \leq v_{i} \leq n, 1 \leq x_{i} \leq 1 0^{9})$ .
Если $t_{i} = 2$ , то далее следует целое число $y_{i} (1 \leq y_{i} \leq 1 0^{4})$ .
Если $t_{i} = 3$ , то далее следует целое число $q_{i} (1 \leq q_{i} \leq n)$ .

Выходные данные

Для каждой операции третьего типа выведите значение $a_{q_{i}}$ . Значения выводите в порядке следования соответствующих запросов во входных данных.

Примеры

Ввод #1

Ответ #1

Ввод #2

Ответ #2

Отправки 2K

Коэффициент принятия 30 %