#include <bits/stdc++.h>
using namespace std;
int N, M;
int A[300013];
int f[300013], fp[300013];
int st[(1 << 20)], lazy[(1 << 20)][2];
inline int add(int x, int y) { return (x + y) % 1000000009; }
inline int sub(int x, int y) { return (x - y + 1000000009) % 1000000009; }
inline int mul(int x, int y) { return (long long)x * y % 1000000009; }
void push(int lo, int hi, int node) {
  int len = hi - lo + 1;
  int d = (lo + hi) / 2 + 1 - lo;
  if (lazy[node][0]) {
    st[node] = add(st[node], mul(lazy[node][0], fp[len + 1]));
    if (lo != hi) {
      lazy[2 * node + 1][0] = add(lazy[2 * node + 1][0], lazy[node][0]);
      lazy[2 * node + 2][0] =
          add(lazy[2 * node + 2][0], mul(lazy[node][0], f[d + 1]));
      lazy[2 * node + 2][1] =
          add(lazy[2 * node + 2][1], mul(lazy[node][0], f[d]));
    }
    lazy[node][0] = 0;
  }
  if (lazy[node][1]) {
    st[node] = add(st[node], mul(lazy[node][1], fp[len]));
    if (lo != hi) {
      lazy[2 * node + 1][1] = add(lazy[2 * node + 1][1], lazy[node][1]);
      lazy[2 * node + 2][0] =
          add(lazy[2 * node + 2][0], mul(lazy[node][1], f[d]));
      lazy[2 * node + 2][1] =
          add(lazy[2 * node + 2][1], mul(lazy[node][1], f[d - 1]));
    }
    lazy[node][1] = 0;
  }
}
void build_tree(int lo = 0, int hi = -1, int node = 0) {
  if (hi == -1) hi = N - 1;
  if (lo == hi) {
    st[node] = A[lo];
    return;
  }
  int mid = (lo + hi) / 2;
  build_tree(lo, mid, 2 * node + 1);
  build_tree(mid + 1, hi, 2 * node + 2);
  st[node] = add(st[2 * node + 1], st[2 * node + 2]);
}
void update_range(int s, int e, int x, int lo = 0, int hi = -1, int node = 0) {
  if (hi == -1) hi = N - 1;
  push(lo, hi, node);
  if (lo > e || hi < s) return;
  if (s <= lo && hi <= e) {
    lazy[node][0] = mul(x, f[lo - s + 1]);
    lazy[node][1] = mul(x, f[lo - s]);
    push(lo, hi, node);
    return;
  }
  int mid = (lo + hi) / 2;
  update_range(s, e, x, lo, mid, 2 * node + 1);
  update_range(s, e, x, mid + 1, hi, 2 * node + 2);
  st[node] = add(st[2 * node + 1], st[2 * node + 2]);
}
int query(int s, int e, int lo = 0, int hi = -1, int node = 0) {
  if (hi == -1) hi = N - 1;
  push(lo, hi, node);
  if (lo > e || hi < s) return 0;
  if (s <= lo && hi <= e) return st[node];
  int mid = (lo + hi) / 2;
  return add(query(s, e, lo, mid, 2 * node + 1),
             query(s, e, mid + 1, hi, 2 * node + 2));
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin >> N >> M;
  f[1] = 1;
  for (int i = 2; i <= N + 2; i++) {
    f[i] = add(f[i - 1], f[i - 2]);
    fp[i] = add(fp[i - 1], f[i - 1]);
  }
  for (int i = 0; i < N; i++) cin >> A[i];
  build_tree();
  while (M--) {
    int t, l, r;
    cin >> t >> l >> r;
    --l, --r;
    if (t == 1)
      update_range(l, r, 1);
    else
      cout << query(l, r) << '\n';
  }
  cout.flush();
  return 0;
}

### Prompt

Your task is to create 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;
int N, M;
int A[300013];
int f[300013], fp[300013];
int st[(1 << 20)], lazy[(1 << 20)][2];
inline int add(int x, int y) { return (x + y) % 1000000009; }
inline int sub(int x, int y) { return (x - y + 1000000009) % 1000000009; }
inline int mul(int x, int y) { return (long long)x * y % 1000000009; }
void push(int lo, int hi, int node) {
  int len = hi - lo + 1;
  int d = (lo + hi) / 2 + 1 - lo;
  if (lazy[node][0]) {
    st[node] = add(st[node], mul(lazy[node][0], fp[len + 1]));
    if (lo != hi) {
      lazy[2 * node + 1][0] = add(lazy[2 * node + 1][0], lazy[node][0]);
      lazy[2 * node + 2][0] =
          add(lazy[2 * node + 2][0], mul(lazy[node][0], f[d + 1]));
      lazy[2 * node + 2][1] =
          add(lazy[2 * node + 2][1], mul(lazy[node][0], f[d]));
    }
    lazy[node][0] = 0;
  }
  if (lazy[node][1]) {
    st[node] = add(st[node], mul(lazy[node][1], fp[len]));
    if (lo != hi) {
      lazy[2 * node + 1][1] = add(lazy[2 * node + 1][1], lazy[node][1]);
      lazy[2 * node + 2][0] =
          add(lazy[2 * node + 2][0], mul(lazy[node][1], f[d]));
      lazy[2 * node + 2][1] =
          add(lazy[2 * node + 2][1], mul(lazy[node][1], f[d - 1]));
    }
    lazy[node][1] = 0;
  }
}
void build_tree(int lo = 0, int hi = -1, int node = 0) {
  if (hi == -1) hi = N - 1;
  if (lo == hi) {
    st[node] = A[lo];
    return;
  }
  int mid = (lo + hi) / 2;
  build_tree(lo, mid, 2 * node + 1);
  build_tree(mid + 1, hi, 2 * node + 2);
  st[node] = add(st[2 * node + 1], st[2 * node + 2]);
}
void update_range(int s, int e, int x, int lo = 0, int hi = -1, int node = 0) {
  if (hi == -1) hi = N - 1;
  push(lo, hi, node);
  if (lo > e || hi < s) return;
  if (s <= lo && hi <= e) {
    lazy[node][0] = mul(x, f[lo - s + 1]);
    lazy[node][1] = mul(x, f[lo - s]);
    push(lo, hi, node);
    return;
  }
  int mid = (lo + hi) / 2;
  update_range(s, e, x, lo, mid, 2 * node + 1);
  update_range(s, e, x, mid + 1, hi, 2 * node + 2);
  st[node] = add(st[2 * node + 1], st[2 * node + 2]);
}
int query(int s, int e, int lo = 0, int hi = -1, int node = 0) {
  if (hi == -1) hi = N - 1;
  push(lo, hi, node);
  if (lo > e || hi < s) return 0;
  if (s <= lo && hi <= e) return st[node];
  int mid = (lo + hi) / 2;
  return add(query(s, e, lo, mid, 2 * node + 1),
             query(s, e, mid + 1, hi, 2 * node + 2));
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin >> N >> M;
  f[1] = 1;
  for (int i = 2; i <= N + 2; i++) {
    f[i] = add(f[i - 1], f[i - 2]);
    fp[i] = add(fp[i - 1], f[i - 1]);
  }
  for (int i = 0; i < N; i++) cin >> A[i];
  build_tree();
  while (M--) {
    int t, l, r;
    cin >> t >> l >> r;
    --l, --r;
    if (t == 1)
      update_range(l, r, 1);
    else
      cout << query(l, r) << '\n';
  }
  cout.flush();
  return 0;
}

```