#include <bits/stdc++.h>
using namespace std;
template <int p>
struct FF {
  long long val;
  FF(const long long x = 0) { val = (x % p + p) % p; }
  bool operator==(const FF<p>& other) const { return val == other.val; }
  bool operator!=(const FF<p>& other) const { return val != other.val; }
  FF operator+() const { return val; }
  FF operator-() const { return -val; }
  FF& operator+=(const FF<p>& other) {
    val = (val + other.val) % p;
    return *this;
  }
  FF& operator-=(const FF<p>& other) {
    *this += -other;
    return *this;
  }
  FF& operator*=(const FF<p>& other) {
    val = (val * other.val) % p;
    return *this;
  }
  FF operator+(const FF<p>& other) const { return FF(*this) += other; }
  FF operator-(const FF<p>& other) const { return FF(*this) -= other; }
  FF operator*(const FF<p>& other) const { return FF(*this) *= other; }
};
template <int p>
FF<p> operator+(const long long lhs, const FF<p>& rhs) {
  return FF<p>(lhs) += rhs;
}
template <int p>
FF<p> operator-(const long long lhs, const FF<p>& rhs) {
  return FF<p>(lhs) -= rhs;
}
template <int p>
FF<p> operator*(const long long lhs, const FF<p>& rhs) {
  return FF<p>(lhs) *= rhs;
}
int N, M;
FF<1000000009> f[300013], fp[300013];
FF<1000000009> st[(1 << 20)], lazy[(1 << 20)][2];
void push(int lo, int hi, int node) {
  int len = hi - lo + 1;
  int d = (lo + hi) / 2 + 1 - lo;
  if (lazy[node][0] != 0) {
    st[node] += lazy[node][0] * fp[len + 1];
    if (lo != hi) {
      lazy[2 * node + 1][0] += lazy[node][0];
      lazy[2 * node + 2][0] += lazy[node][0] * f[d + 1];
      lazy[2 * node + 2][1] += lazy[node][0] * f[d];
    }
    lazy[node][0] = 0;
  }
  if (lazy[node][1] != 0) {
    st[node] += lazy[node][1] * fp[len];
    if (lo != hi) {
      lazy[2 * node + 1][1] += lazy[node][1];
      lazy[2 * node + 2][0] += lazy[node][1] * f[d];
      lazy[2 * node + 2][1] += lazy[node][1] * f[d - 1];
    }
    lazy[node][1] = 0;
  }
}
void update_range(int s, int e, FF<1000000009> x, FF<1000000009> xp = 0,
                  int lo = 0, int hi = -1, int node = 0) {
  if (hi == -1) hi = N - 1;
  push(lo, hi, node);
  if (lo > e || hi < s) return;
  if (s <= lo && hi <= e) {
    int d = lo - s;
    lazy[node][0] = x * f[d + 1] + xp * f[d];
    lazy[node][1] = x * f[d] + (d ? xp * f[d - 1] : xp);
    push(lo, hi, node);
    return;
  }
  int mid = (lo + hi) / 2;
  update_range(s, e, x, xp, lo, mid, 2 * node + 1);
  update_range(s, e, x, xp, mid + 1, hi, 2 * node + 2);
  st[node] = st[2 * node + 1] + st[2 * node + 2];
}
FF<1000000009> query(int s, int e, int lo = 0, int hi = -1, int node = 0) {
  if (hi == -1) hi = N - 1;
  push(lo, hi, node);
  if (lo > e || hi < s) return 0;
  if (s <= lo && hi <= e) return st[node];
  int mid = (lo + hi) / 2;
  return query(s, e, lo, mid, 2 * node + 1) +
         query(s, e, mid + 1, hi, 2 * node + 2);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin >> N >> M;
  f[1] = 1;
  for (int i = 2; i <= N + 2; i++) {
    f[i] = f[i - 1] + f[i - 2];
    fp[i] = fp[i - 1] + f[i - 1];
  }
  for (int i = 0; i < N; i++) {
    int x;
    cin >> x;
    update_range(i, i, x);
  }
  while (M--) {
    int t, l, r;
    cin >> t >> l >> r;
    --l, --r;
    if (t == 1)
      update_range(l, r, 1);
    else
      cout << query(l, r).val << '\n';
  }
  cout.flush();
  return 0;
}

### Prompt

Please provide a cpp coded solution to the problem described below:

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.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
template <int p>
struct FF {
  long long val;
  FF(const long long x = 0) { val = (x % p + p) % p; }
  bool operator==(const FF<p>& other) const { return val == other.val; }
  bool operator!=(const FF<p>& other) const { return val != other.val; }
  FF operator+() const { return val; }
  FF operator-() const { return -val; }
  FF& operator+=(const FF<p>& other) {
    val = (val + other.val) % p;
    return *this;
  }
  FF& operator-=(const FF<p>& other) {
    *this += -other;
    return *this;
  }
  FF& operator*=(const FF<p>& other) {
    val = (val * other.val) % p;
    return *this;
  }
  FF operator+(const FF<p>& other) const { return FF(*this) += other; }
  FF operator-(const FF<p>& other) const { return FF(*this) -= other; }
  FF operator*(const FF<p>& other) const { return FF(*this) *= other; }
};
template <int p>
FF<p> operator+(const long long lhs, const FF<p>& rhs) {
  return FF<p>(lhs) += rhs;
}
template <int p>
FF<p> operator-(const long long lhs, const FF<p>& rhs) {
  return FF<p>(lhs) -= rhs;
}
template <int p>
FF<p> operator*(const long long lhs, const FF<p>& rhs) {
  return FF<p>(lhs) *= rhs;
}
int N, M;
FF<1000000009> f[300013], fp[300013];
FF<1000000009> st[(1 << 20)], lazy[(1 << 20)][2];
void push(int lo, int hi, int node) {
  int len = hi - lo + 1;
  int d = (lo + hi) / 2 + 1 - lo;
  if (lazy[node][0] != 0) {
    st[node] += lazy[node][0] * fp[len + 1];
    if (lo != hi) {
      lazy[2 * node + 1][0] += lazy[node][0];
      lazy[2 * node + 2][0] += lazy[node][0] * f[d + 1];
      lazy[2 * node + 2][1] += lazy[node][0] * f[d];
    }
    lazy[node][0] = 0;
  }
  if (lazy[node][1] != 0) {
    st[node] += lazy[node][1] * fp[len];
    if (lo != hi) {
      lazy[2 * node + 1][1] += lazy[node][1];
      lazy[2 * node + 2][0] += lazy[node][1] * f[d];
      lazy[2 * node + 2][1] += lazy[node][1] * f[d - 1];
    }
    lazy[node][1] = 0;
  }
}
void update_range(int s, int e, FF<1000000009> x, FF<1000000009> xp = 0,
                  int lo = 0, int hi = -1, int node = 0) {
  if (hi == -1) hi = N - 1;
  push(lo, hi, node);
  if (lo > e || hi < s) return;
  if (s <= lo && hi <= e) {
    int d = lo - s;
    lazy[node][0] = x * f[d + 1] + xp * f[d];
    lazy[node][1] = x * f[d] + (d ? xp * f[d - 1] : xp);
    push(lo, hi, node);
    return;
  }
  int mid = (lo + hi) / 2;
  update_range(s, e, x, xp, lo, mid, 2 * node + 1);
  update_range(s, e, x, xp, mid + 1, hi, 2 * node + 2);
  st[node] = st[2 * node + 1] + st[2 * node + 2];
}
FF<1000000009> query(int s, int e, int lo = 0, int hi = -1, int node = 0) {
  if (hi == -1) hi = N - 1;
  push(lo, hi, node);
  if (lo > e || hi < s) return 0;
  if (s <= lo && hi <= e) return st[node];
  int mid = (lo + hi) / 2;
  return query(s, e, lo, mid, 2 * node + 1) +
         query(s, e, mid + 1, hi, 2 * node + 2);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin >> N >> M;
  f[1] = 1;
  for (int i = 2; i <= N + 2; i++) {
    f[i] = f[i - 1] + f[i - 2];
    fp[i] = fp[i - 1] + f[i - 1];
  }
  for (int i = 0; i < N; i++) {
    int x;
    cin >> x;
    update_range(i, i, x);
  }
  while (M--) {
    int t, l, r;
    cin >> t >> l >> r;
    --l, --r;
    if (t == 1)
      update_range(l, r, 1);
    else
      cout << query(l, r).val << '\n';
  }
  cout.flush();
  return 0;
}

```