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 int64_t N = 3e5 + 7, Mod = 1e9 + 9, Majik = 383008016, A = 691504013,
              B = 308495997;
int64_t it_subtract[4 * N], it_addd[4 * N], lazy_subtract[4 * N],
    lazy_addd[4 * N], n, m;
int64_t addd[N], subtract[N], add_inv[N], subtract_inv[N];
void add(int64_t &a, int64_t b) { a = (a + b) % Mod; }
void init_sum() {
  int64_t tmp = 1;
  add_inv[0] = 1;
  for (int64_t i = 1; i <= n; ++i)
    tmp = (1ll * tmp * 691504012) % Mod, add(add_inv[i], add_inv[i - 1] + tmp);
  tmp = 1;
  subtract_inv[0] = 1;
  for (int64_t i = 1; i <= n; ++i)
    tmp = (1ll * tmp * 308495996) % Mod,
    add(subtract_inv[i], subtract_inv[i - 1] + tmp);
  tmp = 1;
  addd[0] = 1;
  for (int64_t i = 1; i <= n; ++i)
    tmp = (1ll * tmp * A) % Mod, add(addd[i], addd[i - 1] + tmp);
  tmp = 1;
  subtract[0] = 1;
  for (int64_t i = 1; i <= n; ++i)
    tmp = (1ll * tmp * B) % Mod, add(subtract[i], subtract[i - 1] + tmp);
}
int64_t sum_add_inv(int64_t l, int64_t r) {
  if (l == 0) return add_inv[r];
  int64_t k = add_inv[r] - add_inv[l - 1];
  if (k < 0) k += Mod;
  return k;
}
int64_t sum_subtract_inv(int64_t l, int64_t r) {
  if (l == 0) return subtract_inv[r];
  int64_t k = subtract_inv[r] - subtract_inv[l - 1];
  if (k < 0) k += Mod;
  return k;
}
int64_t sum_addd(int64_t l, int64_t r) {
  if (l == 0) return addd[r];
  int64_t k = addd[r] - addd[l - 1];
  if (k < 0) k += Mod;
  return k;
}
int64_t sum_subtract(int64_t l, int64_t r) {
  if (l == 0) return subtract[r];
  int64_t k = subtract[r] - subtract[l - 1];
  if (k < 0) k += Mod;
  return k;
}
void down_subtract(int64_t node, int64_t l, int64_t r) {
  if (lazy_subtract[node] == 0) return;
  int64_t t = lazy_subtract[node];
  lazy_subtract[node] = 0;
  add(it_subtract[node], 1ll * t * sum_subtract(l, r) % Mod);
  if (l != r) {
    add(lazy_subtract[(node << 1)], t);
    add(lazy_subtract[((node << 1) + 1)], t);
  }
}
void update_subtract(int64_t node, int64_t l, int64_t r, int64_t u, int64_t v,
                     int64_t val) {
  down_subtract(node, l, r);
  if (v < l || r < u) return;
  if (u <= l && r <= v) {
    add(lazy_subtract[node], val);
    down_subtract(node, l, r);
    return;
  }
  update_subtract((node << 1), l, ((l + r) >> 1), u, v, val);
  update_subtract(((node << 1) + 1), ((l + r) >> 1) + 1, r, u, v, val);
  it_subtract[node] =
      (it_subtract[(node << 1)] + it_subtract[((node << 1) + 1)]) % Mod;
}
void down_addd(int64_t node, int64_t l, int64_t r) {
  if (lazy_addd[node] == 0) return;
  int64_t t = lazy_addd[node];
  lazy_addd[node] = 0;
  add(it_addd[node], 1ll * t * sum_addd(l, r) % Mod);
  if (l != r) {
    add(lazy_addd[(node << 1)], t);
    add(lazy_addd[((node << 1) + 1)], t);
  }
}
void update_addd(int64_t node, int64_t l, int64_t r, int64_t u, int64_t v,
                 int64_t val) {
  down_addd(node, l, r);
  if (v < l || r < u) return;
  if (u <= l && r <= v) {
    add(lazy_addd[node], val);
    down_addd(node, l, r);
    return;
  }
  update_addd((node << 1), l, ((l + r) >> 1), u, v, val);
  update_addd(((node << 1) + 1), ((l + r) >> 1) + 1, r, u, v, val);
  it_addd[node] = (it_addd[(node << 1)] + it_addd[((node << 1) + 1)]) % Mod;
}
int64_t get(int64_t node, int64_t l, int64_t r, int64_t u, int64_t v) {
  down_addd(node, l, r);
  down_subtract(node, l, r);
  if (v < l || r < u) return 0;
  if (u <= l && r <= v) return (it_addd[node] - it_subtract[node]) % Mod;
  return (get((node << 1), l, ((l + r) >> 1), u, v) +
          get(((node << 1) + 1), ((l + r) >> 1) + 1, r, u, v)) %
         Mod;
}
signed main() {
  iostream::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> m;
  init_sum();
  vector<int64_t> v(n + 1);
  for (int64_t i = 1; i <= n; ++i) {
    int64_t a;
    cin >> a;
    v[i] = v[i - 1] + a;
  }
  while (m--) {
    int64_t sign, l, r;
    cin >> sign >> l >> r;
    if (sign == 2) {
      int64_t ans =
          (1ll * get(1, 1, n, l, r) * 276601605 + v[r] - v[l - 1]) % Mod;
      if (ans < 0) ans += Mod;
      cout << ans << '\n';
    } else {
      int64_t val = sum_add_inv(l - 1, l - 1);
      update_addd(1, 1, n, l, r, val);
      val = sum_subtract_inv(l - 1, l - 1);
      update_subtract(1, 1, n, l, r, val);
    }
  }
}
