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 comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("-Ofast", "-funroll-all-loops", "-ffast-math")
using namespace std;
const int N = 2 * 1e5 + 13;
long long t[4 * N][3], add[4 * N];
bool ok[4 * N];
long long n, q;
long long a[N];
void build(int v = 1, int tl = 0, int tr = n - 1) {
  if (tl == tr) {
    t[v][0] = t[v][1] = t[v][2] = a[tl];
    return;
  }
  int tm = (tl + tr) / 2;
  build(v << 1, tl, tm);
  build((v << 1) + 1, tm + 1, tr);
  t[v][0] = t[v << 1][0] + t[(v << 1) + 1][0];
  t[v][1] = min(t[v << 1][1], t[(v << 1) + 1][1]);
  t[v][2] = t[v << 1][2];
}
void push(long long v, long long tl, long long tr) {
  if (!ok[v]) {
    return;
  }
  if (tl == tr) {
    t[v][0] = t[v][1] = t[v][2] = add[v];
    ok[v] = false;
    return;
  }
  t[v][0] = add[v] * (tr - tl + 1);
  t[v][1] = add[v];
  t[v][2] = add[v];
  add[v << 1] = add[v];
  add[(v << 1) + 1] = add[v];
  ok[v << 1] = true;
  ok[(v << 1) + 1] = true;
  ok[v] = false;
}
void upd(int l, int r, long long val, int v = 1, int tl = 0, int tr = n - 1) {
  push(v, tl, tr);
  if (tl > r || tr < l) {
    return;
  }
  if (tl >= l && tr <= r) {
    add[v] = val;
    ok[v] = true;
    push(v, tl, tr);
    return;
  }
  int tm = (tl + tr) / 2;
  upd(l, r, val, v << 1, tl, tm);
  upd(l, r, val, (v << 1) + 1, tm + 1, tr);
  t[v][0] = t[v << 1][0] + t[(v << 1) + 1][0];
  t[v][1] = min(t[v << 1][1], t[(v << 1) + 1][1]);
  t[v][2] = t[v << 1][2];
}
long long get(int l, int r, int i, int v = 1, int tl = 0, int tr = n - 1) {
  push(v, tl, tr);
  if (tl > r || tr < l || l > r) {
    return (i == 0 ? 0ll : 1e17);
  }
  if (tl >= l && tr <= r) {
    return t[v][i];
  }
  int tm = (tl + tr) / 2;
  if (i == 0) {
    return get(l, r, i, v << 1, tl, tm) +
           get(l, r, i, (v << 1) + 1, tm + 1, tr);
  }
  return min(get(l, r, i, v << 1, tl, tm),
             get(l, r, i, (v << 1) + 1, tm + 1, tr));
}
inline long long get(int i, int j) { return get(i, i, j); }
int get_sum(long long s, int v = 1, int tl = 0, int tr = n - 1) {
  push(v, tl, tr);
  if (tl == tr) {
    return tl;
  }
  int tm = (tl + tr) / 2;
  push(v << 1, tl, tm);
  push((v << 1) + 1, tm + 1, tr);
  if (t[v << 1][0] + t[(v << 1) + 1][2] <= s && t[v << 1][0] < s) {
    return get_sum(s - t[v << 1][0], (v << 1) + 1, tm + 1, tr);
  }
  return get_sum(s, v << 1, tl, tm);
}
inline int last(int i, long long val) {
  long long s = get(0, i - 1, 0);
  return get_sum(s + val);
}
int get_next(long long val, int v = 1, int tl = 0, int tr = n - 1) {
  push(v, tl, tr);
  if (t[v][1] > val) {
    return n;
  }
  if (tl == tr) {
    if (t[v][0] > val) {
      tl++;
    }
    return tl;
  }
  int tm = (tl + tr) / 2;
  if (t[v << 1][1] <= val) {
    return get_next(val, v << 1, tl, tm);
  }
  return get_next(val, (v << 1) + 1, tm + 1, tr);
}
inline int nxt(int i, long long val) {
  int res = get_next(val);
  return max(i, res);
}
int main() {
  int _ = 1;
  while (_--) {
    scanf("%lld %lld", &n, &q);
    for (int i = 0; i < n; i++) {
      scanf("%lld", &a[i]);
    }
    build();
    while (q--) {
      long long type, x, y;
      scanf("%lld %lld %lld", &type, &x, &y);
      x--;
      int ans = 0;
      if (type - 1) {
        int cur = nxt(x, y);
        while (cur != n) {
          x = cur;
          cur = last(x, y);
          y -= get(x, cur, 0);
          ans += cur - x + 1;
          cur = nxt(cur + 1, y);
        }
        printf("%lld\n", ans);
      } else {
        int l = -1, r = n;
        while (r - l > 1) {
          int m = (l + r) / 2;
          if (get(m, 0) > y) {
            l = m;
          } else {
            r = m;
          }
        }
        if (r <= x) {
          upd(r, x, y);
        }
      }
    }
  }
}
