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;
const long long inf = 9.2e18;
const int maxn = 3e5 + 70;
const int INF = 2.1e9;
const int maxm = 1e6 + 70;
const int MOD = 1e9 + 9;
const double eps = 1e-7;
const double PI = acos(-1.0);
int n, m, k;
int f[maxn], pre[maxn], a[maxn];
void init() {
  f[1] = f[2] = 1;
  pre[0] = 0;
  pre[1] = 1;
  pre[2] = 2;
  for (int i = 3; i < maxn; i++) {
    f[i] = f[i - 2] + f[i - 1];
    if (f[i] > MOD) f[i] -= MOD;
    pre[i] = pre[i - 1] + f[i];
    if (pre[i] > MOD) pre[i] -= MOD;
  }
}
int sumv[4 * maxn], addv[4 * maxn][2];
void build(int o, int L, int R) {
  if (L == R)
    sumv[o] = a[L];
  else {
    int lc = o * 2, rc = o * 2 + 1;
    int M = L + (R - L) / 2;
    build(lc, L, M);
    build(rc, M + 1, R);
    sumv[o] = sumv[lc] + sumv[rc];
    if (sumv[o] > MOD) sumv[o] -= MOD;
  }
}
void maintain(int o, int L, int R) {
  if (L == R)
    sumv[o] = a[L];
  else {
    int lc = o * 2, rc = o * 2 + 1;
    sumv[o] = sumv[lc] + sumv[rc];
    if (sumv[o] > MOD) sumv[o] -= MOD;
  }
  sumv[o] += (((long long)addv[o][0] * pre[R - L + 1] +
               (long long)addv[o][1] * (pre[R - L + 2] - 1)) %
                  MOD +
              MOD) %
             MOD;
  if (sumv[o] > MOD) sumv[o] -= MOD;
}
int ql, qr, _sum;
void update(int o, int L, int R) {
  if (ql <= L && qr >= R) {
    if (L - ql + 1 == 1)
      addv[o][0]++;
    else if (L - ql + 1 == 2)
      addv[o][1]++;
    else {
      addv[o][0] += f[L - ql + 1 - 2];
      addv[o][1] += f[L - ql + 1 - 1];
    }
    if (addv[o][0] > MOD) addv[o][0] -= MOD;
    if (addv[o][1] > MOD) addv[o][1] -= MOD;
  } else {
    int lc = o * 2, rc = o * 2 + 1;
    int M = L + (R - L) / 2;
    if (ql <= M) update(lc, L, M);
    if (qr >= M + 1) update(rc, M + 1, R);
  }
  maintain(o, L, R);
}
void query(int o, int L, int R, int add0, int add1) {
  if (ql <= L && qr >= R) {
    _sum += sumv[o];
    if (_sum > MOD) _sum -= MOD;
    _sum += (((long long)add0 * pre[R - L + 1] +
              (long long)add1 * (pre[R - L + 2] - 1)) %
                 MOD +
             MOD) %
            MOD;
    if (_sum > MOD) _sum -= MOD;
  } else {
    int lc = o * 2, rc = o * 2 + 1;
    int M = L + (R - L) / 2;
    add0 += addv[o][0];
    add1 += addv[o][1];
    if (add0 > MOD) add0 -= MOD;
    if (add1 > MOD) add1 -= MOD;
    if (ql <= M) {
      query(lc, L, M, add0, add1);
    }
    if (qr >= M + 1) {
      int addr0 = 0, addr1 = 0;
      if (M + 1 - L + 1 == 2)
        addr1 += add0;
      else {
        addr0 += ((long long)add0 * f[M + 1 - L + 1 - 2]) % MOD;
        addr1 += ((long long)add0 * f[M + 1 - L + 1 - 1]) % MOD;
      }
      if (addr0 > MOD) addr0 -= MOD;
      if (addr1 > MOD) addr1 -= MOD;
      addr0 += ((long long)add1 * f[M + 1 - L + 2 - 2]) % MOD;
      addr1 += ((long long)add1 * f[M + 1 - L + 2 - 1]) % MOD;
      if (addr0 > MOD) addr0 -= MOD;
      if (addr1 > MOD) addr1 -= MOD;
      query(rc, M + 1, R, addr0, addr1);
    }
  }
}
void check(int o, int L, int R) {
  cout << L << " --- " << R << ": " << sumv[o] << " " << addv[o][0] << " "
       << addv[o][1] << endl;
  if (L < R) {
    int lc = o * 2, rc = o * 2 + 1;
    int M = L + (R - L) / 2;
    check(lc, L, M);
    check(rc, M + 1, R);
  }
}
int main() {
  init();
  while (cin >> n >> m) {
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    build(1, 1, n);
    while (m--) {
      int op;
      scanf("%d%d%d", &op, &ql, &qr);
      if (op == 1) {
        update(1, 1, n);
      } else {
        _sum = 0;
        query(1, 1, n, 0, 0);
        printf("%d\n", _sum);
      }
    }
  }
  return 0;
}
