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>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update

using namespace std;
using namespace __gnu_pbds;

template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#ifdef LOCAL
#define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
#else
#define debug(...) ;
#endif

vector<string> vec_splitter(string s)
{
    s += ',';
    vector<string> res;
    while (!s.empty())
    {
        res.push_back(s.substr(0, s.find(',')));
        s = s.substr(s.find(',') + 1);
    }
    return res;
}

void debug_out(
        vector<string> __attribute__ ((unused)) args,
        __attribute__ ((unused)) int idx,
        __attribute__ ((unused)) int LINE_NUM)
{
    cerr << endl;
}

template<typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T)
{
    if (idx > 0)
        cerr << ", ";
    else
        cerr << "Line(" << LINE_NUM << ") ";
    stringstream ss;
    ss << H;
    cerr << args[idx] << " = " << ss.str();
    debug_out(args, idx + 1, LINE_NUM, T...);
}

typedef long long ll;
typedef double ld;
#define rep(i, start, end) for(int i = start; i < end; ++i)
#define sz(x) (int)((x).size())
#define pb push_back
#define all(x) x.begin(), x.end()
#define clr(d, v) memset(d, v, sizeof(d))
#define pii pair<int, int>
#define X first
#define Y second
//#define debug(x) cerr << #x << " : " << (x) << " "
const long double PI = 3.14159265358979323846;
const long double eps = (1e-15);
enum
{
    LESS, EQUAL, GREATER
};

int dcmp(ld x, ld y, ld EPS = eps)
{
    if (fabs(x - y) <= EPS)
        return EQUAL;
    return x > y ? GREATER : LESS;
}

const int MAX_N = 2e5 + 5;
#define left(x) ((x<<1))
#define right(x) ((x<<1) + 1)
int n, q, arr[MAX_N];

struct Node
{
    ll sum;
    ll mn, mx, lazy;

    Node(ll sum = 0, ll mn = 0, ll mx = 0, ll lazy = 0) : sum(sum), mn(mn), mx(mx), lazy(lazy)
    {

    }

    Node operator+(const Node &other) const
    {
        return {sum + other.sum, min(mn, other.mn), max(mx, other.mx), 0};
    }
} t[4 * MAX_N];

void push(int p, int l, int r)
{
    if (t[p].lazy)
    {
        t[p].mn = t[p].lazy;
        t[p].mx = t[p].lazy;
        t[p].sum = 1LL * (r - l + 1) * t[p].lazy;
        if (l != r)
        {
            t[left(p)].lazy = t[p].lazy;
            t[right(p)].lazy = t[p].lazy;
        }
        t[p].lazy = 0;
    }
}

void Set(int stq, int enq, int v, int p = 1, int l = 0, int r = n - 1)
{
    if (l >= stq && r <= enq)
    {
        t[p].lazy = v;
        push(p, l, r);
        return;
    }
    push(p, l, r);
    if (l > enq || r < stq)
        return;
    int mid = (l + r) / 2;
    Set(stq, enq, v, left(p), l, mid);
    Set(stq, enq, v, right(p), mid + 1, r);
    t[p] = t[left(p)] + t[right(p)];
}

int findFirstLessThanOrEqual(int stq, int enq, ll v, int p = 1, int l = 0, int r = n - 1)
{
    push(p, l, r);
    if (l > enq || r < stq || t[p].mn > v)
        return n;
    if (l == r)
        return l;
    int mid = (l + r) / 2;
    int ans = findFirstLessThanOrEqual(stq, enq, v, left(p), l, mid);
    if (ans == n)
        ans = findFirstLessThanOrEqual(stq, enq, v, right(p), mid + 1, r);
    return ans;
}

int findLastWithSumLessThanOrEqual(ll v, int p = 1, int l = 0, int r = n - 1)
{
    push(p, l, r);
    if (t[p].sum <= v)
        return r;
    if (t[p].mx > v)
        return l - 1;
    int mid = (l + r) / 2;
    if (t[left(p)].sum < v)
        return findLastWithSumLessThanOrEqual(v - t[left(p)].sum, right(p), mid + 1, r);
    return findLastWithSumLessThanOrEqual(v, left(p), l, mid);
}

ll sum(int stq, int enq, int p = 1, int l = 0, int r = n - 1)
{
    push(p, l, r);
    if (l >= stq && r <= enq)
        return t[p].sum;
    if (l > enq || r < stq)
        return 0;
    int mid = (l + r) / 2;
    return sum(stq, enq, left(p), l, mid) + sum(stq, enq, right(p), mid + 1, r);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
#endif
    cin >> n >> q;
    rep(i, 0, n)
    {
        cin >> arr[i];
        Set(i, i, arr[i]);
    }
//    Set(0, n - 2, 2);
//    cerr << sum(0, n - 1) << endl;
    while (q--)
    {
        int type, x;
        ll y;
        cin >> type >> x >> y;
        --x;
        if (type == 1)
        {
            int i = findFirstLessThanOrEqual(0, x, y);
            if (i <= x)
                Set(i, x, y);
        }
        else
        {
            int ans = 0;
            while (x < n)
            {
                x = findFirstLessThanOrEqual(x, n - 1, y);
                if (x == n)
                    break;
                int to = findLastWithSumLessThanOrEqual(y + (x ? sum(0, x - 1) : 0));
                y -= sum(x, to);
//                assert(y >= 0);
                to++;
//                if (to <= x)
//                    break;
                ans += to - x;
                x = to;
            }
            cout << ans << '\n';
        }
    }
}