#include <bits/stdc++.h>
using namespace std;
const int M = 3e5 + 10;
const int mod = (int)1e9 + 9;
int n, m;
int a[M];
int fib[M][2];
int sumfib[M][2];
void add(int &a, int b) {
  a += b;
  if (a < 0) a += mod;
  if (a >= mod) a -= mod;
}
struct Node {
  int f[2];
  int sum;
  bool mk;
  void Init() { f[0] = f[1] = sum = mk = 0; }
  void mark(int *_f, int n) {
    mk = true;
    add(sum,
        (1ll * _f[0] * sumfib[n][0] % mod + 1ll * _f[1] * sumfib[n][1] % mod) %
            mod);
    add(f[0], _f[0]);
    add(f[1], _f[1]);
  }
} T[M << 2];
int getfib(long long f0, long long f1, int n) {
  return (f0 * fib[n][0] + f1 * fib[n][1]) % mod;
}
struct Segtree {
  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].mk == false) return;
    int mid = l + r >> 1;
    T[o << 1].mark(T[o].f, mid - l + 1);
    int _f[2] = {getfib(T[o].f[0], T[o].f[1], mid - l + 2),
                 getfib(T[o].f[0], T[o].f[1], mid - l + 3)};
    T[o << 1 | 1].mark(_f, r - mid);
    T[o].f[0] = T[o].f[1] = 0;
    T[o].mk = 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) {
      int _f[2] = {getfib(1, 1, l - pl + 1), getfib(1, 1, l - pl + 2)};
      T[o].mark(_f, 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;
  }
} sgt;
int main() {
  fib[1][0] = 1, fib[2][1] = 1;
  for (int i = 3; i < M; ++i) {
    fib[i][0] = (1ll * fib[i - 1][0] + fib[i - 2][0]) % mod;
    fib[i][1] = (1ll * fib[i - 1][1] + fib[i - 2][1]) % mod;
  }
  for (int i = 1; i < M; ++i) {
    add(sumfib[i][0], fib[i][0]);
    add(sumfib[i][0], sumfib[i - 1][0]);
    add(sumfib[i][1], fib[i][1]);
    add(sumfib[i][1], sumfib[i - 1][1]);
  }
  scanf("%d%d", &n, &m);
  sgt.build(1, 1, n);
  int op, l, r;
  while (m--) {
    scanf("%d%d%d", &op, &l, &r);
    if (op == 2)
      printf("%d\n", sgt.ask(1, 1, n, l, r));
    else {
      sgt.update(1, 1, n, l, r);
    }
  }
}

### Prompt

Please formulate a CPP solution to 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>
using namespace std;
const int M = 3e5 + 10;
const int mod = (int)1e9 + 9;
int n, m;
int a[M];
int fib[M][2];
int sumfib[M][2];
void add(int &a, int b) {
  a += b;
  if (a < 0) a += mod;
  if (a >= mod) a -= mod;
}
struct Node {
  int f[2];
  int sum;
  bool mk;
  void Init() { f[0] = f[1] = sum = mk = 0; }
  void mark(int *_f, int n) {
    mk = true;
    add(sum,
        (1ll * _f[0] * sumfib[n][0] % mod + 1ll * _f[1] * sumfib[n][1] % mod) %
            mod);
    add(f[0], _f[0]);
    add(f[1], _f[1]);
  }
} T[M << 2];
int getfib(long long f0, long long f1, int n) {
  return (f0 * fib[n][0] + f1 * fib[n][1]) % mod;
}
struct Segtree {
  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].mk == false) return;
    int mid = l + r >> 1;
    T[o << 1].mark(T[o].f, mid - l + 1);
    int _f[2] = {getfib(T[o].f[0], T[o].f[1], mid - l + 2),
                 getfib(T[o].f[0], T[o].f[1], mid - l + 3)};
    T[o << 1 | 1].mark(_f, r - mid);
    T[o].f[0] = T[o].f[1] = 0;
    T[o].mk = 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) {
      int _f[2] = {getfib(1, 1, l - pl + 1), getfib(1, 1, l - pl + 2)};
      T[o].mark(_f, 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;
  }
} sgt;
int main() {
  fib[1][0] = 1, fib[2][1] = 1;
  for (int i = 3; i < M; ++i) {
    fib[i][0] = (1ll * fib[i - 1][0] + fib[i - 2][0]) % mod;
    fib[i][1] = (1ll * fib[i - 1][1] + fib[i - 2][1]) % mod;
  }
  for (int i = 1; i < M; ++i) {
    add(sumfib[i][0], fib[i][0]);
    add(sumfib[i][0], sumfib[i - 1][0]);
    add(sumfib[i][1], fib[i][1]);
    add(sumfib[i][1], sumfib[i - 1][1]);
  }
  scanf("%d%d", &n, &m);
  sgt.build(1, 1, n);
  int op, l, r;
  while (m--) {
    scanf("%d%d%d", &op, &l, &r);
    if (op == 2)
      printf("%d\n", sgt.ask(1, 1, n, l, r));
    else {
      sgt.update(1, 1, n, l, r);
    }
  }
}

```