К своим трем годам Умный Бобер в совершенстве овладел всеми арифметическими операциями, а от своего учителя по математике одаренный ученик получил следующее домашнее задание на лето:
Дана последовательность целых чисел a1, a2, ..., an. Необходимо последовательно произвести над ней m операций следующего вида:
Этим летом Умный Бобер решил отправиться в тур по великим озерам Канады, потому просит Вас помочь ему в решении данной задачи.
Первая строка содержит два целых числа n и m (1 ≤ n, m ≤ 2·105) — количество чисел в последовательности и количество операций соответственно. Вторая строка содержит n целых чисел a1, a2, ..., an (0 ≤ ai ≤ 105). Далее идет m строк, каждая из которых описывает операцию. Каждый строка начинается с целого числа ti (1 ≤ ti ≤ 3) — тип операции:
Ограничения на входные данные для получения 30 баллов (подзадача E1):
Ограничения на входные данные для получения 70 баллов (подзадачи E1+E2):
Ограничения на входные данные для получения 100 баллов (подзадачи E1+E2+E3):
Для каждого запроса второго типа выведите вычисленную сумму по модулю 1000000000 (109).
5 5 1 3 1 2 4 2 1 4 2 1 5 2 2 4 1 3 10 2 1 5
12 32 8 50
5 4 1 3 1 2 4 3 1 4 1 2 2 4 1 2 10 2 1 5
12 45
3000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач