In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the recurrence relation 

F1 = 1; F2 = 1; Fn = Fn - 1 + Fn - 2 (n > 2).

DZY loves Fibonacci numbers very much. Today DZY gives you an array consisting of n integers: a1, a2, ..., an. Moreover, there are m queries, each query has one of the two types:

  1. Format of the query "1 l r". In reply to the query, you need to add Fi - l + 1 to each element ai, where l ≤ i ≤ r. 
  2. Format of the query "2 l r". In reply to the query you should output the value of <image> modulo 1000000009 (109 + 9). 



Help DZY reply to all the queries.

Input

The first line of the input contains two integers n and m (1 ≤ n, m ≤ 300000). The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 109) — initial array a.

Then, m lines follow. A single line describes a single query in the format given in the statement. It is guaranteed that for each query inequality 1 ≤ l ≤ r ≤ n holds.

Output

For each query of the second type, print the value of the sum on a single line.

Examples

Input

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


Output

17
12

Note

After the first query, a = [2, 3, 5, 7].

For the second query, sum = 2 + 3 + 5 + 7 = 17.

After the third query, a = [2, 4, 6, 9].

For the fourth query, sum = 2 + 4 + 6 = 12.
#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
const int N = 300009;
const int inf = 0x3f3f3f3f;
const long long oo = 0x3f3f3f3f3f3f3f3fll;
const int mod = 1e9 + 9;
pair<long long, long long> f[N];
long long sum[N];
int a[N];
struct Seg {
  int l, r;
  long long f1, f2;
  long long sum;
} tree[N * 4];
void PushDown(int idx) {
  int lsz = tree[idx << 1].r - tree[idx << 1].l + 1;
  int rsz = tree[idx << 1 | 1].r - tree[idx << 1 | 1].l + 1;
  long long &f1 = tree[idx].f1;
  long long &f2 = tree[idx].f2;
  tree[idx << 1].f1 = (tree[idx << 1].f1 + f1) % mod;
  tree[idx << 1].f2 = (tree[idx << 1].f2 + f2) % mod;
  tree[idx << 1].sum +=
      f1 * sum[lsz] % mod + f2 * sum[lsz + 1] % mod - f2 + mod;
  tree[idx << 1].sum %= mod;
  tree[idx << 1 | 1].f1 = (tree[idx << 1 | 1].f1 + f1 * f[lsz + 1].first % mod +
                           f2 * f[lsz + 2].first % mod) %
                          mod;
  tree[idx << 1 | 1].f2 =
      (tree[idx << 1 | 1].f2 + f1 * f[lsz + 1].second % mod +
       f2 * f[lsz + 2].second % mod) %
      mod;
  tree[idx << 1 | 1].sum += f1 * (sum[lsz + rsz] - sum[lsz] + mod) % mod +
                            f2 * (sum[lsz + rsz + 1] - sum[lsz + 1]) % mod +
                            mod;
  tree[idx << 1 | 1].sum %= mod;
  f1 = f2 = 0;
  return;
}
void BTree(int l, int r, int idx) {
  tree[idx].l = l;
  tree[idx].r = r;
  tree[idx].f1 = 0;
  tree[idx].f2 = 0;
  tree[idx].sum = a[l];
  if (l == r) return;
  int mid = (l + r) >> 1;
  BTree(l, mid, idx << 1);
  BTree(mid + 1, r, idx << 1 | 1);
  tree[idx].sum = (tree[idx << 1].sum + tree[idx << 1 | 1].sum) % mod;
}
void insert(int l, int r, long long x, long long y, int idx) {
  if (tree[idx].l == l && tree[idx].r == r) {
    int sz = r - l + 1;
    long long k = sum[sz] * x % mod + sum[sz + 1] * y % mod - y + mod;
    k %= mod;
    (tree[idx].sum += k) %= mod;
    tree[idx].f1 = (tree[idx].f1 + x) % mod;
    tree[idx].f2 = (tree[idx].f2 + y) % mod;
    return;
  }
  PushDown(idx);
  int mid = (tree[idx].l + tree[idx].r) >> 1;
  if (r <= mid)
    insert(l, r, x, y, idx << 1);
  else if (l > mid)
    insert(l, r, x, y, idx << 1 | 1);
  else {
    insert(l, mid, x, y, idx << 1);
    int lsz = mid - l + 1;
    long long tx =
        (f[lsz + 1].first * x % mod + f[lsz + 2].first * y % mod) % mod;
    long long ty =
        (f[lsz + 1].second * x % mod + f[lsz + 2].second * y % mod) % mod;
    insert(mid + 1, r, tx, ty, idx << 1 | 1);
  }
  tree[idx].sum = (tree[idx << 1].sum + tree[idx << 1 | 1].sum) % mod;
}
long long query(int l, int r, int idx) {
  if (tree[idx].l == l && tree[idx].r == r) {
    return tree[idx].sum;
  }
  PushDown(idx);
  int mid = (tree[idx].l + tree[idx].r) >> 1;
  long long ret = 0;
  if (r <= mid)
    ret += query(l, r, idx << 1);
  else if (l > mid)
    ret += query(l, r, idx << 1 | 1);
  else
    ret += query(l, mid, idx << 1), ret += query(mid + 1, r, idx << 1 | 1);
  ret %= mod;
  tree[idx].sum = (tree[idx << 1].sum + tree[idx << 1 | 1].sum) % mod;
  return ret;
}
int main() {
  f[1] = make_pair(1, 0);
  f[2] = make_pair(0, 1);
  for (int i = 3; i < N; i++)
    f[i] = make_pair((f[i - 1].first + f[i - 2].first) % mod,
                     (f[i - 1].second + f[i - 2].second) % mod);
  sum[1] = 1;
  for (int i = 2; i < N; i++)
    sum[i] = (sum[i - 1] + f[i].first + f[i].second) % mod;
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  BTree(1, n, 1);
  for (int i = 0; i < m; i++) {
    int t, l, r;
    scanf("%d%d%d", &t, &l, &r);
    if (t == 1) {
      insert(l, r, 1, 0, 1);
    } else {
      cout << query(l, r, 1) << endl;
    }
  }
  return 0;
}
