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 read_int() {
  int value;
  cin >> value;
  return value;
}
template <class T>
void println(const T& value) {
  cout << value << '\n';
}
template <class T>
void print_vector(const vector<T>& values) {
  for (size_t(i) = 0, __size = (values.size()); (i) < __size; ++(i))
    cout << values[i] << ' ';
  cout << '\n';
  ;
}
void print_indexes(const vector<size_t>& indexes) {
  for (size_t(i) = 0, __size = (indexes.size()); (i) < __size; ++(i))
    cout << indexes[i] + 1 << ' ';
  cout << '\n';
  ;
}
bool check_index(const size_t index, const size_t size) {
  return (0 <= index && index < size);
}
bool check_indexes(const size_t x, const size_t x_size, const size_t y,
                   const size_t y_size) {
  return check_index(x, x_size) && check_index(y, y_size);
}
int set_bit(int& mask, const size_t bit_index) {
  return mask = (mask | (1 << bit_index));
}
const unsigned int MODULO = 1000 * 1000 * 1000 + 9;
inline unsigned int add(unsigned int a, unsigned int b) {
  return (a + b) % MODULO;
}
inline unsigned int multiply(unsigned int a, unsigned int b) {
  return static_cast<unsigned int>((a * 1LL * b) % MODULO);
}
class fib_matrix {
 public:
  unsigned int values[2][2];
  fib_matrix() {
    for (size_t(row) = 0, __size = (2); (row) < __size; ++(row))
      for (size_t(column) = 0, __size = (2); (column) < __size; ++(column))
        values[row][column] = 0;
  }
  fib_matrix(const fib_matrix& base) {
    for (size_t(row) = 0, __size = (2); (row) < __size; ++(row))
      for (size_t(column) = 0, __size = (2); (column) < __size; ++(column))
        values[row][column] = base.values[row][column];
  }
  fib_matrix& operator=(const fib_matrix& other) {
    if (this != &other) {
      for (size_t(row) = 0, __size = (2); (row) < __size; ++(row))
        for (size_t(column) = 0, __size = (2); (column) < __size; ++(column))
          (*this).values[row][column] = other.values[row][column];
    }
    return (*this);
  }
  fib_matrix operator+(const fib_matrix& other) {
    fib_matrix result;
    for (size_t(row) = 0, __size = (2); (row) < __size; ++(row))
      for (size_t(column) = 0, __size = (2); (column) < __size; ++(column))
        result.values[row][column] =
            add((*this).values[row][column], other.values[row][column]);
    return result;
  }
  fib_matrix operator*(const fib_matrix& other) {
    fib_matrix result;
    for (size_t(row) = 0, __size = (2); (row) < __size; ++(row))
      for (size_t(mid) = 0, __size = (2); (mid) < __size; ++(mid))
        for (size_t(other_column) = 0, __size = (2); (other_column) < __size;
             ++(other_column))
          result.values[row][other_column] =
              add(result.values[row][other_column],
                  multiply((*this).values[row][mid],
                           other.values[mid][other_column]));
    return result;
  }
};
const unsigned long long SHIFT = 32;
const unsigned long long FIRST_MASK = (1LL << SHIFT) - 1;
long long multiply(const fib_matrix& coeff_matrix,
                   const long long& base_values) {
  unsigned int base_first = ((base_values)&FIRST_MASK);
  unsigned int base_second = ((base_values) >> SHIFT);
  unsigned int first_value =
      add(multiply(coeff_matrix.values[0][0], base_first),
          multiply(coeff_matrix.values[0][1], base_second));
  unsigned int second_value =
      add(multiply(coeff_matrix.values[1][0], base_first),
          multiply(coeff_matrix.values[1][1], base_second));
  return ((first_value) |
          (static_cast<unsigned long long>(second_value) << SHIFT));
}
unsigned int get_sum(const fib_matrix& sum_matrix,
                     const long long& base_values) {
  unsigned int base_first = ((base_values)&FIRST_MASK);
  unsigned int base_second = ((base_values) >> SHIFT);
  unsigned int sum = add(multiply(sum_matrix.values[0][0], base_first),
                         multiply(sum_matrix.values[0][1], base_second));
  return sum;
}
long long add_base(const long long& changed_base, const long long& added_base) {
  unsigned int first_value =
      add(((changed_base)&FIRST_MASK), ((added_base)&FIRST_MASK));
  unsigned int second_value =
      add(((changed_base) >> SHIFT), ((added_base) >> SHIFT));
  return ((first_value) |
          (static_cast<unsigned long long>(second_value) << SHIFT));
}
static const long long BASE =
    ((1LL) | (static_cast<unsigned long long>(0LL) << SHIFT));
static const long long EMPTY_BASE = 0;
inline size_t min(const size_t a, const size_t b) { return (a < b ? a : b); }
inline size_t max(const size_t a, const size_t b) { return (a > b ? a : b); }
class Segment_tree {
 private:
  static const size_t ROOT = 1;
  const size_t array_size, tree_size;
  vector<size_t> v_sizes;
  vector<long long> bases;
  vector<unsigned int> sums;
  vector<fib_matrix> powers;
  vector<long long> base_powers;
  vector<fib_matrix> sum_matrixes;
  unsigned int build_tree(const size_t v, const size_t left, const size_t right,
                          const vector<unsigned int>& array) {
    if (left == right) {
      v_sizes[v] = 1;
      return (sums[v] = array[left]);
    } else {
      size_t mid = ((left + right) >> 1);
      size_t v_left = (v << 1);
      size_t v_right = (v_left + 1);
      unsigned int left_sum = build_tree(v_left, left, mid, array);
      unsigned int right_sum = build_tree(v_right, mid + 1, right, array);
      v_sizes[v] = v_sizes[v_left] + v_sizes[v_right];
      return (sums[v] = add(left_sum, right_sum));
    }
  }
  void push(const size_t v, const size_t v_left, const size_t v_right) {
    long long vertex_base = bases[v];
    if (vertex_base != 0) {
      long long left_base = bases[v_left];
      long long right_base = bases[v_right];
      size_t left_size = v_sizes[v_left];
      bases[v_left] = add_base(left_base, vertex_base);
      bases[v_right] =
          add_base(right_base, multiply(powers[left_size], vertex_base));
      bases[v] = EMPTY_BASE;
    }
  }
  void update(const size_t v, const size_t v_left, const size_t v_right) {
    long long left_base = bases[v_left];
    size_t left_size = v_sizes[v_left];
    long long right_base = bases[v_right];
    size_t right_size = v_sizes[v_right];
    unsigned int left_sum =
        add(sums[v_left], get_sum(sum_matrixes[left_size], left_base));
    unsigned int right_sum =
        add(sums[v_right], get_sum(sum_matrixes[right_size], right_base));
    sums[v] = add(left_sum, right_sum);
  }
  unsigned int add_segment(const size_t v, const size_t left,
                           const size_t right, const size_t left_index,
                           const size_t right_index, const size_t base_power) {
    if (right_index < left || right < left_index) return 0;
    if (left == left_index && right_index == right) {
      long long base = base_powers[base_power];
      bases[v] = add_base(bases[v], base);
    } else {
      size_t v_left = (v << 1);
      size_t v_right = (v_left + 1);
      size_t mid = ((left + right) >> 1);
      push(v, v_left, v_right);
      if (right_index <= mid)
        add_segment(v_left, left, mid, left_index, right_index, base_power);
      else if (left_index >= mid + 1)
        add_segment(v_right, mid + 1, right, left_index, right_index,
                    base_power);
      else {
        size_t left_part_size = (mid - left_index + 1);
        add_segment(v_left, left, mid, left_index, mid, base_power);
        add_segment(v_right, mid + 1, right, mid + 1, right_index,
                    base_power + left_part_size);
      }
      update(v, v_left, v_right);
    }
    return sums[v];
  }
  unsigned int const get_segment(const size_t v, const size_t left,
                                 const size_t right, const size_t left_index,
                                 const size_t right_index) {
    if (right_index < left || right < left_index) return 0;
    unsigned int segment_sum = 0;
    if (left == left_index && right_index == right) {
      segment_sum = add(segment_sum, sums[v]);
      size_t v_size = v_sizes[v];
      segment_sum = add(segment_sum, get_sum(sum_matrixes[v_size], bases[v]));
    } else {
      size_t v_left = (v << 1);
      size_t v_right = (v_left + 1);
      size_t mid = ((left + right) >> 1);
      push(v, v_left, v_right);
      unsigned int left_sum =
          get_segment(v_left, left, mid, left_index, min(mid, right_index));
      unsigned int right_sum = get_segment(
          v_right, mid + 1, right, max(left_index, mid + 1), right_index);
      segment_sum = add(segment_sum, add(left_sum, right_sum));
      update(v, v_left, v_right);
    }
    return segment_sum;
  }

 public:
  Segment_tree(const vector<unsigned int>& array)
      : array_size(array.size()),
        tree_size(array_size << 2),
        v_sizes(tree_size),
        bases(tree_size),
        sums(tree_size),
        powers(array_size + 10),
        base_powers(powers.size()),
        sum_matrixes(powers.size()) {
    powers[0].values[0][0] = 1;
    powers[0].values[1][1] = 1;
    powers[1].values[0][0] = 1;
    powers[1].values[0][1] = 1;
    powers[1].values[1][0] = 1;
    for (size_t power = 2; power < powers.size(); ++power)
      powers[power] = powers[power - 1] * powers[1];
    for (size_t(power) = 0, __size = (powers.size()); (power) < __size;
         ++(power))
      base_powers[power] = multiply(powers[power], BASE);
    for (size_t power = 1; power < powers.size(); ++power)
      sum_matrixes[power] = sum_matrixes[power - 1] + powers[power - 1];
    build_tree(ROOT, 0, array_size - 1, array);
  }
  void add_segment(const size_t left, const size_t right) {
    add_segment(ROOT, 0, array_size - 1, left, right, 0);
  }
  unsigned int const get_segment(const size_t left, const size_t right) {
    unsigned int sum = get_segment(ROOT, 0, array_size - 1, left, right);
    return sum;
  }
};
const int ADD = 1, PRINT_SUM = 2;
int main() {
  const size_t n = read_int();
  size_t queries_count = read_int();
  vector<unsigned int> array(n);
  for (size_t(i) = 0, __size = (n); (i) < __size; ++(i)) array[i] = read_int();
  Segment_tree tree(array);
  while (queries_count-- > 0) {
    int operation = read_int();
    size_t left = read_int() - 1;
    size_t right = read_int() - 1;
    if (operation == ADD)
      tree.add_segment(left, right);
    else
      println(tree.get_segment(left, right));
  }
  return 0;
}
