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>
const int maxn = 400000 + 100;
const long long inv = 276601605;
const long long q1 = 691504013;
const long long q2 = 308495997;
const long long MOD = 1e9 + 9;
long long sum[maxn << 2];
long long p1[maxn << 2];
long long p2[maxn << 2];
long long pw1[maxn], pw2[maxn];
long long f1[maxn], f2[maxn];
long long a[maxn];
int tl, tr;
void init() {
  pw1[0] = 1, pw2[0] = 1;
  for (int i = 1; i <= 300000 + 100; i++) {
    pw1[i] = (pw1[i - 1] * q1) % MOD;
    pw2[i] = (pw2[i - 1] * q2) % MOD;
  }
  f1[1] = 1, f2[1] = 1;
  for (int i = 2; i <= 300000 + 100; i++) {
    f1[i] = (f1[i - 1] + pw1[i - 1]) % MOD;
    f2[i] = (f2[i - 1] + pw2[i - 1]) % MOD;
  }
}
void pushdown(int l, int r, int rt) {
  if (l == r) return;
  int mid = (l + r) >> 1;
  int lc = rt << 1;
  int rc = rt << 1 | 1;
  long long delta;
  if (p1[rt] != 0) {
    p1[lc] = (p1[lc] + p1[rt]) % MOD;
    sum[lc] = (sum[lc] + (p1[rt] * f1[mid - l + 1] % MOD) + MOD) % MOD;
    delta = (p1[rt] * pw1[mid - l + 1]) % MOD;
    p1[rc] = (p1[rc] + delta + MOD) % MOD;
    sum[rc] = (sum[rc] + (delta * f1[r - mid]) % MOD + MOD) % MOD;
    p1[rt] = 0;
  }
  if (p2[rt] != 0) {
    p2[lc] = (p2[lc] + p2[rt]) % MOD;
    sum[lc] = (sum[lc] - (p2[rt] * f2[mid - l + 1] % MOD) + MOD) % MOD;
    delta = (p2[rt] * pw2[mid - l + 1]) % MOD;
    p2[rc] = (p2[rc] + delta + MOD) % MOD;
    sum[rc] = (sum[rc] - (delta * f2[r - mid]) % MOD + MOD) % MOD;
    p2[rt] = 0;
  }
}
void update(int l, int r, int rt) {
  pushdown(l, r, rt);
  if (tl <= l && r <= tr) {
    long long delta = pw1[l - tl + 1];
    p1[rt] = (p1[rt] + delta) % MOD;
    sum[rt] = (sum[rt] + delta * f1[r - l + 1] % MOD + MOD) % MOD;
    delta = pw2[l - tl + 1];
    p2[rt] = (p2[rt] + delta) % MOD;
    sum[rt] = (sum[rt] - delta * f2[r - l + 1] % MOD + MOD) % MOD;
  } else {
    int mid = (l + r) >> 1;
    if (tl <= mid) update(l, mid, rt << 1);
    if (tr > mid) update(mid + 1, r, rt << 1 | 1);
    sum[rt] = (sum[rt << 1] + sum[rt << 1 | 1]) % MOD;
  }
}
long long query(int L, int R, int l, int r, int rt) {
  pushdown(l, r, rt);
  if (L <= l && r <= R) {
    return sum[rt];
  }
  int mid = (l + r) >> 1;
  if (R <= mid) return query(L, R, l, mid, rt << 1);
  if (L > mid) return query(L, R, mid + 1, r, rt << 1 | 1);
  return (query(L, R, l, mid, rt << 1) + query(L, R, mid + 1, r, rt << 1 | 1)) %
         MOD;
}
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%lld", &a[i]);
    a[i] = (a[i - 1] + a[i]) % MOD;
  }
  init();
  while (m--) {
    int op;
    scanf("%d%d%d", &op, &tl, &tr);
    if (op == 1) {
      update(1, n, 1);
    } else {
      long long ans = query(tl, tr, 1, n, 1);
      ans = (ans * inv) % MOD;
      ans = (ans + a[tr] - a[tl - 1] + 2 * MOD) % MOD;
      if (ans < 0) ans = (ans + MOD) % MOD;
      printf("%lld\n", ans);
    }
  }
  return 0;
}
