Nhắc lại ~F_n~ là số fibonacci thứ ~n~ với ~F_1 = F_2 = 1~.

Cho mảng ~a~ có ~n~ phần tử và ~q~ truy vấn có một trong 2 dạng sau đây:

• 1 l r, cộng thêm giá trị ~F_{i - l + 1}~ với mỗi phần tử ~l \le i \le r~.
• 2 l r, in ra ~\sum_{i=l} ^{r} a_i~ modulo ~10^9+9~.

Input

• Dòng đầu tiên gồm 2 số ~1 \le n, q \le 300000~.
• Dòng tiếp theo gồm ~n~ số tự nhiên của mảng ~a~ (~1 \le a_i \le 10^9~).

Output

• In ra kết quả của mỗi truy vấn 2.

Sample Test

Input:

4 4
1 2 3 4
1 1 4
2 1 4
1 2 4
2 1 3

Output:

17
12