Олимпиадный тренинг

Задача . C. DZY любит числа Фибоначчи

Задача

Темы: математика Структуры данных теория чисел *2400

Как известно, ряд чисел Фибоначчи F_n определяется рекуррентным соотношением

F₁ = 1; F₂ = 1; F_n = F_n - 1 + F_n - 2 (n > 2).

DZY очень любит числа Фибоначчи. Сегодня он дал вам массив, состоящий из n целых чисел: a₁, a₂, ..., a_n. Кроме того, он дал вам m запросов. Каждый запрос имеет один из двух следующих типов:

Формат запроса: «1 l r». В ответ на запрос надо добавить F_{i - l + 1} к каждому элементу a_i, где l ≤ i ≤ r.
Формат запроса: «2 l r». В ответ на запрос надо вывести значение $\text{[math]}$ по модулю 1000000009 (10⁹ + 9).

Помогите DZY ответить на все запросы.

Входные данные

В первой строке записано два целых числа n и m (1 ≤ n, m ≤ 300000). Во второй строке записано n целых чисел a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁹) — изначальный массив a.

Затем следует m строк. Одна строка описывает один запрос в формате, указанном в условии. Гарантируется, что для каждого запроса выполняется неравенство 1 ≤ l ≤ r ≤ n.

Выходные данные

Для каждого запроса второго типа выведите значение суммы в отдельной строке.

Примечание

После первого запроса a = [2, 3, 5, 7].

Для второго запроса sum = 2 + 3 + 5 + 7 = 17.

После третьего запроса a = [2, 4, 6, 9].

Для четвертого запроса sum = 2 + 4 + 6 = 12.