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;
inline int rei() {
  int x;
  cin >> x;
  return x;
}
inline long long rel() {
  long long x;
  cin >> x;
  return x;
}
inline string res() {
  string x;
  cin >> x;
  return x;
}
class Monoid1 {
 public:
  using t = tuple<long long, long long, long long>;
  static t id() { return make_tuple(0, 0, 0); }
  static t op(const t& l, const t& r) {
    return make_tuple((get<0>(l) + get<0>(r)) % 1000000009,
                      (get<1>(l) + get<1>(r)) % 1000000009,
                      (get<2>(l) + get<2>(r)) % 1000000009);
  }
};
class Monoid2 {
 public:
  using t = long long;
  static t id() { return 0; }
  static t op(const t& l, const t& r) { return (l + r) % 1000000009; }
};
template <typename M>
class SegmentTree {
  using T = typename M::t;
  const int n;
  vector<T> data;
  int size(int n_) {
    int res = 1;
    while (res <= n_) {
      res <<= 1;
    }
    return res;
  }

 public:
  SegmentTree(int n_) : n(size(n_)), data(n * 2, M::id()) {}
  SegmentTree(int n_, T v) : n(size(n_)), data(n * 2, v) {}
  SegmentTree(const vector<T>& data_)
      : n(size(data_.size())), data(n * 2, M::id()) {
    init(data_);
  }
  void init(const vector<T>& data_) {
    for (int i = 0; i < (int)data_.size(); i++) data[i + n] = data_[i];
  }
  T Query(int k) {
    k += n;
    T ans = data[k];
    while (k >>= 1) {
      ans = M::op(ans, data[k]);
    }
    return ans;
  }
  void Update(int a, int b, const T x) {
    for (a += n, b += n; a < b; a >>= 1, b >>= 1) {
      if (a & 1) data[a] = M::op(data[a], x), a++;
      if (b & 1) b--, data[b] = M::op(data[b], x);
    }
  }
};
tuple<long long, long long, long long> Plus[300001];
tuple<long long, long long, long long> Minus[300001];
long long Calc(tuple<long long, long long, long long> X) {
  const long long x0 = 0;
  const long long x1 = 1;
  const long long x2 = 2;
  return (get<0>(X) * x0 + get<1>(X) * x1 + get<2>(X) * x2) % 1000000009;
}
long long Calc(tuple<long long, long long, long long> X,
               tuple<long long, long long, long long> Y) {
  long long prod0 = get<0>(X) * get<0>(Y) % 1000000009;
  long long prod1 = (get<0>(X) * get<1>(Y) % 1000000009 +
                     get<1>(X) * get<0>(Y) % 1000000009) %
                    1000000009;
  long long prod2 =
      (get<0>(X) * get<2>(Y) % 1000000009 + get<1>(X) * get<1>(Y) % 1000000009 +
       get<2>(X) * get<0>(Y) % 1000000009) %
      1000000009;
  long long prod3 = (get<1>(X) * get<2>(Y) % 1000000009 +
                     get<2>(X) * get<1>(Y) % 1000000009) %
                    1000000009;
  long long prod4 = get<2>(X) * get<2>(Y) % 1000000009;
  const long long x0 = 0;
  const long long x1 = 1;
  const long long x2 = 2;
  const long long x3 = 4;
  const long long x4 = 7;
  return (prod0 * x0 + prod1 * x1 + prod2 * x2 + prod3 * x3 + prod4 * x4) %
         1000000009;
}
void Calc() {
  int N = rei();
  int M = rei();
  vector<long long> A(N + 1);
  for (int i = 1; i <= N; i++) {
    A[i] = rei();
    A[i] += A[i - 1];
    A[i] %= 1000000009;
  }
  Plus[0] = make_tuple(1, 0, 0);
  Minus[0] = make_tuple(1, 0, 0);
  for (int i = 1; i <= N; i++) {
    long long x0 = 0;
    long long x1 = get<0>(Plus[i - 1]);
    long long x2 = get<1>(Plus[i - 1]);
    long long x3 = get<2>(Plus[i - 1]);
    x0 = (1000000009 - x3) % 1000000009;
    x2 += 2 * x3;
    x2 %= 1000000009;
    Plus[i] = make_tuple(x0, x1, x2);
  }
  for (int i = 1; i <= N; i++) {
    long long xm = get<0>(Minus[i - 1]);
    long long x0 = get<1>(Minus[i - 1]);
    long long x1 = get<2>(Minus[i - 1]);
    long long x2 = 0;
    x2 = (1000000009 - xm) % 1000000009;
    x1 += 2 * xm;
    x1 %= 1000000009;
    Minus[i] = make_tuple(x0, x1, x2);
  }
  SegmentTree<Monoid1> Seg(N + 1);
  SegmentTree<Monoid2> Seg2(A);
  for (int i = 0; i < M; i++) {
    int type = rei();
    if (type == 1) {
      int l = rei() - 1;
      int r = rei();
      Seg.Update(l, r, Minus[l]);
      Seg2.Update(r, N + 1, Calc(Plus[r - l]));
    } else {
      int l = rei() - 1;
      int r = rei();
      long long ans = 2 * 1000000009 + Calc(Seg.Query(r), Plus[r]) -
                      Calc(Seg.Query(l), Plus[l]) + Seg2.Query(r) -
                      Seg2.Query(l);
      ans %= 1000000009;
      cout << ans << "\n";
    }
  }
}
int main(int argc, char** argv) {
  ios::sync_with_stdio(false), cin.tie(0);
  cout.tie(0);
  Calc();
  return 0;
}
