eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

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

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

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

У Сережи есть массив, состоящий из 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}. Значения выводите в порядке следования соответствующих запросов во входных данных.

Приклад

Вхідні дані #1
5 6
1 2 3 4 5
3 1
2 10
1 1 5
3 1
2 10
3 1
Вихідні дані #1
1
5
15
Вхідні дані #2
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
2
9
11
20
30
40
39