Математикийн үүднээс авч үзвэл Фибоначийн тоонуудын $F_{n}$ дараалал нь тодорхой давтамжтай холбоотой

$F_{1} = 1; F_{2} = 1; F_{n} = F_{n - 1} + F_{n - 2} (n > 2).$

Дзи Фибоначийн тоонуудад маш их дуртай. Өнөөдөр Дзи чамд $n$ бүхэл тоонуудаас бүрдсэн массив өгсөн: $a_{1}, a_{2}, ..., a_{n}$. Үүнээс гадна $m$ асуулгууд өгсөн ба асуулга бүр нь дараах хоёр төрлийн нэг байна:

1. "$1 l r$" хэлбэрийн асуулга. Асуулгын хариу нь $l ≤ i ≤ r$ байх $F_{i - l + 1}$-н $a_{i}$ элемент бүрийг нэмэх хэрэгтэй.
2. "$2 l r$" хэлбэрийн асуулга. Асуулгын хариу нь модуль $1000000009 (10^{9} + 9)$ утга байх ёстой.

Бүх асуулгад хариулахад нь Дзид тусал.

Оролт

Эхний мөр нь $n$, $m$ ($1 ≤ n, m ≤ 300000$) хоёр бүхэл тоог агуулна. Хоёр дахь мөр нь анхны $a$ массив болох $n$ бүхэл $a_{1}, a_{2}, ..., a_{n} (1 ≤ a_{i} ≤ 10^{9})$ тоонуудыг агуулна.

Дараа нь $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$.