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>
using namespace std;
long long f[300010], Sum[300010], a[300010];
void init() {
  f[0] = 0;
  f[1] = f[2] = 1;
  for (int i = 3; i <= 300001; i++) f[i] = (f[i - 1] + f[i - 2]) % 1000000009;
  for (int i = 1; i <= 300001; i++) {
    Sum[i] = (f[i] + Sum[i - 1]) % 1000000009;
  }
}
struct tree {
  int l, r;
  long long f1, f2, sum;
} t[300010 << 2];
void pushup(int p) {
  t[p].sum = (t[(p << 1)].sum + t[((p << 1) | 1)].sum) % 1000000009;
}
void change(int p, long long f1, long long f2) {
  int len = t[p].r - t[p].l + 1;
  if (len == 1) {
    t[p].sum = (t[p].sum + f1) % 1000000009;
  } else if (len == 2) {
    t[p].sum = (t[p].sum + f1 + f2) % 1000000009;
  } else {
    long long tmp = (f1 * (Sum[len - 2] + 1) + f2 * Sum[len - 1]) % 1000000009;
    t[p].sum = (t[p].sum + tmp) % 1000000009;
  }
}
void pushdown(int p) {
  if (t[p].f1 || t[p].f2) {
    t[(p << 1)].f1 = (t[(p << 1)].f1 + t[p].f1) % 1000000009;
    t[(p << 1)].f2 = (t[(p << 1)].f2 + t[p].f2) % 1000000009;
    int len = t[(p << 1)].r - t[(p << 1)].l + 1;
    long long F1, F2;
    F1 = (f[len - 1] * t[p].f1 + f[len] * t[p].f2) % 1000000009;
    F2 = (f[len] * t[p].f1 + f[len + 1] * t[p].f2) % 1000000009;
    t[((p << 1) | 1)].f1 = (t[((p << 1) | 1)].f1 + F1) % 1000000009;
    t[((p << 1) | 1)].f2 = (t[((p << 1) | 1)].f2 + F2) % 1000000009;
    change((p << 1), t[p].f1, t[p].f2);
    change(((p << 1) | 1), F1, F2);
    t[p].f1 = t[p].f2 = 0;
  }
}
void build(int p, int l, int r) {
  t[p].l = l, t[p].r = r;
  t[p].sum = t[p].f1 = t[p].f2 = 0;
  if (l == r) {
    t[p].sum = a[r];
    return;
  }
  build((p << 1), l, ((t[p].l + t[p].r) >> 1));
  build(((p << 1) | 1), ((t[p].l + t[p].r) >> 1) + 1, r);
  pushup(p);
}
void modify(int p, int l, int r, int val) {
  if (t[p].l == l && t[p].r == r) {
    t[p].f1 = (t[p].f1 + f[val]) % 1000000009;
    t[p].f2 = (t[p].f2 + f[val + 1]) % 1000000009;
    change(p, f[val], f[val + 1]);
    return;
  }
  pushdown(p);
  if (l > ((t[p].l + t[p].r) >> 1))
    modify(((p << 1) | 1), l, r, val);
  else if (r <= ((t[p].l + t[p].r) >> 1))
    modify((p << 1), l, r, val);
  else {
    modify((p << 1), l, ((t[p].l + t[p].r) >> 1), val);
    modify(((p << 1) | 1), ((t[p].l + t[p].r) >> 1) + 1, r,
           val + ((t[p].l + t[p].r) >> 1) + 1 - l);
  }
  pushup(p);
}
long long query(int p, int l, int r) {
  if (t[p].l == l && t[p].r == r) {
    return t[p].sum;
  }
  pushdown(p);
  if (l > ((t[p].l + t[p].r) >> 1))
    return query(((p << 1) | 1), l, r);
  else if (r <= ((t[p].l + t[p].r) >> 1))
    return query((p << 1), l, r);
  else {
    return (query((p << 1), l, ((t[p].l + t[p].r) >> 1)) +
            query(((p << 1) | 1), ((t[p].l + t[p].r) >> 1) + 1, r)) %
           1000000009;
  }
}
int main() {
  init();
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) scanf("%I64d", &a[i]);
  build(1, 1, n);
  while (m--) {
    int typ, l, r;
    scanf("%d%d%d", &typ, &l, &r);
    if (typ == 1)
      modify(1, l, r, 1);
    else
      printf("%I64d\n", query(1, l, r));
  }
  return 0;
}
