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;
const int MOD = 1e9 + 9;
const int sr5 = 616991993;
int power(int x, int n) {
  int r = 1;
  for (; n; x = x * (long long)x % MOD, n >>= 1)
    if (n & 1) r = r * (long long)x % MOD;
  return r;
}
int inv(int x) { return power(x, MOD - 2); }
int fix(int x) { return x < 0 ? x + MOD : x; }
void add(int &x, int y) { x = (x + y) % MOD; }
int mul(int x, int y) { return x * (long long)y % MOD; }
int r5 = inv(sr5);
int xx = (1 + sr5) * (long long)inv(2) % MOD;
int yy = (1 - sr5) * (long long)inv(2) % MOD;
struct SegTree {
  int Q, L, R, a, iQ;
  int q[312345];
  struct node {
    int s, a0;
  } v[312345 * 4];
  void init(int _Q) {
    Q = _Q;
    q[0] = 1;
    iQ = inv(Q - 1);
    for (int i = 1; i < 312345; ++i) q[i] = mul(q[i - 1], Q);
  }
  inline int calc(int x, int l, int r) {
    int res = v[x].s;
    if (v[x].a0) add(res, mul(mul(v[x].a0, q[r - l + 1] - 1), iQ));
    return res;
  }
  inline void rep0(int x, int l, int m, int r) {
    if (v[x].a0) {
      add(v[x * 2].a0, v[x].a0);
      add(v[x * 2 + 1].a0, v[x].a0 * (long long)q[m + 1 - l] % MOD);
      v[x].a0 = 0;
    }
  }
  inline void rep1(int x, int l, int m, int r) {
    v[x].s = calc(x * 2, l, m);
    add(v[x].s, calc(x * 2 + 1, m + 1, r));
  }
  void update(int x, int l, int r) {
    if (l > R || r < L) return;
    if (L <= l && r <= R) {
      add(v[x].a0, mul(a, q[l - L]));
      return;
    }
    int m = (l + r) / 2;
    rep0(x, l, m, r);
    update(x * 2, l, m);
    update(x * 2 + 1, m + 1, r);
    rep1(x, l, m, r);
  }
  int query(int x, int l, int r) {
    if (l > R || r < L) return 0;
    if (L <= l && r <= R) return calc(x, l, r);
    int m = (l + r) / 2;
    rep0(x, l, m, r);
    int res = query(x * 2, l, m);
    add(res, query(x * 2 + 1, m + 1, r));
    rep1(x, l, m, r);
    return res;
  }
} sx, sy;
int fn(int n) { return r5 * (long long)(power(xx, n) - power(yy, n)) % MOD; }
int s[312345];
int main() {
  sx.init(xx);
  sy.init(yy);
  sx.a = mul(r5, xx);
  sy.a = mul(r5, yy);
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 0; i < int(n); i++) {
    scanf("%d", s + i + 1);
    add(s[i + 1], s[i]);
  }
  while (m--) {
    int t, l, r;
    scanf("%d%d%d", &t, &l, &r);
    sx.L = sy.L = l;
    sx.R = sy.R = r;
    if (t == 1) {
      sx.update(1, 1, n);
      sy.update(1, 1, n);
    } else {
      assert(t == 2);
      int res = (s[r] - s[l - 1]) % MOD;
      add(res, sx.query(1, 1, n));
      add(res, -sy.query(1, 1, n));
      printf("%d\n", fix(res));
    }
  }
}
