| ABBYY Cup 3.0 |
|---|
| Закончено |
К своим трем годам Умный Бобер в совершенстве овладел всеми арифметическими операциями, а от своего учителя по математике одаренный ученик получил следующее домашнее задание на лето:
Дана последовательность целых чисел a1, a2, ..., an. Необходимо последовательно произвести над ней m операций следующего вида:
- Для заданных чисел xi и vi присвоить элементу axi значение vi.
- Для заданных чисел li и ri необходимо вычислить сумму
, где f0 = f1 = 1 и при i ≥ 2: fi = fi - 1 + fi - 2. - Для тройки чисел li ri di необходимо для всех x (li ≤ x ≤ ri) увеличить значение ax на di.
Этим летом Умный Бобер решил отправиться в тур по великим озерам Канады, потому просит Вас помочь ему в решении данной задачи.
Первая строка содержит два целых числа n и m (1 ≤ n, m ≤ 2·105) — количество чисел в последовательности и количество операций соответственно. Вторая строка содержит n целых чисел a1, a2, ..., an (0 ≤ ai ≤ 105). Далее идет m строк, каждая из которых описывает операцию. Каждый строка начинается с целого числа ti (1 ≤ ti ≤ 3) — тип операции:
- если ti = 1, то далее идет два целых числа xi vi (1 ≤ xi ≤ n, 0 ≤ vi ≤ 105);
- если ti = 2, то далее идет два целых числа li ri (1 ≤ li ≤ ri ≤ n);
- если ti = 3, то далее идет три целых числа li ri di (1 ≤ li ≤ ri ≤ n, 0 ≤ di ≤ 105).
Ограничения на входные данные для получения 30 баллов (подзадача E1):
- Гарантируется, что n не превышает 100, m не превышает 10000 и не будет запросов 3-го типа.
Ограничения на входные данные для получения 70 баллов (подзадачи E1+E2):
- Гарантируется, что будут запросы только 1-го и 2-го типа.
Ограничения на входные данные для получения 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
