#include <bits/stdc++.h>
using namespace std;
const long long mod = 1000000009ll;
struct node_type {
  long long l, r, val[2], sum, child[2];
} node[1000001];
long long n, m, o, l, r, tot = 1, a[300001], x[300001][2], y[300001][2];
void build_tree(int root) {
  if (node[root].l == node[root].r) return;
  long long mid = node[root].l + node[root].r >> 1;
  node[++tot].l = node[root].l, node[tot].r = mid, node[root].child[0] = tot,
  build_tree(tot);
  node[++tot].l = mid + 1, node[tot].r = node[root].r,
  node[root].child[1] = tot, build_tree(tot);
}
void push_down(int root) {
  if (node[root].l == node[root].r ||
      node[root].val[0] == 0 && node[root].val[1] == 0)
    return;
  if (node[node[root].child[0]].l == node[node[root].child[0]].r)
    (node[node[root].child[0]].sum += node[root].val[0]) %= mod;
  else {
    (node[node[root].child[0]].val[0] += node[root].val[0]) %= mod,
        (node[node[root].child[0]].val[1] += node[root].val[1]) %= mod;
    (node[node[root].child[0]].sum +=
     y[node[node[root].child[0]].r - node[node[root].child[0]].l + 1][0] *
     node[root].val[0] % mod) %= mod;
    (node[node[root].child[0]].sum +=
     y[node[node[root].child[0]].r - node[node[root].child[0]].l + 1][1] *
     node[root].val[1] % mod) %= mod;
  }
  long long p =
      (x[node[node[root].child[0]].r - node[node[root].child[0]].l + 2][0] *
           node[root].val[0] % mod +
       x[node[node[root].child[0]].r - node[node[root].child[0]].l + 2][1] *
           node[root].val[1] % mod) %
      mod;
  long long q =
      (x[node[node[root].child[0]].r - node[node[root].child[0]].l + 3][0] *
           node[root].val[0] % mod +
       x[node[node[root].child[0]].r - node[node[root].child[0]].l + 3][1] *
           node[root].val[1] % mod) %
      mod;
  if (node[node[root].child[1]].l == node[node[root].child[1]].r)
    (node[node[root].child[1]].sum += p) %= mod;
  else {
    (node[node[root].child[1]].val[0] += p) %= mod,
        (node[node[root].child[1]].val[1] += q) %= mod;
    (node[node[root].child[1]].sum +=
     y[node[node[root].child[1]].r - node[node[root].child[1]].l + 1][0] * p %
     mod) %= mod;
    (node[node[root].child[1]].sum +=
     y[node[node[root].child[1]].r - node[node[root].child[1]].l + 1][1] * q %
     mod) %= mod;
  }
  node[root].val[0] = node[root].val[1] = 0;
}
void push_up(int root) {
  if (node[root].l == node[root].r) return;
  node[root].sum =
      (node[node[root].child[0]].sum + node[node[root].child[1]].sum) % mod;
}
void insert_line(int root, int l, int r, int val) {
  if (node[root].r < l || node[root].l > r) return;
  if (node[root].l >= l && node[root].r <= r) {
    if (node[root].l == node[root].r)
      (node[root].sum += x[val][0] + x[val][1]) %= mod;
    else {
      (node[root].val[0] += x[val][0] + x[val][1]) %= mod;
      (node[root].val[1] += x[val + 1][0] + x[val + 1][1]) %= mod;
      (node[root].sum += y[node[root].r - node[root].l + 1][0] *
                         (x[val][0] + x[val][1]) % mod) %= mod;
      (node[root].sum += y[node[root].r - node[root].l + 1][1] *
                         (x[val + 1][0] + x[val + 1][1]) % mod) %= mod;
    }
    return;
  }
  push_down(root);
  insert_line(node[root].child[0], l, r, val);
  insert_line(node[root].child[1], l, r,
              max(1ll, val + node[node[root].child[1]].l -
                           max((long long)l, node[node[root].child[0]].l)));
  push_up(root);
}
long long get_sum(int root, int l, int r) {
  if (node[root].r < l || node[root].l > r) return 0;
  if (node[root].l >= l && node[root].r <= r) return node[root].sum % mod;
  long long ret;
  push_down(root);
  ret = (get_sum(node[root].child[0], l, r) +
         get_sum(node[root].child[1], l, r)) %
        mod;
  push_up(root);
  return ret;
}
int main() {
  scanf("%lld%lld", &n, &m);
  x[1][0] = x[2][1] = y[1][0] = y[2][0] = y[2][1] = 1;
  for (int i = 3; i <= n; ++i) {
    x[i][0] = (x[i - 1][0] + x[i - 2][0]) % mod;
    x[i][1] = (x[i - 1][1] + x[i - 2][1]) % mod;
    y[i][0] = (y[i - 1][0] + x[i][0]) % mod;
    y[i][1] = (y[i - 1][1] + x[i][1]) % mod;
  }
  node[1].l = 1, node[1].r = n, build_tree(1);
  for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]), (a[i] += a[i - 1]) %= mod;
  while (m--) {
    scanf("%lld%lld%lld", &o, &l, &r);
    if (o == 1)
      insert_line(1, l, r, 1);
    else
      printf("%lld\n",
             ((get_sum(1, l, r) + a[r] - a[l - 1]) % mod + mod) % mod);
  }
  return 0;
}

### Prompt

In Cpp, your task is to solve 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 long long mod = 1000000009ll;
struct node_type {
  long long l, r, val[2], sum, child[2];
} node[1000001];
long long n, m, o, l, r, tot = 1, a[300001], x[300001][2], y[300001][2];
void build_tree(int root) {
  if (node[root].l == node[root].r) return;
  long long mid = node[root].l + node[root].r >> 1;
  node[++tot].l = node[root].l, node[tot].r = mid, node[root].child[0] = tot,
  build_tree(tot);
  node[++tot].l = mid + 1, node[tot].r = node[root].r,
  node[root].child[1] = tot, build_tree(tot);
}
void push_down(int root) {
  if (node[root].l == node[root].r ||
      node[root].val[0] == 0 && node[root].val[1] == 0)
    return;
  if (node[node[root].child[0]].l == node[node[root].child[0]].r)
    (node[node[root].child[0]].sum += node[root].val[0]) %= mod;
  else {
    (node[node[root].child[0]].val[0] += node[root].val[0]) %= mod,
        (node[node[root].child[0]].val[1] += node[root].val[1]) %= mod;
    (node[node[root].child[0]].sum +=
     y[node[node[root].child[0]].r - node[node[root].child[0]].l + 1][0] *
     node[root].val[0] % mod) %= mod;
    (node[node[root].child[0]].sum +=
     y[node[node[root].child[0]].r - node[node[root].child[0]].l + 1][1] *
     node[root].val[1] % mod) %= mod;
  }
  long long p =
      (x[node[node[root].child[0]].r - node[node[root].child[0]].l + 2][0] *
           node[root].val[0] % mod +
       x[node[node[root].child[0]].r - node[node[root].child[0]].l + 2][1] *
           node[root].val[1] % mod) %
      mod;
  long long q =
      (x[node[node[root].child[0]].r - node[node[root].child[0]].l + 3][0] *
           node[root].val[0] % mod +
       x[node[node[root].child[0]].r - node[node[root].child[0]].l + 3][1] *
           node[root].val[1] % mod) %
      mod;
  if (node[node[root].child[1]].l == node[node[root].child[1]].r)
    (node[node[root].child[1]].sum += p) %= mod;
  else {
    (node[node[root].child[1]].val[0] += p) %= mod,
        (node[node[root].child[1]].val[1] += q) %= mod;
    (node[node[root].child[1]].sum +=
     y[node[node[root].child[1]].r - node[node[root].child[1]].l + 1][0] * p %
     mod) %= mod;
    (node[node[root].child[1]].sum +=
     y[node[node[root].child[1]].r - node[node[root].child[1]].l + 1][1] * q %
     mod) %= mod;
  }
  node[root].val[0] = node[root].val[1] = 0;
}
void push_up(int root) {
  if (node[root].l == node[root].r) return;
  node[root].sum =
      (node[node[root].child[0]].sum + node[node[root].child[1]].sum) % mod;
}
void insert_line(int root, int l, int r, int val) {
  if (node[root].r < l || node[root].l > r) return;
  if (node[root].l >= l && node[root].r <= r) {
    if (node[root].l == node[root].r)
      (node[root].sum += x[val][0] + x[val][1]) %= mod;
    else {
      (node[root].val[0] += x[val][0] + x[val][1]) %= mod;
      (node[root].val[1] += x[val + 1][0] + x[val + 1][1]) %= mod;
      (node[root].sum += y[node[root].r - node[root].l + 1][0] *
                         (x[val][0] + x[val][1]) % mod) %= mod;
      (node[root].sum += y[node[root].r - node[root].l + 1][1] *
                         (x[val + 1][0] + x[val + 1][1]) % mod) %= mod;
    }
    return;
  }
  push_down(root);
  insert_line(node[root].child[0], l, r, val);
  insert_line(node[root].child[1], l, r,
              max(1ll, val + node[node[root].child[1]].l -
                           max((long long)l, node[node[root].child[0]].l)));
  push_up(root);
}
long long get_sum(int root, int l, int r) {
  if (node[root].r < l || node[root].l > r) return 0;
  if (node[root].l >= l && node[root].r <= r) return node[root].sum % mod;
  long long ret;
  push_down(root);
  ret = (get_sum(node[root].child[0], l, r) +
         get_sum(node[root].child[1], l, r)) %
        mod;
  push_up(root);
  return ret;
}
int main() {
  scanf("%lld%lld", &n, &m);
  x[1][0] = x[2][1] = y[1][0] = y[2][0] = y[2][1] = 1;
  for (int i = 3; i <= n; ++i) {
    x[i][0] = (x[i - 1][0] + x[i - 2][0]) % mod;
    x[i][1] = (x[i - 1][1] + x[i - 2][1]) % mod;
    y[i][0] = (y[i - 1][0] + x[i][0]) % mod;
    y[i][1] = (y[i - 1][1] + x[i][1]) % mod;
  }
  node[1].l = 1, node[1].r = n, build_tree(1);
  for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]), (a[i] += a[i - 1]) %= mod;
  while (m--) {
    scanf("%lld%lld%lld", &o, &l, &r);
    if (o == 1)
      insert_line(1, l, r, 1);
    else
      printf("%lld\n",
             ((get_sum(1, l, r) + a[r] - a[l - 1]) % mod + mod) % mod);
  }
  return 0;
}

```