У Сережи есть массив, состоящий из n целых чисел, a1, a2, ..., an. Сережа — активный мальчик, поэтому сейчас он собирается выполнить m операций. Каждая из этих операций будет иметь один из трех следующих видов:
Помогите Сереже, выполните все его операции.
В первой строке записаны целые числа 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
1000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач