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>
using namespace std;
const int N = 4e5 + 10;
inline int read() {
  char ch = getchar();
  int x = 0, f = 1;
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = (x << 1) + (x << 3) - '0' + ch;
    ch = getchar();
  }
  return x * f;
}
int n, m;
int p[N];
int val[N];
int size[N];
int find(int x) {
  if (x == p[x]) return x;
  return p[x] = find(p[x]);
}
int main() {
  n = read(), m = read();
  val[0] = 2e9;
  val[n + 1] = 2e9;
  for (int i = 1; i <= n + n; i++) p[i] = i, size[i] = 1;
  for (int i = 1; i <= n; i++) {
    val[i] = read();
    if (val[i] == val[i - 1]) {
      int x = find(i);
      int y = find(i - 1);
      p[x] = y;
      size[y] += size[x];
    }
  }
  while (m--) {
    int op = read(), x = read(), y = read();
    if (op == 1) {
      int fx = find(x);
      if (val[fx] < y) {
        p[x + 1] = x + 1;
        val[x + 1] = val[fx];
        size[x + 1] = size[fx] - (x - fx + 1);
        size[fx] -= size[x + 1];
      }
      while (val[fx] < y) {
        val[fx] = y;
        int tmp = find(p[fx - 1]);
        if (val[tmp] <= y) {
          size[tmp] += size[fx];
          p[fx] = tmp;
        }
        fx = tmp;
      }
    } else {
      int ans = 0;
      int fx = find(x);
      int l = x;
      int r = fx + size[fx] - 1;
      int x = val[fx];
      while (y > 0 && l <= n) {
        int tmp = min(y, (r - l + 1) * x);
        ans += tmp / x;
        y -= tmp / x * x;
        if (!y)
          break;
        else {
          l = find(r + 1);
          x = val[l];
          r = l + size[l] - 1;
        }
      }
      printf("%d\n", ans);
    }
  }
}
