You are given an array a_1, a_2, …, a_n of integers. This array is non-increasing.

Let's consider a line with n shops. The shops are numbered with integers from 1 to n from left to right. The cost of a meal in the i-th shop is equal to a_i.

You should process q queries of two types:

  * 1 x y: for each shop 1 ≤ i ≤ x set a_{i} = max(a_{i}, y). 
  * 2 x y: let's consider a hungry man with y money. He visits the shops from x-th shop to n-th and if he can buy a meal in the current shop he buys one item of it. Find how many meals he will purchase. The man can buy a meal in the shop i if he has at least a_i money, and after it his money decreases by a_i. 

Input

The first line contains two integers n, q (1 ≤ n, q ≤ 2 ⋅ 10^5).

The second line contains n integers a_{1},a_{2}, …, a_{n} (1 ≤ a_{i} ≤ 10^9) — the costs of the meals. It is guaranteed, that a_1 ≥ a_2 ≥ … ≥ a_n.

Each of the next q lines contains three integers t, x, y (1 ≤ t ≤ 2, 1≤ x ≤ n, 1 ≤ y ≤ 10^9), each describing the next query.

It is guaranteed that there exists at least one query of type 2.

Output

For each query of type 2 output the answer on the new line.

Example

Input


10 6
10 10 10 6 6 5 5 5 3 1
2 3 50
2 4 10
1 3 10
2 2 36
1 4 7
2 2 17


Output


8
3
6
2

Note

In the first query a hungry man will buy meals in all shops from 3 to 10.

In the second query a hungry man will buy meals in shops 4, 9, and 10.

After the third query the array a_1, a_2, …, a_n of costs won't change and will be \{10, 10, 10, 6, 6, 5, 5, 5, 3, 1\}.

In the fourth query a hungry man will buy meals in shops 2, 3, 4, 5, 9, and 10.

After the fifth query the array a of costs will be \{10, 10, 10, 7, 6, 5, 5, 5, 3, 1\}.

In the sixth query a hungry man will buy meals in shops 2 and 4.
1 1
5
2 1 6

1

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
void *wmem;
char memarr[96000000];
template <class S, class T>
inline S min_L(S a, T b) {
  return a <= b ? a : b;
}
template <class T>
inline void walloc1d(T **arr, int x, void **mem = &wmem) {
  static int skip[16] = {0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
  (*mem) = (void *)(((char *)(*mem)) + skip[((unsigned long long)(*mem)) & 15]);
  (*arr) = (T *)(*mem);
  (*mem) = ((*arr) + x);
}
template <class T>
inline void walloc1d(T **arr, int x1, int x2, void **mem = &wmem) {
  walloc1d(arr, x2 - x1, mem);
  (*arr) -= x1;
}
inline int my_getchar() {
  static char buf[1048576];
  static int s = 1048576;
  static int e = 1048576;
  if (s == e && e == 1048576) {
    e = fread(buf, 1, 1048576, stdin);
    s = 0;
  }
  if (s == e) {
    return EOF;
  }
  return buf[s++];
}
inline void rd(int &x) {
  int k;
  int m = 0;
  x = 0;
  for (;;) {
    k = my_getchar();
    if (k == '-') {
      m = 1;
      break;
    }
    if ('0' <= k && k <= '9') {
      x = k - '0';
      break;
    }
  }
  for (;;) {
    k = my_getchar();
    if (k < '0' || k > '9') {
      break;
    }
    x = x * 10 + k - '0';
  }
  if (m) {
    x = -x;
  }
}
struct MY_WRITER {
  char buf[1048576];
  int s;
  int e;
  MY_WRITER() {
    s = 0;
    e = 1048576;
  }
  ~MY_WRITER() {
    if (s) {
      fwrite(buf, 1, s, stdout);
    }
  }
};
MY_WRITER MY_WRITER_VAR;
void my_putchar(int a) {
  if (MY_WRITER_VAR.s == MY_WRITER_VAR.e) {
    fwrite(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);
    MY_WRITER_VAR.s = 0;
  }
  MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;
}
inline void wt_L(char a) { my_putchar(a); }
inline void wt_L(int x) {
  int s = 0;
  int m = 0;
  char f[10];
  if (x < 0) {
    m = 1;
    x = -x;
  }
  while (x) {
    f[s++] = x % 10;
    x /= 10;
  }
  if (!s) {
    f[s++] = 0;
  }
  if (m) {
    my_putchar('-');
  }
  while (s--) {
    my_putchar(f[s] + '0');
  }
}
template <class SVAL, class SFUN>
struct segtree_rh {
  int N;
  int logN;
  int trueN;
  SVAL *val;
  SFUN *fun;
  char *dofun;
  void malloc(int maxN, int once = 0);
  void walloc(int maxN, int once = 0, void **mem = &wmem);
  void free(void);
  SVAL &operator[](int i);
  void setN(int n, int zerofill = 1, int dobuild = 1);
  void build(void);
  inline void push_one(int a);
  inline void push(int a);
  inline void build(int a);
  inline void change(int a, int b, SFUN f);
  inline SVAL get(int a, int b);
  template <bool (*f)(SVAL)>
  int max_right(int a, int mx);
  template <bool (*f)(SVAL)>
  int max_right(int a);
  template <bool (*f)(SVAL)>
  int min_left(int b, int mn);
  template <bool (*f)(SVAL)>
  int min_left(int b);
};
int N;
int Q;
int T;
int X;
int Y;
int A[200000];
struct sval {
  int sz;
  long long sm;
  long long mn;
};
sval segtree_rh_merge(sval a, sval b) {
  return {a.sz + b.sz, a.sm + b.sm, min_L(a.mn, b.mn)};
}
sval segtree_rh_apply(long long f, sval a) { return {a.sz, a.sz * f, f}; }
long long segtree_rh_compose(long long f, long long g) { return f; }
bool search_min(sval a) { return a.mn >= Y; }
bool search_sum(sval a) { return a.sm <= Y; }
segtree_rh<sval, long long> t;
int main() {
  int FmcKpFmN;
  wmem = memarr;
  int i;
  int j;
  int k;
  long long v;
  sval tv;
  rd(N);
  rd(Q);
  {
    int KL2GvlyY;
    for (KL2GvlyY = (0); KL2GvlyY < (N); KL2GvlyY++) {
      rd(A[KL2GvlyY]);
    }
  }
  t.walloc(N);
  t.setN(N);
  for (i = (0); i < (N); i++) {
    t[i] = {1, A[i], A[i]};
  }
  t.build();
  for (FmcKpFmN = (0); FmcKpFmN < (Q); FmcKpFmN++) {
    rd(T);
    rd(X);
    X += (-1);
    rd(Y);
    if (T == 1) {
      i = t.max_right<search_min>(0, X);
      if (i + 1 < X + 1) {
        t.change(i + 1, X + 1, Y);
      }
    }
    if (T == 2) {
      int res = 0;
      while (X < N) {
        i = t.max_right<search_sum>(X);
        if (X < i) {
          Y -= t.get(X, i).sm;
        }
        res += i - X;
        X = i;
        i = t.max_right<search_min>(i);
        X = i;
      }
      wt_L(res);
      wt_L('\n');
    }
  }
  return 0;
}
template <class SVAL, class SFUN>
void segtree_rh<SVAL, SFUN>::malloc(int maxN, int once) {
  int i;
  for (i = 1; i < maxN; i *= 2) {
    ;
  }
  val = new SVAL[2 * i];
  fun = new SFUN[i];
  dofun = new char[i];
  if (once) {
    setN(maxN);
  }
}
template <class SVAL, class SFUN>
void segtree_rh<SVAL, SFUN>::walloc(int maxN, int once, void **mem) {
  int i;
  for (i = 1; i < maxN; i *= 2) {
    ;
  }
  walloc1d(&val, 2 * i, mem);
  walloc1d(&fun, i, mem);
  walloc1d(&dofun, i, mem);
  if (once) {
    setN(maxN);
  }
}
template <class SVAL, class SFUN>
void segtree_rh<SVAL, SFUN>::free(void) {
  delete[] val;
  delete[] fun;
}
template <class SVAL, class SFUN>
SVAL &segtree_rh<SVAL, SFUN>::operator[](int i) {
  return val[N + i];
}
template <class SVAL, class SFUN>
void segtree_rh<SVAL, SFUN>::setN(int n, int zerofill, int dobuild) {
  int i;
  for (i = 1, logN = 0; i < n; i *= 2, logN++) {
    ;
  }
  trueN = n;
  N = i;
  if (dobuild) {
    build();
  }
}
template <class SVAL, class SFUN>
void segtree_rh<SVAL, SFUN>::build(void) {
  int i;
  for (i = N - 1; i; i--) {
    val[i] = segtree_rh_merge(val[2 * i], val[2 * i + 1]);
  }
  int GgkpftXM = N;
  for (i = (1); i < (GgkpftXM); i++) {
    dofun[i] = 0;
  }
}
template <class SVAL, class SFUN>
inline void segtree_rh<SVAL, SFUN>::push_one(int a) {
  if (dofun[a]) {
    if (2 * a < N) {
      if (dofun[2 * a]) {
        fun[2 * a] = segtree_rh_compose(fun[a], fun[2 * a]);
      } else {
        fun[2 * a] = fun[a];
        dofun[2 * a] = 1;
      }
    }
    val[2 * a] = segtree_rh_apply(fun[a], val[2 * a]);
    if (2 * a + 1 < N) {
      if (dofun[2 * a + 1]) {
        fun[2 * a + 1] = segtree_rh_compose(fun[a], fun[2 * a + 1]);
      } else {
        fun[2 * a + 1] = fun[a];
        dofun[2 * a + 1] = 1;
      }
    }
    val[2 * a + 1] = segtree_rh_apply(fun[a], val[2 * a + 1]);
    dofun[a] = 0;
  }
}
template <class SVAL, class SFUN>
inline void segtree_rh<SVAL, SFUN>::push(int a) {
  int i;
  for (i = logN; i; i--) {
    push_one(a >> i);
  }
}
template <class SVAL, class SFUN>
inline void segtree_rh<SVAL, SFUN>::build(int a) {
  while (a > 1) {
    a /= 2;
    val[a] = segtree_rh_merge(val[2 * a], val[2 * a + 1]);
    if (dofun[a]) {
      val[a] = segtree_rh_apply(fun[a], val[a]);
    }
  }
}
template <class SVAL, class SFUN>
inline void segtree_rh<SVAL, SFUN>::change(int a, int b, SFUN f) {
  int aa;
  int bb;
  if (a >= b) {
    return;
  }
  aa = (a += N);
  bb = (b += N);
  push(a);
  push(b - 1);
  if (a % 2) {
    val[a] = segtree_rh_apply(f, val[a]);
    a++;
  }
  if (b % 2) {
    b--;
    val[b] = segtree_rh_apply(f, val[b]);
  }
  a /= 2;
  b /= 2;
  while (a < b) {
    if (a % 2) {
      val[a] = segtree_rh_apply(f, val[a]);
      if (dofun[a]) {
        fun[a] = segtree_rh_compose(f, fun[a]);
      } else {
        fun[a] = f;
        dofun[a] = 1;
      }
      a++;
    }
    if (b % 2) {
      b--;
      val[b] = segtree_rh_apply(f, val[b]);
      if (dofun[b]) {
        fun[b] = segtree_rh_compose(f, fun[b]);
      } else {
        fun[b] = f;
        dofun[b] = 1;
      }
    }
    a /= 2;
    b /= 2;
  }
  build(aa);
  build(bb - 1);
}
template <class SVAL, class SFUN>
inline SVAL segtree_rh<SVAL, SFUN>::get(int a, int b) {
  SVAL res;
  SVAL tmp;
  int fga = 0;
  int fgb = 0;
  a += N;
  b += N;
  push(a);
  push(b - 1);
  while (a < b) {
    if (a % 2) {
      if (fga) {
        res = segtree_rh_merge(res, val[a]);
      } else {
        res = val[a];
        fga = 1;
      }
      a++;
    }
    if (b % 2) {
      b--;
      if (fgb) {
        tmp = segtree_rh_merge(val[b], tmp);
      } else {
        tmp = val[b];
        fgb = 1;
      }
    }
    a /= 2;
    b /= 2;
  }
  if (fga == 1 && fgb == 0) {
    return res;
  }
  if (fga == 0 && fgb == 1) {
    return tmp;
  }
  if (fga == 1 && fgb == 1) {
    return segtree_rh_merge(res, tmp);
  }
  return res;
}
template <class SVAL, class SFUN>
template <bool (*f)(SVAL)>
int segtree_rh<SVAL, SFUN>::max_right(int a, int mx) {
  int fg = 0;
  int ta = a;
  int sz = 1;
  SVAL cur;
  SVAL tmp;
  if (a >= mx) {
    return mx;
  }
  a += N;
  push(a);
  for (;;) {
    while (a % 2 == 0) {
      a /= 2;
      sz *= 2;
    }
    if (ta + sz <= mx) {
      if (fg == 0) {
        tmp = val[a];
      } else {
        tmp = segtree_rh_merge(cur, val[a]);
      }
    }
    if (ta + sz > mx || !f(tmp)) {
      while (a < N) {
        push_one(a);
        a *= 2;
        sz /= 2;
        if (ta + sz <= mx) {
          if (fg == 0) {
            tmp = val[a];
          } else {
            tmp = segtree_rh_merge(cur, val[a]);
          }
        }
        if (ta + sz <= mx && f(tmp)) {
          fg = 1;
          cur = tmp;
          a++;
          ta += sz;
        }
      }
      return a - N;
    }
    fg = 1;
    cur = tmp;
    if ((a & (a + 1)) == 0) {
      break;
    }
    a++;
    ta += sz;
  }
  return mx;
}
template <class SVAL, class SFUN>
template <bool (*f)(SVAL)>
int segtree_rh<SVAL, SFUN>::max_right(int a) {
  return max_right<f>(a, trueN);
}
template <class SVAL, class SFUN>
template <bool (*f)(SVAL)>
int segtree_rh<SVAL, SFUN>::min_left(int b, int mn) {
  int fg = 0;
  int tb = b;
  int sz = 1;
  SVAL cur;
  SVAL tmp;
  if (b <= mn) {
    return mn;
  }
  b += N;
  push(b - 1);
  for (;;) {
    while (b % 2 == 0) {
      b /= 2;
      sz *= 2;
    }
    if (tb - sz >= mn) {
      if (fg == 0) {
        tmp = val[b - 1];
      } else {
        tmp = segtree_rh_merge(val[b - 1], cur);
      }
    }
    if (tb - sz < mn || !f(tmp)) {
      while (b - 1 < N) {
        push_one(b - 1);
        b *= 2;
        sz /= 2;
        if (tb - sz >= mn) {
          if (fg == 0) {
            tmp = val[b - 1];
          } else {
            tmp = segtree_rh_merge(val[b - 1], cur);
          }
        }
        if (tb - sz >= mn && f(tmp)) {
          fg = 1;
          cur = tmp;
          b--;
          tb -= sz;
        }
      }
      return b - N;
    }
    fg = 1;
    cur = tmp;
    b--;
    tb -= sz;
    if (tb <= mn) {
      break;
    }
  }
  return mn;
}
template <class SVAL, class SFUN>
template <bool (*f)(SVAL)>
int segtree_rh<SVAL, SFUN>::min_left(int b) {
  return min_left<f>(b, 0);
}
