DZY Loves Fibonacci Numbers

Source: Codeforces

Version: Phuoc Hung OJ Extended

Problem Statement

Type 1 adds a Fibonacci prefix to a range; type 2 asks for the range sum modulo $10^9+9$.

Input

The first line contains $n,m$, followed by the initial array. Each of the next $m$ lines is 1 l r or 2 l r as defined above.

Output

For each type-2 query print the range sum modulo $10^9+9$.

Subtasks

• Subtask 1 (20%): size and operation count at most 30; all other validity conditions are unchanged.

• Subtask 2 (30%): size and operation count at most 3000; all other validity conditions are unchanged.

• Subtask 3 (50%): full constraints:

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

• $1\le a_i\le10^9$

Examples

Input

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

Output

17
12

Explanation

After the first update the array is [2,3,5,7], with sum 17. The next update on [2,4] gives [2,4,6,9], so the sum of [1,3] is 12.