У Сережи есть массив, состоящий из n целых чисел a1,a2,...,an. Сережа активный мальчик, поэтому сейчас он собирается выполнить m операций. Каждая из этих операций будет иметь один из трех следующих видов:
Сделать vi-ый элемент массива равным xi. Другими словами, выполнить присвоение avi=xi.
Увеличить каждый элемент массива на yi. Другими словами, выполнить n присвоений ai=ai+yi (1≤i≤n).
Выписать на листок 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. Значения выводите в порядке следования соответствующих запросов во входных данных.