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;
int mpow(int base, int exp);
void ipgraph(int m);
void dfs(int u, int par);
const int mod = 1000000007 + 2;
const int N = 1048577, M = N;
long long A = 276601605;
long long C = 691504013;
long long D = 308495997;
vector<int> g[N];
int a[N];
long long T[N], PO1[N], PO2[N];
long long dp[3];
class GP {
 public:
  long long a, r;
  GP() {}
  GP(long long x, long long y) { a = x % mod, r = y % mod; }
  void init(long long x, long long y) { a = x % mod, r = y % mod; }
  long long sum(long long lo, long long hi) {
    return (prefix(hi) - prefix(lo - 1) + mod) % mod;
  }
  long long nth(long long n) { return a * mpow(r, n - 1) % mod; }
  long long prefix(long long n) {
    if (n == 0) return 0;
    if (r == 1) return n * a;
    long long ans = (a * (mpow(r, n) - 1 + mod)) % mod;
    ans *= inv(r - 1, mod - 2);
    ans %= mod;
    return ans;
  }
  int inv(int n, int x) {
    if (n + 1 == C) return dp[0];
    if (n + 1 == D) return dp[1];
  }
} gp1, gp2, l1[N], l2[N];
void build(int id, int lo, int hi) {
  if (lo == hi) {
    T[id] = a[lo];
    return;
  }
  int mid = (lo + hi) / 2;
  build(2 * id, lo, mid);
  build(2 * id + 1, mid + 1, hi);
  T[id] = (T[2 * id] + T[2 * id + 1]) % mod;
}
int x, y;
void update(int id, int lo, int hi, int L, int R) {
  l1[id].a %= mod;
  l2[id].a %= mod;
  if (lo == L and hi == R) {
    l1[id].a += gp1.nth(lo - x + 1);
    l2[id].a += gp2.nth(lo - x + 1);
    T[id] += (gp1.sum(lo - x + 1, hi - x + 1) -
              gp2.sum(lo - x + 1, hi - x + 1) + mod) %
             mod;
    return;
  }
  int mid = (lo + hi) / 2;
  if (l1[id].a) {
    l1[2 * id].a += l1[id].a;
    l2[2 * id].a += l2[id].a;
    l1[2 * id + 1].a += l1[id].nth(mid - lo + 2);
    l2[2 * id + 1].a += l2[id].nth(mid - lo + 2);
    T[2 * id] +=
        (mod + l1[id].prefix(mid - lo + 1) - l2[id].prefix(mid - lo + 1)) % mod;
    T[2 * id + 1] += (mod + l1[id].sum(mid + 2 - lo, hi - lo + 1) -
                      l2[id].sum(mid + 2 - lo, 1 + hi - lo)) %
                     mod;
    l1[id].a = l2[id].a = 0;
  }
  if (R <= mid)
    update(2 * id, lo, mid, L, R);
  else if (L > mid)
    update(2 * id + 1, mid + 1, hi, L, R);
  else
    update(2 * id, lo, mid, L, mid),
        update(2 * id + 1, mid + 1, hi, mid + 1, R);
  T[id] = (mod + T[2 * id] + T[2 * id + 1]) % mod;
}
long long query(int id, int lo, int hi, int L, int R) {
  l1[id].a %= mod;
  l2[id].a %= mod;
  if (lo == L and hi == R) {
    return T[id] % mod;
  }
  int mid = (lo + hi) / 2;
  if (l1[id].a) {
    l1[2 * id].a += l1[id].a;
    l2[2 * id].a += l2[id].a;
    l1[2 * id + 1].a += l1[id].nth(mid - lo + 2);
    l2[2 * id + 1].a += l2[id].nth(mid - lo + 2);
    T[2 * id] +=
        (mod + l1[id].prefix(mid - lo + 1) - l2[id].prefix(mid - lo + 1)) % mod;
    T[2 * id + 1] += (mod + l1[id].sum(mid + 2 - lo, hi - lo + 1) -
                      l2[id].sum(mid + 2 - lo, 1 + hi - lo)) %
                     mod;
    l1[id].a = l2[id].a = 0;
  }
  if (R <= mid) return query(2 * id, lo, mid, L, R);
  if (L > mid) return query(2 * id + 1, mid + 1, hi, L, R);
  return (query(2 * id, lo, mid, L, mid) +
          query(2 * id + 1, mid + 1, hi, mid + 1, R)) %
         mod;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int i, n, k, j;
  dp[0] = mpow(C - 1, mod - 2);
  dp[1] = mpow(D - 1, mod - 2);
  gp1.init(A * C, C);
  gp2.init(A * D, D);
  PO1[0] = PO2[0] = 1;
  for (i = 1; 1 < N ? i < N : i > N; 1 < N ? i += 1 : i -= 1)
    l1[i].init(0, C), l2[i].init(0, D);
  for (i = 1; 1 < N ? i < N : i > N; 1 < N ? i += 1 : i -= 1)
    PO1[i] = (C * PO1[i - 1]) % mod;
  for (i = 1; 1 < N ? i < N : i > N; 1 < N ? i += 1 : i -= 1)
    PO2[i] = (D * PO2[i - 1]) % mod;
  cin >> n >> k;
  for (i = 0; i < n; i++) cin >> a[i];
  build(1, 0, n - 1);
  while (k--) {
    cin >> j >> x >> y;
    x--, y--;
    if (j == 1) {
      update(1, 0, n - 1, x, y);
    } else
      cout << query(1, 0, n - 1, x, y) << endl;
  }
  return 0;
}
int mpow(int base, int exp) {
  if (base == C) return PO1[exp];
  if (base == D) return PO2[exp];
  base %= mod;
  int result = 1;
  while (exp > 0) {
    if (exp & 1) result = ((long long)result * base) % mod;
    base = ((long long)base * base) % mod;
    exp >>= 1;
  }
  return result;
}
