Задача J. (20081225) Динамический массив

Автор:Жюри зимних сборов 2009   Ограничение времени:30 сек
Входной файл:dynarray.in   Ограничение памяти:512 Мб
Выходной файл:dynarray.out  
Максимальный балл:100  

Условие

Требуется реализовать структуру данных, которая представляет из себя динамический массив, поддерживающий следующие операции:

Элементы массива нумеруются с единицы.

Формат входного файла

В первой строке находятся два натуральных числа n и m — начальное количество элементов в массиве и количество операций (1 ≤ n ≤ 200 000, 1 ≤ m ≤ 200 000). Во второй строке находится n целых чисел a1, a2, , an  — элементы исходного массива (0 ≤ ai ≤ 106). Следующие m строк содержат описания операций в формате "1 u p" (u ≥ 1, u не превосходит текущего размера массива, 0 ≤ p ≤ 106), "2 u p" (u ≥ 0, u не превосходит текущего размера массива, 0 ≤ p ≤ 106) или "3 u v p" (1 ≤ u ≤ v, v не превосходит текущего размера массива, 0 ≤ p ≤ 106).

Формат выходного файла

В выходном файле должны находиться ответы на запросы  — по одному в строке.

Примеры тестов

Входной файл (dynarray.in) Выходной файл (dynarray.out)
1
5 5
1 3 5 4 2
3 2 4 4
1 3 3
3 2 4 4
2 2 10
3 2 4 4
2
3
2

0.073s 0.021s 13