C. DZY любит числа Фибоначчи
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

F1 = 1; F2 = 1; Fn = Fn - 1 + Fn - 2 (n > 2).

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

  1. Формат запроса: «1 l r». В ответ на запрос надо добавить Fi - l + 1 к каждому элементу ai, где l ≤ i ≤ r.
  2. Формат запроса: «2 l r». В ответ на запрос надо вывести значение по модулю 1000000009 (109 + 9).

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

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

В первой строке записано два целых числа n и m (1 ≤ n, m ≤ 300000). Во второй строке записано n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 109) — изначальный массив a.

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

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

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

Примеры
Входные данные
4 4
1 2 3 4
1 1 4
2 1 4
1 2 4
2 1 3
Выходные данные
17
12
Примечание

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

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

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

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