DZY yêu số Fibonacci (DZY Loves Fibonacci Numbers)

Nguồn: Codeforces

Phiên bản: Phước Hưng OJ Extended

Đề bài

Mỗi update 1 l r cộng dãy $F_1,F_2,\ldots,F_{r-l+1}$ vào đoạn. Query 2 l r hỏi tổng đoạn modulo $10^9+9$.

Input

Dòng đầu chứa $n,m$. Dòng thứ hai chứa mảng ban đầu $a_1,a_2,\ldots,a_n$. Mỗi trong $m$ dòng sau là 1 l r hoặc 2 l r đúng như mô tả đề bài.

Output

Mỗi truy vấn loại 2 in tổng đoạn modulo $10^9+9$.

Subtask

• Subtask 1 (20%): $n$ và số thao tác không vượt 30; các điều kiện còn lại giữ như đề đầy đủ.

• Subtask 2 (30%): $n$ và số thao tác không vượt 3000; các điều kiện còn lại giữ như đề đầy đủ.

• Subtask 3 (50%): toàn bộ giới hạn:

• $1\le n,m\le3\cdot10^5$

• $1\le a_i\le10^9$

Ví dụ

Input

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

Output

17
12

Giải thích

Sau update đầu, mảng là [2,3,5,7], tổng bằng 17. Sau update tiếp theo trên [2,4], mảng là [2,4,6,9], nên tổng [1,3] bằng 12.