DZY và dãy Fibonacci

Cho dãy Fibonacci được định nghĩa $F_1=1$, $F_2=1$, $F_n=F_{n-1}+F_{n-2}$ với mọi $n>2$.

Cho một mảng gồm $n$ số nguyên $a_1,a_2,\dots ,a_n$ và $m$ truy vấn. Mỗi truy vấn thuộc một trong hai loại:

1. Cập nhật "1 l r": với mỗi $i$ thỏa $l\le i\le r$, cộng thêm $F_{i-l+1}$ vào $a_i$.
2. Truy vấn "2 l r": in ra giá trị $(a_l+a_{l+1}+\cdots +a_r)mod({10}^9+9)$.

Hãy xử lý tất cả các truy vấn theo thứ tự.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên $n$ và $m$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.
• $m$ dòng tiếp theo, mỗi dòng mô tả một truy vấn theo định dạng nêu trên. Đảm bảo $1\le l\le r\le n$.

Dữ liệu ra

Với mỗi truy vấn loại 2, in ra một dòng chứa giá trị tổng modulo ${10}^9+9$.

Ràng buộc

• $1\le n,m\le 3·{10}^5$
• $1\le a_i\le {10}^9$

Ví dụ