B. Сережа и массив
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Сережи есть массив, состоящий из n целых чисел, a1, a2, ..., an. Сережа — активный мальчик, поэтому сейчас он собирается выполнить m операций. Каждая из этих операций будет иметь один из трех следующих видов:

  1. Сделать vi-ый элемент массива равным xi. Другими словами, выполнить присвоение avi = xi.
  2. Увеличить каждый элемент массива на yi. Другими словами, выполнить n присвоений ai = ai + yi (1 ≤ i ≤ n).
  3. Выписать на листок qi-ый элемент массива. То есть элемент aqi.

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

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

В первой строке записаны целые числа n, m (1 ≤ n, m ≤ 105). Во второй строке записаны n целых чисел через пробел a1, a2, ..., an (1 ≤ ai ≤ 109) — исходный массив.

Следующие m строк описывают операции, i-ая строка описывает i-ую операцию. Первое число в i-ой строке — целое число ti (1 ≤ ti ≤ 3), которое обозначает тип операции. Если ti = 1, то далее следуют два целых числа vi и xi, (1 ≤ vi ≤ n, 1 ≤ xi ≤ 109). Если ti = 2, то далее следует целое число yi (1 ≤ yi ≤ 104). Если же ti = 3, то далее следует целое число qi (1 ≤ qi ≤ n).

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

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

Примеры
Входные данные
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
Выходные данные
2
9
11
20
30
40
39