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 MN = 300111;
const long long MOD = 1000000009;
struct Matrix {
  int m, n;
  long long x[3][3];
} matf[30], mats[30], I[4];
struct Node {
  long long sum, f0, f1;
} it[MN * 6];
long long a[MN];
Matrix operator*(const Matrix &a, const Matrix &b) {
  Matrix c;
  c.m = a.m;
  c.n = b.n;
  for (int i = 0, _a = (c.m); i < _a; i++)
    for (int j = 0, _a = (c.n); j < _a; j++) {
      c.x[i][j] = 0;
      for (int k = 0, _a = (a.n); k < _a; k++) {
        c.x[i][j] += a.x[i][k] * (long long)b.x[k][j];
      }
      c.x[i][j] %= MOD;
    }
  return c;
}
int cache[1000111];
void initMatrix() {
  for (int t = 0, _a = (4); t < _a; t++) {
    I[t].m = I[t].n = t;
    for (int i = 0, _a = (t); i < _a; i++)
      for (int j = 0, _a = (t); j < _a; j++)
        if (i == j)
          I[t].x[i][j] = 1;
        else
          I[t].x[i][j] = 0;
  }
  matf[0].m = matf[0].n = 2;
  matf[0].x[0][0] = 0;
  matf[0].x[0][1] = 1;
  matf[0].x[1][0] = 1;
  matf[0].x[1][1] = 1;
  mats[0].m = mats[0].n = 3;
  mats[0].x[0][0] = 0;
  mats[0].x[0][1] = 1;
  mats[0].x[0][2] = 0;
  mats[0].x[1][0] = 1;
  mats[0].x[1][1] = 1;
  mats[0].x[1][2] = 0;
  mats[0].x[2][0] = 1;
  mats[0].x[2][1] = 1;
  mats[0].x[2][2] = 1;
  for (int i = (1), _b = (29); i <= _b; i++) {
    matf[i] = matf[i - 1] * matf[i - 1];
    mats[i] = mats[i - 1] * mats[i - 1];
  }
  for (int u = 0, _a = (1000000); u < _a; u++) {
    for (int i = 0, _a = (20); i < _a; i++)
      if (u & (1 << i)) {
        cache[u] = i;
        break;
      }
  }
}
Matrix cachePower[3][300111];
bool hasCache[3][300111];
Matrix power(int t, int k) {
  if (hasCache[t][k]) return cachePower[t][k];
  hasCache[t][k] = true;
  Matrix res;
  if (t == 0)
    res = I[matf[0].m];
  else
    res = I[mats[0].m];
  int savek = k;
  while (k) {
    int i = cache[k];
    k -= 1 << i;
    if (t == 0)
      res = res * matf[i];
    else
      res = res * mats[i];
  }
  cachePower[t][savek] = res;
  return res;
}
inline long long add(long long x, long long y) {
  long long res = x + y;
  if (res >= MOD) res -= MOD;
  return res;
}
void init(int i, int l, int r) {
  if (l == r) {
    it[i].sum = a[l];
    it[i].f0 = it[i].f1 = 0;
    return;
  }
  int mid = (l + r) >> 1;
  init(((i) << 1), l, mid);
  init((((i) << 1) + 1), mid + 1, r);
  it[i].sum = add(it[((i) << 1)].sum, it[(((i) << 1) + 1)].sum);
}
Matrix cur;
inline long long getSum(long long f0, long long f1, int k) {
  cur = power(1, k);
  return ((cur.x[2][0] * f0 + cur.x[2][1] * f1) % MOD +
          cur.x[2][2] * (f0 + f1)) %
         MOD;
}
inline void put(int i, int l, int r, long long f0, long long f1) {
  if (l == r) {
    it[i].sum = add(it[i].sum, f0);
  } else {
    it[i].sum = add(it[i].sum, getSum(f0, f1, r - l - 1));
    it[i].f0 = add(it[i].f0, f0);
    it[i].f1 = add(it[i].f1, f1);
  }
}
inline pair<long long, long long> getK(long long f0, long long f1, int k) {
  if (k == 0) return make_pair(f0, f1);
  cur = power(0, k);
  return make_pair((cur.x[0][0] * f0 + cur.x[0][1] * f1) % MOD,
                   (cur.x[1][0] * f0 + cur.x[1][1] * f1) % MOD);
}
void down(int i, int l, int r, int mid) {
  if (it[i].f0 || it[i].f1) {
    pair<long long, long long> ff = getK(it[i].f0, it[i].f1, mid - l + 1);
    put(((i) << 1), l, mid, it[i].f0, it[i].f1);
    put((((i) << 1) + 1), mid + 1, r, ff.first, ff.second);
    it[i].f0 = it[i].f1 = 0;
  }
}
void update(int i, int l, int r, int u, int v) {
  if (v < l || r < u) return;
  if (u <= l && r <= v) {
    pair<long long, long long> ff = getK(1, 1, l - u);
    put(i, l, r, ff.first, ff.second);
    return;
  }
  int mid = (l + r) >> 1;
  down(i, l, r, mid);
  update(((i) << 1), l, mid, u, v);
  update((((i) << 1) + 1), mid + 1, r, u, v);
  it[i].sum = add(it[((i) << 1)].sum, it[(((i) << 1) + 1)].sum);
}
long long get(int i, int l, int r, int u, int v) {
  if (v < l || r < u) return 0;
  if (u <= l && r <= v) return it[i].sum;
  int mid = (l + r) >> 1;
  down(i, l, r, mid);
  return add(get(((i) << 1), l, mid, u, v),
             get((((i) << 1) + 1), mid + 1, r, u, v));
}
int INP, AM, REACHEOF;
char BUF[(1 << 12) + 1], *inp = BUF;
int main() {
  initMatrix();
  int n, q;
  {
    AM = 0;
    {
      if (!*inp) {
        if (REACHEOF) return 0;
        memset(BUF, 0, sizeof BUF);
        int inpzzz = fread(BUF, 1, (1 << 12), stdin);
        if (inpzzz != (1 << 12)) REACHEOF = true;
        inp = BUF;
      }
      INP = *inp++;
    };
    while (!(((INP) >= '0') && ((INP) <= '9')) && INP != '-') {
      if (!*inp) {
        if (REACHEOF) return 0;
        memset(BUF, 0, sizeof BUF);
        int inpzzz = fread(BUF, 1, (1 << 12), stdin);
        if (inpzzz != (1 << 12)) REACHEOF = true;
        inp = BUF;
      }
      INP = *inp++;
    };
    if (INP == '-') {
      AM = 1;
      {
        if (!*inp) {
          if (REACHEOF) return 0;
          memset(BUF, 0, sizeof BUF);
          int inpzzz = fread(BUF, 1, (1 << 12), stdin);
          if (inpzzz != (1 << 12)) REACHEOF = true;
          inp = BUF;
        }
        INP = *inp++;
      };
    }
    n = INP - '0';
    {
      if (!*inp) {
        if (REACHEOF) return 0;
        memset(BUF, 0, sizeof BUF);
        int inpzzz = fread(BUF, 1, (1 << 12), stdin);
        if (inpzzz != (1 << 12)) REACHEOF = true;
        inp = BUF;
      }
      INP = *inp++;
    };
    while ((((INP) >= '0') && ((INP) <= '9'))) {
      n = 10 * n + (INP - '0');
      {
        if (!*inp) {
          if (REACHEOF) return 0;
          memset(BUF, 0, sizeof BUF);
          int inpzzz = fread(BUF, 1, (1 << 12), stdin);
          if (inpzzz != (1 << 12)) REACHEOF = true;
          inp = BUF;
        }
        INP = *inp++;
      };
    }
    if (AM) n = -n;
  };
  {
    AM = 0;
    {
      if (!*inp) {
        if (REACHEOF) return 0;
        memset(BUF, 0, sizeof BUF);
        int inpzzz = fread(BUF, 1, (1 << 12), stdin);
        if (inpzzz != (1 << 12)) REACHEOF = true;
        inp = BUF;
      }
      INP = *inp++;
    };
    while (!(((INP) >= '0') && ((INP) <= '9')) && INP != '-') {
      if (!*inp) {
        if (REACHEOF) return 0;
        memset(BUF, 0, sizeof BUF);
        int inpzzz = fread(BUF, 1, (1 << 12), stdin);
        if (inpzzz != (1 << 12)) REACHEOF = true;
        inp = BUF;
      }
      INP = *inp++;
    };
    if (INP == '-') {
      AM = 1;
      {
        if (!*inp) {
          if (REACHEOF) return 0;
          memset(BUF, 0, sizeof BUF);
          int inpzzz = fread(BUF, 1, (1 << 12), stdin);
          if (inpzzz != (1 << 12)) REACHEOF = true;
          inp = BUF;
        }
        INP = *inp++;
      };
    }
    q = INP - '0';
    {
      if (!*inp) {
        if (REACHEOF) return 0;
        memset(BUF, 0, sizeof BUF);
        int inpzzz = fread(BUF, 1, (1 << 12), stdin);
        if (inpzzz != (1 << 12)) REACHEOF = true;
        inp = BUF;
      }
      INP = *inp++;
    };
    while ((((INP) >= '0') && ((INP) <= '9'))) {
      q = 10 * q + (INP - '0');
      {
        if (!*inp) {
          if (REACHEOF) return 0;
          memset(BUF, 0, sizeof BUF);
          int inpzzz = fread(BUF, 1, (1 << 12), stdin);
          if (inpzzz != (1 << 12)) REACHEOF = true;
          inp = BUF;
        }
        INP = *inp++;
      };
    }
    if (AM) q = -q;
  };
  for (int i = (1), _b = (n); i <= _b; i++) {
    AM = 0;
    {
      if (!*inp) {
        if (REACHEOF) return 0;
        memset(BUF, 0, sizeof BUF);
        int inpzzz = fread(BUF, 1, (1 << 12), stdin);
        if (inpzzz != (1 << 12)) REACHEOF = true;
        inp = BUF;
      }
      INP = *inp++;
    };
    while (!(((INP) >= '0') && ((INP) <= '9')) && INP != '-') {
      if (!*inp) {
        if (REACHEOF) return 0;
        memset(BUF, 0, sizeof BUF);
        int inpzzz = fread(BUF, 1, (1 << 12), stdin);
        if (inpzzz != (1 << 12)) REACHEOF = true;
        inp = BUF;
      }
      INP = *inp++;
    };
    if (INP == '-') {
      AM = 1;
      {
        if (!*inp) {
          if (REACHEOF) return 0;
          memset(BUF, 0, sizeof BUF);
          int inpzzz = fread(BUF, 1, (1 << 12), stdin);
          if (inpzzz != (1 << 12)) REACHEOF = true;
          inp = BUF;
        }
        INP = *inp++;
      };
    }
    a[i] = INP - '0';
    {
      if (!*inp) {
        if (REACHEOF) return 0;
        memset(BUF, 0, sizeof BUF);
        int inpzzz = fread(BUF, 1, (1 << 12), stdin);
        if (inpzzz != (1 << 12)) REACHEOF = true;
        inp = BUF;
      }
      INP = *inp++;
    };
    while ((((INP) >= '0') && ((INP) <= '9'))) {
      a[i] = 10 * a[i] + (INP - '0');
      {
        if (!*inp) {
          if (REACHEOF) return 0;
          memset(BUF, 0, sizeof BUF);
          int inpzzz = fread(BUF, 1, (1 << 12), stdin);
          if (inpzzz != (1 << 12)) REACHEOF = true;
          inp = BUF;
        }
        INP = *inp++;
      };
    }
    if (AM) a[i] = -a[i];
  };
  memset(it, 0, sizeof it);
  init(1, 1, n);
  while (q--) {
    int typ, u, v;
    {
      AM = 0;
      {
        if (!*inp) {
          if (REACHEOF) return 0;
          memset(BUF, 0, sizeof BUF);
          int inpzzz = fread(BUF, 1, (1 << 12), stdin);
          if (inpzzz != (1 << 12)) REACHEOF = true;
          inp = BUF;
        }
        INP = *inp++;
      };
      while (!(((INP) >= '0') && ((INP) <= '9')) && INP != '-') {
        if (!*inp) {
          if (REACHEOF) return 0;
          memset(BUF, 0, sizeof BUF);
          int inpzzz = fread(BUF, 1, (1 << 12), stdin);
          if (inpzzz != (1 << 12)) REACHEOF = true;
          inp = BUF;
        }
        INP = *inp++;
      };
      if (INP == '-') {
        AM = 1;
        {
          if (!*inp) {
            if (REACHEOF) return 0;
            memset(BUF, 0, sizeof BUF);
            int inpzzz = fread(BUF, 1, (1 << 12), stdin);
            if (inpzzz != (1 << 12)) REACHEOF = true;
            inp = BUF;
          }
          INP = *inp++;
        };
      }
      typ = INP - '0';
      {
        if (!*inp) {
          if (REACHEOF) return 0;
          memset(BUF, 0, sizeof BUF);
          int inpzzz = fread(BUF, 1, (1 << 12), stdin);
          if (inpzzz != (1 << 12)) REACHEOF = true;
          inp = BUF;
        }
        INP = *inp++;
      };
      while ((((INP) >= '0') && ((INP) <= '9'))) {
        typ = 10 * typ + (INP - '0');
        {
          if (!*inp) {
            if (REACHEOF) return 0;
            memset(BUF, 0, sizeof BUF);
            int inpzzz = fread(BUF, 1, (1 << 12), stdin);
            if (inpzzz != (1 << 12)) REACHEOF = true;
            inp = BUF;
          }
          INP = *inp++;
        };
      }
      if (AM) typ = -typ;
    };
    {
      AM = 0;
      {
        if (!*inp) {
          if (REACHEOF) return 0;
          memset(BUF, 0, sizeof BUF);
          int inpzzz = fread(BUF, 1, (1 << 12), stdin);
          if (inpzzz != (1 << 12)) REACHEOF = true;
          inp = BUF;
        }
        INP = *inp++;
      };
      while (!(((INP) >= '0') && ((INP) <= '9')) && INP != '-') {
        if (!*inp) {
          if (REACHEOF) return 0;
          memset(BUF, 0, sizeof BUF);
          int inpzzz = fread(BUF, 1, (1 << 12), stdin);
          if (inpzzz != (1 << 12)) REACHEOF = true;
          inp = BUF;
        }
        INP = *inp++;
      };
      if (INP == '-') {
        AM = 1;
        {
          if (!*inp) {
            if (REACHEOF) return 0;
            memset(BUF, 0, sizeof BUF);
            int inpzzz = fread(BUF, 1, (1 << 12), stdin);
            if (inpzzz != (1 << 12)) REACHEOF = true;
            inp = BUF;
          }
          INP = *inp++;
        };
      }
      u = INP - '0';
      {
        if (!*inp) {
          if (REACHEOF) return 0;
          memset(BUF, 0, sizeof BUF);
          int inpzzz = fread(BUF, 1, (1 << 12), stdin);
          if (inpzzz != (1 << 12)) REACHEOF = true;
          inp = BUF;
        }
        INP = *inp++;
      };
      while ((((INP) >= '0') && ((INP) <= '9'))) {
        u = 10 * u + (INP - '0');
        {
          if (!*inp) {
            if (REACHEOF) return 0;
            memset(BUF, 0, sizeof BUF);
            int inpzzz = fread(BUF, 1, (1 << 12), stdin);
            if (inpzzz != (1 << 12)) REACHEOF = true;
            inp = BUF;
          }
          INP = *inp++;
        };
      }
      if (AM) u = -u;
    };
    {
      AM = 0;
      {
        if (!*inp) {
          if (REACHEOF) return 0;
          memset(BUF, 0, sizeof BUF);
          int inpzzz = fread(BUF, 1, (1 << 12), stdin);
          if (inpzzz != (1 << 12)) REACHEOF = true;
          inp = BUF;
        }
        INP = *inp++;
      };
      while (!(((INP) >= '0') && ((INP) <= '9')) && INP != '-') {
        if (!*inp) {
          if (REACHEOF) return 0;
          memset(BUF, 0, sizeof BUF);
          int inpzzz = fread(BUF, 1, (1 << 12), stdin);
          if (inpzzz != (1 << 12)) REACHEOF = true;
          inp = BUF;
        }
        INP = *inp++;
      };
      if (INP == '-') {
        AM = 1;
        {
          if (!*inp) {
            if (REACHEOF) return 0;
            memset(BUF, 0, sizeof BUF);
            int inpzzz = fread(BUF, 1, (1 << 12), stdin);
            if (inpzzz != (1 << 12)) REACHEOF = true;
            inp = BUF;
          }
          INP = *inp++;
        };
      }
      v = INP - '0';
      {
        if (!*inp) {
          if (REACHEOF) return 0;
          memset(BUF, 0, sizeof BUF);
          int inpzzz = fread(BUF, 1, (1 << 12), stdin);
          if (inpzzz != (1 << 12)) REACHEOF = true;
          inp = BUF;
        }
        INP = *inp++;
      };
      while ((((INP) >= '0') && ((INP) <= '9'))) {
        v = 10 * v + (INP - '0');
        {
          if (!*inp) {
            if (REACHEOF) return 0;
            memset(BUF, 0, sizeof BUF);
            int inpzzz = fread(BUF, 1, (1 << 12), stdin);
            if (inpzzz != (1 << 12)) REACHEOF = true;
            inp = BUF;
          }
          INP = *inp++;
        };
      }
      if (AM) v = -v;
    };
    if (typ == 1) {
      update(1, 1, n, u, v);
    } else {
      printf("%d\n", (int)get(1, 1, n, u, v));
    }
  }
  return 0;
}
