В день детей ребенок пришел домой к Пиксу и все перевернул вверх дном. Пикс на него разозлился. В бардаке потерялось много всего, включая любимую последовательность Пикса.
К счастью, Пикс помнит, как можно восстановить последовательность. Сначала нужно завести целочисленный массив a[1], a[2], ..., a[n]. Затем нужно выполнить последовательно m операций. Операции могут быть такими:
Сможете ли вы помочь Пиксу выполнить заданную последовательность операций?
В первой строке записано два целых числа: n, m (1 ≤ n, m ≤ 105). Во второй строке записано n целых чисел через пробел: a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ 109) — начальное значение элементов массива.
Каждая из следующих m строк начинается с целого числа type .
Для каждой операции 1, выведите значение, которое должен записать Пикс. Обратите внимание, что ответ может не помещаться в 32-битное целое число.
Рассмотрим первый тестовый пример:
5 5 1 2 3 4 5 2 3 5 4 3 3 5 1 2 5 2 1 3 3 1 1 3
8 5
10 10 6 9 6 7 6 1 10 10 9 5 1 3 9 2 7 10 9 2 5 10 8 1 4 7 3 3 7 2 7 9 9 1 2 4 1 6 6 1 5 9 3 1 10
49 15 23 1 9
4000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач