#include <bits/stdc++.h>
const int M = 3e5 + 10;
const int mod = 1e9 + 9;
void add(int &a, int b) {
  b %= mod;
  a += b;
  if (a < 0) a += mod;
  if (a > mod) a -= mod;
}
int f[M][2], sf[M][2];
struct nod {
  int f0, f1, sum;
  bool lz;
  void init() {
    f0 = f1 = sum = 0;
    lz = false;
  }
  void mark(int _f0, int _f1, int i) {
    lz = true;
    _f0 %= mod, _f1 %= mod;
    add(sum, 1ll * _f0 * sf[i][0] % mod + 1ll * _f1 * sf[i][1] % mod);
    add(f0, _f0);
    add(f1, _f1);
  }
};
struct Segtree {
  nod T[M << 2];
  void up(int o) { T[o].sum = (T[o << 1].sum + T[o << 1 | 1].sum) % mod; }
  void down(int o, int l, int r) {
    if (T[o].lz == false) return;
    int mid = l + r >> 1;
    T[o << 1].mark(T[o].f0, T[o].f1, mid - l + 1);
    T[o << 1 | 1].mark(1ll * f[mid + 2 - l][0] * T[o].f0 % mod +
                           1ll * f[mid + 2 - l][1] * T[o].f1 % mod,
                       1ll * f[mid + 3 - l][0] * T[o].f0 % mod +
                           1ll * f[mid + 3 - l][1] * T[o].f1 % mod,
                       r - mid);
    T[o].f0 = T[o].f1 = 0;
    T[o].lz = false;
  }
  void build(int o, int l, int r) {
    T[o].init();
    if (l == r) {
      scanf("%d", &T[o].sum);
      return;
    }
    int mid = l + r >> 1;
    build(o << 1, l, mid);
    build(o << 1 | 1, mid + 1, r);
    up(o);
  }
  void update(int o, int l, int r, int pl, int pr) {
    if (pl <= l && r <= pr) {
      T[o].mark(f[l - pl + 3][0], f[l - pl + 3][1], r - l + 1);
      return;
    }
    down(o, l, r);
    int mid = l + r >> 1;
    if (pl <= mid) update(o << 1, l, mid, pl, pr);
    if (pr > mid) update(o << 1 | 1, mid + 1, r, pl, pr);
    up(o);
  }
  int ask(int o, int l, int r, int pl, int pr) {
    if (pl <= l && r <= pr) {
      return T[o].sum;
    }
    down(o, l, r);
    int mid = l + r >> 1;
    int ret = 0;
    if (pl <= mid) add(ret, ask(o << 1, l, mid, pl, pr));
    if (pr > mid) add(ret, ask(o << 1 | 1, mid + 1, r, pl, pr));
    return ret;
  }
} seg;
void init() {
  f[1][0] = 1;
  f[2][1] = 1;
  for (int i = 3; i < M; i++) {
    add(f[i][0], f[i - 1][0]);
    add(f[i][0], f[i - 2][0]);
    add(f[i][1], f[i - 1][1]);
    add(f[i][1], f[i - 2][1]);
  }
  for (int i = 1; i < M; i++) {
    add(sf[i][0], sf[i - 1][0]);
    add(sf[i][0], f[i][0]);
    add(sf[i][1], sf[i - 1][1]);
    add(sf[i][1], f[i][1]);
  }
}
int main() {
  init();
  int n, m;
  scanf("%d%d", &n, &m);
  seg.build(1, 1, n);
  while (m--) {
    int op, l, r;
    scanf("%d%d%d", &op, &l, &r);
    if (op == 1)
      seg.update(1, 1, n, l, r);
    else
      printf("%d\n", seg.ask(1, 1, n, l, r));
  }
}

### Prompt

Create a solution in cpp for the following problem:

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.

### Response

```cpp
#include <bits/stdc++.h>
const int M = 3e5 + 10;
const int mod = 1e9 + 9;
void add(int &a, int b) {
  b %= mod;
  a += b;
  if (a < 0) a += mod;
  if (a > mod) a -= mod;
}
int f[M][2], sf[M][2];
struct nod {
  int f0, f1, sum;
  bool lz;
  void init() {
    f0 = f1 = sum = 0;
    lz = false;
  }
  void mark(int _f0, int _f1, int i) {
    lz = true;
    _f0 %= mod, _f1 %= mod;
    add(sum, 1ll * _f0 * sf[i][0] % mod + 1ll * _f1 * sf[i][1] % mod);
    add(f0, _f0);
    add(f1, _f1);
  }
};
struct Segtree {
  nod T[M << 2];
  void up(int o) { T[o].sum = (T[o << 1].sum + T[o << 1 | 1].sum) % mod; }
  void down(int o, int l, int r) {
    if (T[o].lz == false) return;
    int mid = l + r >> 1;
    T[o << 1].mark(T[o].f0, T[o].f1, mid - l + 1);
    T[o << 1 | 1].mark(1ll * f[mid + 2 - l][0] * T[o].f0 % mod +
                           1ll * f[mid + 2 - l][1] * T[o].f1 % mod,
                       1ll * f[mid + 3 - l][0] * T[o].f0 % mod +
                           1ll * f[mid + 3 - l][1] * T[o].f1 % mod,
                       r - mid);
    T[o].f0 = T[o].f1 = 0;
    T[o].lz = false;
  }
  void build(int o, int l, int r) {
    T[o].init();
    if (l == r) {
      scanf("%d", &T[o].sum);
      return;
    }
    int mid = l + r >> 1;
    build(o << 1, l, mid);
    build(o << 1 | 1, mid + 1, r);
    up(o);
  }
  void update(int o, int l, int r, int pl, int pr) {
    if (pl <= l && r <= pr) {
      T[o].mark(f[l - pl + 3][0], f[l - pl + 3][1], r - l + 1);
      return;
    }
    down(o, l, r);
    int mid = l + r >> 1;
    if (pl <= mid) update(o << 1, l, mid, pl, pr);
    if (pr > mid) update(o << 1 | 1, mid + 1, r, pl, pr);
    up(o);
  }
  int ask(int o, int l, int r, int pl, int pr) {
    if (pl <= l && r <= pr) {
      return T[o].sum;
    }
    down(o, l, r);
    int mid = l + r >> 1;
    int ret = 0;
    if (pl <= mid) add(ret, ask(o << 1, l, mid, pl, pr));
    if (pr > mid) add(ret, ask(o << 1 | 1, mid + 1, r, pl, pr));
    return ret;
  }
} seg;
void init() {
  f[1][0] = 1;
  f[2][1] = 1;
  for (int i = 3; i < M; i++) {
    add(f[i][0], f[i - 1][0]);
    add(f[i][0], f[i - 2][0]);
    add(f[i][1], f[i - 1][1]);
    add(f[i][1], f[i - 2][1]);
  }
  for (int i = 1; i < M; i++) {
    add(sf[i][0], sf[i - 1][0]);
    add(sf[i][0], f[i][0]);
    add(sf[i][1], sf[i - 1][1]);
    add(sf[i][1], f[i][1]);
  }
}
int main() {
  init();
  int n, m;
  scanf("%d%d", &n, &m);
  seg.build(1, 1, n);
  while (m--) {
    int op, l, r;
    scanf("%d%d%d", &op, &l, &r);
    if (op == 1)
      seg.update(1, 1, n, l, r);
    else
      printf("%d\n", seg.ask(1, 1, n, l, r));
  }
}

```