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 = 30+5;
typedef long long ll;
struct node{
    ll sum;
    ll mx;
    ll mv; 
};
int n,q;
ll arr[N];
ll lazy[N<<2];
node tree[N<<2];
typedef pair<int,int> pii;
void build(int l,int r,int rt){
    if(l==r){
        tree[rt].sum=tree[rt].mv=tree[rt].mx=arr[l];
    }else{
        int mid =l+r>>1;
        build(l,mid,rt<<1);
        build(mid+1,r,rt<<1|1);
        tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;
        tree[rt].mv=min(tree[rt<<1].mv,tree[rt<<1|1].mv);
        tree[rt].mx=max(tree[rt<<1].mx,tree[rt<<1|1].mx);
    }
}
void push_down(int rt,int l,int r){
    int ls=rt<<1,rs=rt<<1|1,mid=l+r>>1;
    if(lazy[rt]){
        tree[ls].mv=tree[ls].mx=tree[rs].mv=tree[rs].mx=lazy[rt];
        tree[ls].sum=(mid-l+1)*lazy[rt];
        tree[rs].sum=(r-mid)*lazy[rt];
        lazy[rt]=0;
    }
}

void push_up(int rt){
    tree[rt].mv=min(tree[rt<<1].mv,tree[rt<<1|1].mv);
    tree[rt].mx=max(tree[rt<<1].mx,tree[rt<<1|1].mx);
    tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;
}
void update(int l,int r,int rt,int ul,int ur,int v){
    if(ul <= l && ur >= r){
        if(tree[rt].mv >= v)return;
        if(tree[rt].mx <= v){
            tree[rt].mv=tree[rt].mx=v;
            tree[rt].sum=(r-l+1)*v;
            lazy[rt]=v;
            return;
        }else{
            int mid=l+r>>1;
            update(l,mid,rt<<1,l,mid,v);
            update(mid+1,r,rt<<1|1,mid+1,r,v);
        }
    }else{
        int mid=l+r>>1;
        push_down(rt,l,r);
        if(ul<=mid){
            update(l,mid,rt<<1,ul,ur,v);
        }
        if(ur>mid){
            update(mid+1,r,rt<<1|1,ul,ur,v);
        }
        push_up(rt);
    }
}
ll query_mx(int l,int r,int rt,int ul,int ur){
    if(ul<=l&&ur>=r){
        return tree[rt].mx;
    }else{
        push_down(rt,l,r);
        int mid=l+r>>1;
        ll ans=0;
        if(ul<=mid){
            ans=query_mx(l,mid,rt<<1,ul,ur);
        }
        if(ur>mid){
            ans=max(ans,query_mx(mid+1,r,rt<<1|1,ul,ur));
        }
        return ans;
    }
}

ll query_sum(int l,int r,int rt,int ul,int ur){
    if(ul<=l&&ur>=r){
        return tree[rt].sum;
    }else{
        push_down(rt,l,r);
        int mid=l+r>>1;
        ll ans=0;
        if(ul<=mid){
            ans+=query_sum(l,l+r>>1,rt<<1,ul,ur);
        }
        if(ur>mid){
            ans+=query_sum(mid+1,r,rt<<1|1,ul,ur);
        }
        return ans;
    }
}

pii getx(int x,ll&total){
    int l=x,r=n;
    int bg=0;
    ll p=0;
    while(l<r){
        int mid=l+r>>1;
        p = query_mx(1,n,1,mid,n);
        if(p > total){
            l=mid+1;
        }else{
            r=mid;
        }
    }
    if(l==n&&p>total)return make_pair(-1,-1);
    else{
        bg=l;
        r=n;
        while(l<r){
            int mid=l+r>>1;
            p=query_sum(1,n,1,l,mid);
            if(p <= total){
                if(l==mid)break;
                l=mid;
            }else{
                r=mid-1;
            }
        }

        ll tt = query_sum(1,n,1,bg,r);
        if(tt<=total){
            l=r;
            total -= tt;
        }else{
            total-=query_sum(1,n,1,bg,l);
        }
        return make_pair(bg,l);
    }
}
int main(){
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++){
        scanf("%lld",&arr[i]);
    }
    build(1,n,1);
    int a,b;
    ll c;
    while(q--){
        scanf("%d%d%lld",&a,&b,&c);
        if(a==1){
            update(1,n,1,1,b,c);
        }else{
            int v = 0;
            while(c){
                pii x = getx(b,c);
                if(x.first==-1)break;
                v += x.second-x.first+1;
                b=x.second+1;
                if(b>n)break;
            }
            printf("%d\n",v);
        }
    }

    // system("pause");
    return 0;
}
