#include <bits/stdc++.h>
using namespace std;
const int maxn = 300110;
const int mod = 1e9 + 9;
int n, m;
int sumv[maxn * 4];
int f1[maxn * 4];
int f2[maxn * 4];
int num[maxn];
int sum[maxn];
int f[maxn];
int addv(int a, int b, int n) {
  return ((((long long)f[n + 1] * (long long)b) % mod +
           ((long long)f[n] * (long long)a) % mod) %
              mod +
          (mod - b) % mod) %
         mod;
}
int get(int a, int b, int n) {
  return ((long long)f[n - 1] * (long long)b +
          ((long long)f[n - 2] * (long long)a) % mod) %
         mod;
}
void maintain(int o, int l, int r) {
  int lc = o * 2, rc = lc + 1;
  sumv[o] = 0;
  if (r > l) sumv[o] = (sumv[lc] + sumv[rc]) % mod;
  sumv[o] =
      ((sumv[o] + ((long long)f[r - l + 2] * (long long)(f2[o])) % mod) % mod +
       ((((long long)f[r - l + 1] * (long long)(f1[o])) % mod +
         (mod - f2[o]) % mod) %
        mod)) %
      mod;
}
void update(int o, int l, int r, int yl, int yr) {
  int lc = o * 2, rc = lc + 1;
  int m = l + (r - l) / 2;
  if (yl <= l && yr >= r) {
    f1[o] = (f1[o] + f[l - yl + 1]) % mod;
    f2[o] = (f2[o] + f[l - yl + 2]) % mod;
  } else {
    if (yl <= m) update(lc, l, m, yl, yr);
    if (yr > m) update(rc, m + 1, r, yl, yr);
  }
  maintain(o, l, r);
}
int _sum;
void query(int o, int l, int r, int ql, int qr, int add_f1, int add_f2) {
  int lc = o * 2, rc = lc + 1;
  int m = l + (r - l) / 2;
  if (ql <= l && qr >= r) {
    _sum = ((_sum + sumv[o]) % mod + addv(add_f1, add_f2, r - l + 1)) % mod;
  } else {
    if (ql <= m)
      query(lc, l, m, ql, qr, (add_f1 + f1[o]) % mod, (add_f2 + f2[o]) % mod);
    if (qr > m)
      query(rc, m + 1, r, ql, qr,
            get((add_f1 + f1[o]) % mod, (add_f2 + f2[o]) % mod, m + 2 - l),
            get((add_f1 + f1[o]) % mod, (add_f2 + f2[o]) % mod, m + 3 - l));
  }
}
int main() {
  memset(sumv, 0, sizeof(sumv));
  memset(f1, 0, sizeof(f1));
  memset(f2, 0, sizeof(f2));
  f[0] = 0;
  f[1] = 1;
  f[2] = 1;
  for (int i = 3; i < maxn; ++i) f[i] = (f[i - 1] + f[i - 2]) % mod;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i) scanf("%d", &num[i]);
  sum[0] = 0;
  for (int i = 1; i <= n; ++i) sum[i] = (sum[i - 1] + num[i]) % mod;
  int x, y, z;
  for (int i = 0; i < m; ++i) {
    scanf("%d%d%d", &x, &y, &z);
    if (x == 1)
      update(1, 1, n, y, z);
    else {
      _sum = 0;
      query(1, 1, n, y, z, 0, 0);
      _sum = (_sum + (sum[z] - sum[y - 1] + mod) % mod) % mod;
      printf("%d\n", _sum);
    }
  }
  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 int maxn = 300110;
const int mod = 1e9 + 9;
int n, m;
int sumv[maxn * 4];
int f1[maxn * 4];
int f2[maxn * 4];
int num[maxn];
int sum[maxn];
int f[maxn];
int addv(int a, int b, int n) {
  return ((((long long)f[n + 1] * (long long)b) % mod +
           ((long long)f[n] * (long long)a) % mod) %
              mod +
          (mod - b) % mod) %
         mod;
}
int get(int a, int b, int n) {
  return ((long long)f[n - 1] * (long long)b +
          ((long long)f[n - 2] * (long long)a) % mod) %
         mod;
}
void maintain(int o, int l, int r) {
  int lc = o * 2, rc = lc + 1;
  sumv[o] = 0;
  if (r > l) sumv[o] = (sumv[lc] + sumv[rc]) % mod;
  sumv[o] =
      ((sumv[o] + ((long long)f[r - l + 2] * (long long)(f2[o])) % mod) % mod +
       ((((long long)f[r - l + 1] * (long long)(f1[o])) % mod +
         (mod - f2[o]) % mod) %
        mod)) %
      mod;
}
void update(int o, int l, int r, int yl, int yr) {
  int lc = o * 2, rc = lc + 1;
  int m = l + (r - l) / 2;
  if (yl <= l && yr >= r) {
    f1[o] = (f1[o] + f[l - yl + 1]) % mod;
    f2[o] = (f2[o] + f[l - yl + 2]) % mod;
  } else {
    if (yl <= m) update(lc, l, m, yl, yr);
    if (yr > m) update(rc, m + 1, r, yl, yr);
  }
  maintain(o, l, r);
}
int _sum;
void query(int o, int l, int r, int ql, int qr, int add_f1, int add_f2) {
  int lc = o * 2, rc = lc + 1;
  int m = l + (r - l) / 2;
  if (ql <= l && qr >= r) {
    _sum = ((_sum + sumv[o]) % mod + addv(add_f1, add_f2, r - l + 1)) % mod;
  } else {
    if (ql <= m)
      query(lc, l, m, ql, qr, (add_f1 + f1[o]) % mod, (add_f2 + f2[o]) % mod);
    if (qr > m)
      query(rc, m + 1, r, ql, qr,
            get((add_f1 + f1[o]) % mod, (add_f2 + f2[o]) % mod, m + 2 - l),
            get((add_f1 + f1[o]) % mod, (add_f2 + f2[o]) % mod, m + 3 - l));
  }
}
int main() {
  memset(sumv, 0, sizeof(sumv));
  memset(f1, 0, sizeof(f1));
  memset(f2, 0, sizeof(f2));
  f[0] = 0;
  f[1] = 1;
  f[2] = 1;
  for (int i = 3; i < maxn; ++i) f[i] = (f[i - 1] + f[i - 2]) % mod;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i) scanf("%d", &num[i]);
  sum[0] = 0;
  for (int i = 1; i <= n; ++i) sum[i] = (sum[i - 1] + num[i]) % mod;
  int x, y, z;
  for (int i = 0; i < m; ++i) {
    scanf("%d%d%d", &x, &y, &z);
    if (x == 1)
      update(1, 1, n, y, z);
    else {
      _sum = 0;
      query(1, 1, n, y, z, 0, 0);
      _sum = (_sum + (sum[z] - sum[y - 1] + mod) % mod) % mod;
      printf("%d\n", _sum);
    }
  }
  return 0;
}

```