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 maxarr(vector<int> &arr);
int minarr(vector<int> &arr);
long long modulo(long long base, long long exponent, long long modulus);
long long choose(long long n, long long k);
bool isprime(long long n);
long long inverse(long long a, long long m);
long long fastmult(long long a, long long b, long long c);
vector<long long> a(300005);
vector<long long> prime;
long long sum[300005];
vector<bool> aprime(300005);
void setprime();
long long divCeil(long long a, long long b);
long long arrceil(vector<long long> a, long long k);
long long prefixsum[300005];
long long fibosum[300005];
long long mark[300005];
long long LL[300005];
long long RR[300005];
inline long long scan() {
  char c = getchar();
  long long x = 0;
  while (c < '0' || c > '9') {
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = (x << 1) + (x << 3) + c - '0';
    c = getchar();
  }
  return x;
}
void intialize() {
  fibosum[0] = 0;
  fibosum[1] = 1;
  long long a = 0;
  long long b = 1;
  long long c;
  for (int i = 2; i < 300005; i++) {
    c = a + b;
    c %= 1000000009;
    a = b;
    b = c;
    fibosum[i] = (fibosum[i - 1] + c) % 1000000009;
  }
}
int main() {
  intialize();
  long long n, q;
  n = scan();
  q = scan();
  for (int i = 1; i < n + 1; i++) {
    long long temp;
    temp = scan();
    prefixsum[i] = (prefixsum[i - 1] + temp) % 1000000009;
  }
  long long sqn = 600;
  long long sz = 0;
  while (q--) {
    if (sz == sqn) {
      prefixsum[1] += mark[1];
      if (prefixsum[1] < 0) prefixsum[1] += 1000000009;
      prefixsum[1] %= 1000000009;
      long long sum = mark[1];
      if (sum < 0) sum += 1000000009;
      sum %= 1000000009;
      for (int i = 2; i < n + 1; i++) {
        mark[i] += (mark[i - 1] + mark[i - 2]);
        if (mark[i] < 0) mark[i] += 1000000009;
        mark[i] %= 1000000009;
        sum += mark[i];
        if (sum < 0) sum += 1000000009;
        sum %= 1000000009;
        prefixsum[i] += (sum);
        if (prefixsum[i] < 0) prefixsum[i] += 1000000009;
        prefixsum[i] %= 1000000009;
        mark[i - 2] = 0;
      }
      mark[n] = 0;
      mark[n - 1] = 0;
      sz = 0;
    }
    long long type, l, r;
    type = scan();
    l = scan();
    r = scan();
    if (type == 1) {
      mark[l]++;
      mark[r + 1] -= (fibosum[r - l + 2] - fibosum[r - l + 1]);
      mark[r + 2] -= (fibosum[r - l + 1] - fibosum[r - l]);
      if (mark[r + 1] < 0) mark[r + 1] += 1000000009;
      if (mark[r + 2] < 0) mark[r + 2] += 1000000009;
      mark[r + 1] %= 1000000009;
      mark[r + 2] %= 1000000009;
      LL[sz] = l;
      RR[sz] = r;
      sz++;
    } else {
      long long ans = 0;
      ans += prefixsum[r];
      ans -= prefixsum[l - 1];
      if (ans < 0) ans += 1000000009;
      ans %= 1000000009;
      for (int i = 0; i < sz; i++) {
        long long L = LL[i];
        long long R = RR[i];
        if (R < l || L > r)
          continue;
        else if (l <= L && R <= r)
          ans += fibosum[R - L + 1];
        else if (L <= l && R <= r)
          ans += fibosum[R - L + 1] - fibosum[l - L];
        else if (L >= l && R >= r)
          ans += fibosum[r - L + 1];
        else if (L <= l && r <= R)
          ans += fibosum[r - L + 1] - fibosum[l - L];
        if (ans < 0) ans += 1000000009;
        ans %= 1000000009;
      }
      printf("%lld\n", ans);
    }
  }
  return 0;
}
int maxarr(vector<int> &arr) {
  int maxi = INT_MIN;
  for (int i = 0; i < arr.size(); i++) maxi = max(arr[i], maxi);
  return maxi;
}
int minarr(vector<int> &arr) {
  int mini = INT_MAX;
  for (int i = 0; i < arr.size(); i++) mini = min(arr[i], mini);
  return mini;
}
long long modulo(long long base, long long exponent, long long modulus) {
  if (modulus == 1) return 0;
  long long result = 1;
  base = base % modulus;
  while (exponent > 0) {
    if (exponent % 2 == 1) {
      result = (result * base) % modulus;
    }
    exponent = exponent >> 1;
    base = (base * base) % modulus;
  }
  return result;
}
long long choose(long long n, long long k) {
  if (k == 0) return 1;
  return (n * choose(n - 1, k - 1)) / k;
}
bool isprime(long long n) {
  for (long long i = 2; i * i <= n; i++) {
    if (n % i == 0) return false;
  }
  return true;
}
void EE(long long a, long long b, long long &co1, long long &co2) {
  if (a % b == 0) {
    co1 = 0;
    co2 = 1;
    return;
  }
  EE(b, a % b, co1, co2);
  long long temp = co1;
  co1 = co2;
  co2 = temp - co2 * (a / b);
}
long long inverse(long long a, long long m) {
  long long x, y;
  EE(a, m, x, y);
  if (x < 0) x += m;
  return x;
}
long long fastmult(long long a, long long b, long long c) {
  if (b == 0) return 0;
  long long res = fastmult(a, b >> 1, c);
  res = (res + res) % c;
  if (b % 2 == 1) {
    res = (res + a) % c;
  }
  return res;
}
void setprime() {
  aprime[0] = true;
  for (int i = 2; i * i <= 300005; i++) {
    if (aprime[i - 1] == false) {
      for (int j = i * 2; j <= 300005; j += i) {
        aprime[j - 1] = true;
      }
    }
  }
}
long long divCeil(long long a, long long b) { return (a + b - 1) / b; }
long long arrceil(vector<long long> a, long long k) {
  long long n = a.size();
  long long low = 0;
  long long high = n - 1;
  if (a[0] > k) return -1;
  while (low < high) {
    long long mid = (low + high + 1) / 2;
    if (a[mid] <= k)
      low = mid;
    else
      high = mid - 1;
  }
  return low;
}
