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 int moder = 1e9 + 9;
int N, M;
vector<long long> A;
long long Fib[(300005)];
inline int addMod(long long a, long long b) {
  a += b;
  if (a >= moder) a %= moder;
  return a;
}
template <typename T>
inline void addMod2(T &a, long long b) {
  a = addMod(a, b);
}
template <class T>
class Matrix2D {
 public:
  int M, N;
  vector<T> A;
  Matrix2D() { M = N = 0; }
  Matrix2D(int m, int n, T def) {
    M = m;
    N = n;
    A.resize(m * n, def);
  }
  Matrix2D(int m, int n, vector<T> v) {
    if (v.size() != m * n) v.resize(m * n);
    M = m;
    N = n;
    A = v;
  }
  Matrix2D(vector<vector<T>> B) {
    M = B.size();
    if (M > 0) {
      int i;
      int valid = 1;
      N = B[0].size();
      for (i = 1; i < M; ++i) {
        if (N != int(B[i].size())) {
          M = N = 0;
          A = vector<T>();
          valid = 0;
          break;
        }
      }
      if (valid) {
        int j, k = 0;
        A.resize(M * N);
        for (i = 0; i < M; ++i)
          for (j = 0; j < N; ++j) A[k++] = B[i][j];
      }
    } else
      N = 0;
  }
  static Matrix2D<T> emptyMatrix() { return Matrix2D<T>(); }
  T *operator[](int row) { return (T *)&A[row * N]; }
  friend Matrix2D<T> add(Matrix2D<T> A, Matrix2D<T> B) {
    if (A.M != B.M || A.N != B.N) return emptyMatrix();
    int M = A.M;
    int N = A.N;
    Matrix2D<T> C(M, N, 0);
    for (int i = 0; i < M; ++i) {
      for (int j = 0; j < N; ++j) C[i][j] = A[i][j] + B[i][j];
    }
    return C;
  }
  friend Matrix2D<T> multiply(Matrix2D<T> A, Matrix2D<T> B) {
    if (A.N != B.M) return emptyMatrix();
    int M = A.M;
    int N = A.N;
    int P = B.N;
    Matrix2D<T> C(M, P, 0);
    for (int i = 0; i < M; ++i) {
      for (int j = 0; j < P; ++j) {
        T sum = 0;
        for (int k = 0; k < N; ++k) sum += A[i][k] * B[k][j];
        C[i][j] = sum;
      }
    }
    return C;
  }
  void print_format(const char *format) {
    int i, j, k = 0;
    for (i = 0; i < M; ++i) {
      for (j = 0; j < N; ++j) {
        if (j) putchar(' ');
        printf(format, A[k++]);
      }
      putchar('\n');
    }
    putchar('\n');
  }
};
template <class T>
class SquareMatrix : public Matrix2D<T> {
 public:
  SquareMatrix() : Matrix2D<T>() {}
  SquareMatrix(int n, T def) : Matrix2D<T>(n, n, def) {}
  SquareMatrix(int n, vector<T> v) : Matrix2D<T>(n, n, v) {}
  SquareMatrix(vector<vector<T>> B) : Matrix2D<T>(B) {
    if (this->M != this->N) *this = emptyMatrix();
  }
  SquareMatrix<T> operator=(Matrix2D<T> B) {
    if (B.M != B.N) return emptyMatrix();
    return *this = SquareMatrix(B.M, B.A);
  }
  static SquareMatrix<T> emptyMatrix() { return SquareMatrix<T>(); }
  static SquareMatrix<T> identityMatrix(int n) {
    return diagonalMatrix(n, 1, 0);
  }
  static SquareMatrix<T> diagonalMatrix(int n, T diag, T rest) {
    SquareMatrix<T> B(n, rest);
    for (int i = 0; i < n; ++i) B[i][i] = diag;
    return B;
  }
  SquareMatrix<T> power(long long k) {
    if (k == 0)
      return identityMatrix(this->M);
    else if (k == 1)
      return *this;
    else {
      SquareMatrix B = this->power(k >> 1);
      B = multiply(B, B);
      if (k & 1) B = multiply(B, *this);
      return B;
    }
  }
};
template <class T, int D, T moder>
class SquareMatrixMod : public SquareMatrix<T> {
 public:
  SquareMatrixMod() : SquareMatrix<T>(D, 0) {}
  SquareMatrixMod(T diag) : SquareMatrix<T>(D, 0) {
    for (int i = 0; i < D; ++i) (*this)[i][i] = diag;
  }
  SquareMatrixMod(vector<T> v) : SquareMatrix<T>(D, v) {}
  SquareMatrixMod(vector<vector<T>> B) : SquareMatrix<T>(B) {}
  static SquareMatrixMod<T, D, moder> identityMatrix() {
    return SquareMatrixMod<T, D, moder>(1);
  }
  static SquareMatrixMod<T, D, moder> diagonalMatrix(T diag) {
    return SquareMatrixMod<T, D, moder>(diag);
  }
  friend SquareMatrixMod<T, D, moder> multiplyMod(
      SquareMatrixMod<T, D, moder> A, SquareMatrixMod<T, D, moder> B) {
    Matrix2D<T> C = multiply(A, B);
    int D2 = D * D;
    T *mat = C[0];
    for (int i = 0; i < D2; ++i) *(mat + i) %= moder;
    return SquareMatrixMod<T, D, moder>(C.A);
  }
  SquareMatrixMod<T, D, moder> power(long long k) {
    if (k == 0)
      return identityMatrix();
    else if (k == 1)
      return *this;
    else {
      SquareMatrixMod<T, D, moder> B = this->power(k >> 1);
      B = multiplyMod(B, B);
      if (k & 1) B = multiplyMod(B, *this);
      return B;
    }
  }
};
SquareMatrixMod<long long, 3, moder> SM[(300005)];
class LazySegmentTree {
 private:
  vector<int> left_bound, right_bound;
  int query_left, query_right;
  int size;
  int base;
  vector<long long> seg_value;
  vector<pair<int, int>> seg_lazy;
  long long query_value;
  long long query_result;
  inline int left_child(int id) { return id + id; }
  inline int right_child(int id) { return id + id + 1; }
  void seg_push(int id) {
    pair<int, int> lazy = seg_lazy[id];
    seg_lazy[id] = pair<int, int>(0, 0);
    if (lazy == pair<int, int>(0, 0)) return;
    int l = left_bound[id];
    int r = right_bound[id];
    long long res =
        SM[r - l + 1][2][0] * lazy.first + SM[r - l + 1][2][1] * lazy.second;
    addMod2(seg_value[id], res);
    if (id < base) {
      int lc = left_child(id);
      int rc = right_child(id);
      addMod2(seg_lazy[lc].first, lazy.first);
      addMod2(seg_lazy[lc].second, lazy.second);
      auto &mat = SM[(r - l + 1) >> 1];
      long long a = mat[0][0] * lazy.first + mat[0][1] * lazy.second;
      long long b = mat[1][0] * lazy.first + mat[1][1] * lazy.second;
      addMod2(seg_lazy[rc].first, a);
      addMod2(seg_lazy[rc].second, b);
    }
  }
  void seg_merge(int id) {
    if (id < base) {
      int lc = left_child(id);
      int rc = right_child(id);
      seg_push(lc);
      seg_push(rc);
      seg_value[id] = addMod(seg_value[lc], seg_value[rc]);
    }
  }
  void internal_update(int id) {
    if (query_right < left_bound[id] || right_bound[id] < query_left) return;
    if (query_left <= left_bound[id] && right_bound[id] <= query_right) {
      int a = left_bound[id] - query_left;
      addMod2(seg_lazy[id].first, Fib[a + 1]);
      addMod2(seg_lazy[id].second, Fib[a + 2]);
      seg_push(id);
      return;
    }
    seg_push(id);
    internal_update(left_child(id));
    internal_update(right_child(id));
    seg_merge(id);
  }
  void internal_query(int id) {
    if (query_right < left_bound[id] || right_bound[id] < query_left) return;
    if (query_left <= left_bound[id] && right_bound[id] <= query_right) {
      seg_push(id);
      addMod2(query_result, seg_value[id]);
      return;
    }
    seg_push(id);
    internal_query(left_child(id));
    internal_query(right_child(id));
    seg_merge(id);
  }
  void update_bound(int id, int l, int r) {
    left_bound[id] = l;
    right_bound[id] = r;
    if (l < r) {
      int m = (l + r) / 2;
      update_bound(left_child(id), l, m);
      update_bound(right_child(id), m + 1, r);
    }
  }

 public:
  LazySegmentTree(const vector<long long> &A) { init(A); }
  ~LazySegmentTree() {
    left_bound.clear();
    right_bound.clear();
    seg_value.clear();
    seg_lazy.clear();
  }
  void init(const vector<long long> &A) {
    int n = A.size();
    if (n <= 0) {
      base = size = 0;
      return;
    }
    base = 2;
    while (base < n) base <<= 1;
    size = base * 2;
    left_bound.resize(size);
    right_bound.resize(size);
    seg_value.resize(size, 0LL);
    seg_lazy.resize(size, pair<int, int>(0, 0));
    update_bound(1, 0, base - 1);
    for (int i = 0; i < n; ++i) seg_value[i + base] = A[i];
    for (int i = base - 1; i >= 1; --i) seg_merge(i);
  }
  void update(int l, int r) {
    query_left = l;
    query_right = r;
    internal_update(1);
  }
  long long query(int l, int r) {
    query_left = l;
    query_right = r;
    query_result = 0;
    internal_query(1);
    return query_result;
  }
};
int main() {
  int i;
  scanf("%d %d", &N, &M);
  A.resize(N);
  for (i = 0; i < N; ++i) {
    int a;
    scanf("%d", &a);
    A[i] = a;
  }
  LazySegmentTree ST(A);
  SM[0] = SquareMatrixMod<long long, 3, moder>::identityMatrix();
  SM[1] =
      SquareMatrixMod<long long, 3, moder>({{0, 1, 0}, {1, 1, 0}, {1, 0, 1}});
  for (i = 2; i <= N; ++i) SM[i] = multiplyMod(SM[i - 1], SM[1]);
  Fib[1] = Fib[2] = 1;
  for (i = 3; i <= N; ++i) Fib[i] = addMod(Fib[i - 1], Fib[i - 2]);
  for (i = 0; i < M; ++i) {
    int t, a, b;
    scanf("%d %d %d", &t, &a, &b);
    --a;
    --b;
    if (t == 1) {
      ST.update(a, b);
    } else {
      printf("%I64d\n", ST.query(a, b));
    }
  }
  return 0;
}
