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.
#include <bits/stdc++.h>
using namespace std;
FILE *debug;
void setIO(string file = "sample") {}
void closeIO() {}
template <class T>
void read(T &x) {
  char tmp = 0;
  T flag = 1, ret = 0;
  while (tmp != '-' && !isdigit(tmp)) tmp = getchar();
  if (tmp == '-') flag = -1, tmp = getchar();
  while (isdigit(tmp)) ret *= 10, ret += tmp - '0', tmp = getchar();
  x = flag * ret;
}
long long getint() {
  long long ret;
  read<long long>(ret);
  return ret;
}
void endline() { fprintf(debug, "\n"); }
inline int getID(int l, int r) { return l + r | l != r; }
const long long modd = 1000000009LL;
struct ma {
  long long a[3][3];
};
ma mut(ma x, ma y) {
  ma re;
  memset(re.a, 0, sizeof(re.a));
  for (int i = 0; i < 3; ++i)
    for (int j = 0; j < 3; ++j)
      for (int k = 0; k < 3; ++k)
        re.a[i][j] = (re.a[i][j] + x.a[i][k] * y.a[k][j]) % modd;
  return re;
}
void addmod(long long &x, long long y, long long z) {
  y %= modd;
  z %= modd;
  x = y + z;
  while (x >= modd) x -= modd;
  while (x < 0) x += modd;
}
ma a[300005];
int n, m, y[300005];
long long sum[300005 * 4], c1[300005 * 4], c2[300005 * 4], l[300005 * 4],
    r[300005 * 4];
void upd(int _t) { addmod(sum[_t], sum[_t * 2], sum[_t * 2 + 1]); }
long long f(long long p, long long q, int k) {
  long long re;
  addmod(re, a[k - 1].a[0][0] * p, a[k - 1].a[0][1] * q);
  return re;
}
long long s(long long p, long long q, int k) {
  long long re;
  addmod(re, a[k].a[2][0] * p, a[k].a[2][1] * q);
  return re;
}
void pd(int o) {
  long long d1, d2;
  if (c1[o] || c2[o]) {
    addmod(c1[o * 2], c1[o * 2], c1[o]);
    addmod(c2[o * 2], c2[o * 2], c2[o]);
    addmod(sum[o * 2], sum[o * 2], s(c1[o], c2[o], r[o * 2] - l[o * 2] + 1));
    d1 = f(c1[o], c2[o], r[o * 2] - l[o * 2] + 2);
    d2 = f(c1[o], c2[o], r[o * 2] - l[o * 2] + 3);
    addmod(c1[o * 2 + 1], c1[o * 2 + 1], d1);
    addmod(c2[o * 2 + 1], c2[o * 2 + 1], d2);
    addmod(sum[o * 2 + 1], sum[o * 2 + 1],
           s(d1, d2, r[o * 2 + 1] - l[o * 2 + 1] + 1));
    c1[o] = c2[o] = 0;
  }
}
void mkt(int _t, int _l, int _r) {
  l[_t] = _l;
  r[_t] = _r;
  c1[_t] = c2[_t] = 0;
  if (_l == _r) {
    sum[_t] = y[_l];
    return;
  }
  int mid = (_l + _r) >> 1;
  ;
  mkt(_t * 2, _l, mid);
  mkt(_t * 2 + 1, mid + 1, _r);
  upd(_t);
}
long long getsum(int _t, int _l, int _r, int l, int r) {
  if (l <= _l && _r <= r) return sum[_t];
  pd(_t);
  int mid = (_l + _r) >> 1;
  ;
  long long ret = 0;
  if (l <= mid) addmod(ret, ret, getsum(_t * 2, _l, mid, l, r));
  if (r > mid) addmod(ret, ret, getsum(_t * 2 + 1, mid + 1, _r, l, r));
  return ret;
}
void change(int _t, int _l, int _r, int l, int r, long long f1, long long f2) {
  if (l <= _l && _r <= r) {
    addmod(c1[_t], c1[_t], f1);
    addmod(c2[_t], c2[_t], f2);
    addmod(sum[_t], sum[_t], s(f1, f2, _r - _l + 1));
    return;
  }
  pd(_t);
  int mid = (_l + _r) >> 1;
  ;
  if (r <= mid)
    change(_t * 2, _l, mid, l, r, f1, f2);
  else if (l > mid)
    change(_t * 2 + 1, mid + 1, _r, l, r, f1, f2);
  else {
    change(_t * 2, _l, mid, l, mid, f1, f2);
    change(_t * 2 + 1, mid + 1, _r, mid + 1, r, f(f1, f2, mid - l + 2),
           f(f1, f2, mid - l + 3));
  }
  upd(_t);
}
int main(int argc, char *argv[]) {
  setIO("sample");
  int n = getint(), m = getint();
  for (int i = 1; i <= n; ++i) y[i] = getint();
  for (int i = 0; i <= 2; ++i) a[0].a[i][i] = 1;
  a[1].a[0][1] = a[1].a[1][0] = a[1].a[1][1] = a[1].a[2][0] = a[1].a[2][2] = 1;
  for (int i = 2; i <= n; ++i) a[i] = mut(a[i - 1], a[1]);
  mkt(1, 1, n);
  for (int i = 1; i <= m; ++i) {
    int o = getint(), p = getint(), q = getint();
    if (o == 1)
      change(1, 1, n, p, q, 1LL, 1LL);
    else
      printf("%I64d\n", getsum(1, 1, n, p, q));
  }
  closeIO();
  return EXIT_SUCCESS;
}
