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 double eps = 1e-9;
const int oo = 0x3f3f3f3f;
template <class Type, class LazyType>
struct Entry {
  Type data;
  LazyType lazy;
  bool markReset;
  Entry(Type data_, LazyType lazy_, bool markReset_ = false)
      : data(data_), lazy(lazy_), markReset(markReset_) {}
};
template <class Type, class LazyType>
struct SegmentTree {
  typedef Type (*SegmentTreeValueMergerPointer)(Type a, Type b);
  typedef Type (*SegmentTreeValueLazyMergerPointer)(Type a, LazyType b, int F,
                                                    int T);
  typedef LazyType (*SegmentTreeLazyMergerPointer)(LazyType a, LazyType b);
  int S;
  int SP2;
  Type neutral_value, empty_value;
  LazyType neutral_lazy_value;
  SegmentTreeValueMergerPointer valueMerger;
  SegmentTreeValueLazyMergerPointer valueLazyMerger;
  SegmentTreeLazyMergerPointer lazyMerger;
  vector<Entry<Type, LazyType> > entries;
  SegmentTree(int N, Type neutral_value_, Type empty_value_,
              LazyType neutral_lazy_value_,
              SegmentTreeValueMergerPointer valueMerger_,
              SegmentTreeValueLazyMergerPointer valueLazyMerger_,
              SegmentTreeLazyMergerPointer lazyMerger_) {
    neutral_value = neutral_value_;
    empty_value = empty_value_;
    neutral_lazy_value = neutral_lazy_value_;
    valueLazyMerger = valueLazyMerger_;
    valueMerger = valueMerger_;
    lazyMerger = lazyMerger_;
    S = N;
    entries = vector<Entry<Type, LazyType> >(
        S * 2 + 2, Entry<Type, LazyType>(neutral_value, neutral_lazy_value));
    SP2 = 1;
    while (SP2 * 2 <= S) SP2 *= 2;
  }
  Type mergeValues(Type v1, Type v2) { return valueMerger(v1, v2); }
  LazyType mergeLazy(LazyType old, LazyType upd) {
    return lazyMerger(old, upd);
  }
  Type mergeValueLazy(Type old, LazyType upd, int F, int T) {
    return valueLazyMerger(old, upd, F, T);
  }
  int get_mid(int D, int P2) {
    return (((P2 >> 1) | P2) <= D) ? P2 : D - (P2 >> 1);
  }
  void distributeReset(int id, int F, int T) {
    assert(entries[id].markReset);
    entries[id].markReset = false;
    if (F + 1 == T) return;
    entries[id * 2 + 1] = entries[id * 2 + 2] =
        Entry<Type, LazyType>(neutral_value, neutral_lazy_value, true);
  }
  Type query(int id, int P2, int F, int T, int f, int t) {
    if (entries[id].markReset) distributeReset(id, F, T);
    f = max(f, F);
    t = min(t, T);
    if (f >= t) return empty_value;
    if (f == F && t == T) return entries[id].data;
    int M = F + get_mid(T - F, P2);
    Type r1 = query(id * 2 + 1, P2 >> 1, F, M, f, t);
    Type r2 = query(id * 2 + 2, P2 >> 1, M, T, f, t);
    return mergeValueLazy(mergeValues(r1, r2), entries[id].lazy, f, t);
  }
  Type query(int f, int t) {
    auto res = query(0, SP2, 0, S, f, t);
    return res;
  }
  void update(int id, int P2, int F, int T, int f, int t, LazyType change) {
    if (entries[id].markReset) distributeReset(id, F, T);
    f = max(f, F);
    t = min(t, T);
    if (f >= t) return;
    if (f == F && t == T) {
      entries[id].lazy = mergeLazy(entries[id].lazy, change);
      entries[id].data = mergeValueLazy(entries[id].data, change, F, T);
    } else {
      int M = F + get_mid(T - F, P2);
      update(id * 2 + 1, P2 >> 1, F, M, f, t, change);
      update(id * 2 + 2, P2 >> 1, M, T, f, t, change);
      entries[id].data = mergeValueLazy(
          mergeValues(entries[id * 2 + 1].data, entries[id * 2 + 2].data),
          entries[id].lazy, F, T);
    }
  }
  void update(int f, int t, LazyType change) {
    update(0, SP2, 0, S, f, t, change);
  }
  void reset(int id, int P2, int F, int T, int f, int t) {
    if (entries[id].markReset) return;
    f = max(f, F);
    t = min(t, T);
    if (f >= t) return;
    if (f == F && t == T) {
      entries[id] =
          Entry<Type, LazyType>(neutral_value, neutral_lazy_value, true);
    } else {
      int M = F + get_mid(T - F, P2);
      update(id * 2 + 1, P2 >> 1, F, M, F, T, entries[id].lazy);
      update(id * 2 + 2, P2 >> 1, M, T, F, T, entries[id].lazy);
      entries[id].lazy = neutral_lazy_value;
      reset(id * 2 + 1, P2 >> 1, F, M, f, t);
      reset(id * 2 + 2, P2 >> 1, M, T, f, t);
      entries[id].data = mergeValueLazy(
          mergeValues(entries[id * 2 + 1].data, entries[id * 2 + 2].data),
          entries[id].lazy, F, T);
    }
  }
  void reset(int f, int t) { reset(0, SP2, 0, S, f, t); }
  void init(int id, int P2, int F, int T, vector<Type> &initialValues) {
    entries[id] =
        Entry<Type, LazyType>(neutral_value, neutral_lazy_value, false);
    if (F + 1 == T) {
      entries[id].data = initialValues[F];
    } else {
      int M = F + get_mid(T - F, P2);
      init(id * 2 + 1, P2 >> 1, F, M, initialValues);
      init(id * 2 + 2, P2 >> 1, M, T, initialValues);
      entries[id].data = mergeValueLazy(
          mergeValues(entries[id * 2 + 1].data, entries[id * 2 + 2].data),
          entries[id].lazy, F, T);
    }
  }
  void init(vector<Type> &initialValues) {
    assert(initialValues.size() == (unsigned int)S);
    init(0, SP2, 0, S, initialValues);
  }
  void debugTree(int id, int P2, int F, int T) {
    cerr << "(" << id << "," << F << "," << T << "):" << entries[id].data << " "
         << entries[id].lazy << " " << entries[id].markReset << endl;
    if (F + 1 == T) {
      return;
    } else {
      int M = F + get_mid(T - F, P2);
      debugTree(id * 2 + 1, P2 >> 1, F, M);
      debugTree(id * 2 + 2, P2 >> 1, M, T);
    }
  }
  void debugTree() { debugTree(0, SP2, 0, S); }
};
const long long MOD = 1e9 + 9;
long long mod(long long v) { return ((v % MOD) + MOD) % MOD; }
vector<long long> fib_mem;
vector<long long> fib_acu_mem;
long long fib(int p) {
  ;
  ;
  return fib_mem[p];
}
long long fib_acu(int p) {
  ;
  ;
  return fib_acu_mem[p];
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int N, Q;
  cin >> N >> Q;
  fib_acu_mem = fib_mem = vector<long long>(N + 10);
  fib_mem[1] = fib_mem[0] = 0;
  fib_mem[2] = 1;
  for (int i = (3); i < (N + 10); i++)
    fib_mem[i] = mod(fib_mem[i - 1] + fib_mem[i - 2]);
  for (int i = (1); i < (N + 10); i++)
    fib_acu_mem[i] = mod(fib_acu_mem[i - 1] + fib_mem[i]);
  SegmentTree<long long, tuple<long long, long long, int> > segmentTree(
      N, 0, 0, tuple<long long, long long, int>(0, 0, 0),
      [](long long a, long long b) { return mod(a + b); },
      [](long long a, tuple<long long, long long, int> b, int F,
         int T) -> long long {
        return mod(
            a +
            get<0>(b) *
                (fib_acu(T - get<2>(b) + 1) - fib_acu(F - get<2>(b) + 1)) +
            get<1>(b) * (fib_acu(T - get<2>(b)) - fib_acu(F - get<2>(b))));
      },
      [](tuple<long long, long long, int> a, tuple<long long, long long, int> b)
          -> tuple<long long, long long, int> {
        int maxid = max(get<2>(a), get<2>(b));
        tuple<long long, long long, int> res(0, 0, maxid);
        for (auto x : {a, b}) {
          if (maxid == get<2>(x)) {
            res = tuple<long long, long long, int>(mod(get<0>(res) + get<0>(x)),
                                                   mod(get<1>(res) + get<1>(x)),
                                                   maxid);
          } else {
            int diff = maxid - get<2>(x);
            long long v1 =
                fib(diff + 2) * get<0>(x) + fib(diff + 1) * get<1>(x);
            long long v2 =
                fib(diff + 3) * get<0>(x) + fib(diff + 2) * get<1>(x);
            res = tuple<long long, long long, int>(
                mod(get<0>(res) + v1), mod(get<1>(res) + v2 - v1), maxid);
          }
        }
        return res;
      });
  vector<long long> initialValues(N);
  for (int i = (0); i < (N); i++) cin >> initialValues[i];
  segmentTree.init(initialValues);
  for (int q = (0); q < (Q); q++) {
    int k, f, t;
    cin >> k >> f >> t;
    --f;
    if (k == 1)
      segmentTree.update(f, t, tuple<long long, long long, int>(1, 0, f));
    else
      cout << segmentTree.query(f, t) << "\n";
  }
  return 0;
}
