Сережа и массив
Сережа и массив
У Сережи есть массив, состоящий из 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 \le i \le n).
Выписать на листок q_i-ый элемент массива. То есть элемент a_{q_i}.
Помогите Сереже, выполните все его операции.
Вхідні дані
В первой строке записаны целые числа 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), которое обозначает тип операции.
Если t_i = 1, то далее следуют два целых числа v_i и x_i~(1 \le v_i \le n, 1 \le x_i \le 10^9).
Если t_i = 2, то далее следует целое число y_i~(1 \le y_i \le 10^4).
Если t_i = 3, то далее следует целое число q_i~(1 \le q_i \le n).
Вихідні дані
Для каждой операции третьего типа выведите значение a_{q_i}. Значения выводите в порядке следования соответствующих запросов во входных данных.
Приклад
5 6 1 2 3 4 5 3 1 2 10 1 1 5 3 1 2 10 3 1
1 5 15
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