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

// Don't place your source in a package
import javax.swing.*;
import java.lang.reflect.Array;
import java.text.DecimalFormat;
import java.util.*;
import java.lang.*;
import java.io.*;
import java.math.*;
import java.util.stream.Stream;



// Please name your class Main
public class Main {
    static FastScanner fs=new FastScanner();
    static class FastScanner {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer("");
        public String next() {
            while (!st.hasMoreElements())
                try {
                    st=new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            return st.nextToken();
        }
        int Int() {
            return Integer.parseInt(next());
        }

        long Long() {
            return Long.parseLong(next());
        }

        String Str(){
            return next();
        }
    }


    public static void main (String[] args) throws java.lang.Exception {
        PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
        //reading /writing file
        //Scanner sc=new Scanner(new File("input.txt"));
        //PrintWriter pr=new PrintWriter("output.txt");


        int T=1;
        for(int t=0;t<T;t++){
            int n=Int();
            int m=Int();

            int A[]=Arr(n);
            int q[][]=new int[m][3];
            for(int i=0;i<q.length;i++){
                q[i][0]=Int();
                q[i][1]=Int()-1;
                q[i][2]=Int();
            }

            Solution sol=new Solution(out);
            sol.solution(A,q);
        }
        out.close();

    }

    public static int[] Arr(int n){
        int A[]=new int[n];
        for(int i=0;i<n;i++)A[i]=Int();
        return A;
    }
    public static int Int(){
        return fs.Int();
    }
    public static long Long(){
        return fs.Long();
    }
    public static String Str(){
        return fs.Str();
    }

}








class Solution{
    PrintWriter out;
    int INF=Integer.MAX_VALUE;
    int MOD=1000000007;
    public Solution(PrintWriter out){
        this.out=out;
    }

    Seg seg;
    int cnt=0;
    int money=0;
    int index=INF;
    public void solution(int A[],int q[][]){

        int n=A.length;
        seg=new Seg(0,n-1,A);

        for(int i=0;i<q.length;i++){
            int opt=q[i][0];
            if(opt==1){//update
                int r=q[i][1],val=q[i][2];
                index=INF;
                findmin(seg,r,val);
                if(index!=INF){
                    seg.update(index,r,val);
                }
            }
            else{//query
                int start=q[i][1];
                money=q[i][2];
                cnt=0;
                dfs(start,seg);
                out.println(cnt);
            }
        }

    }


    public void findmin(Seg root,int end,int val){
        int l=root.l;
        int r=root.r;
        if(l>end||l>r||index<=l){
            return;
        }

        if(l==r){
            if(root.min()<val){
                index=Math.min(index,l);
            }
            return;
        }

        int mid=l+(r-l)/2;
        if(root.min()>=val){
            return;
        }
        else{
            index=Math.min(index,r);
        }

        if(root.setTo!=-1){
            root.left.update(l,mid,root.setTo);
            root.right.update(mid+1,r,root.setTo);
            root.min=Math.min(root.left.min,root.right.min);
            root.max=Math.max(root.left.max,root.right.max);
            root.sum=root.left.sum+root.right.sum;
            root.setTo=-1;
        }

        findmin(root.left,end,val);
        findmin(root.right,end,val);
    }

    public void dfs(int start,Seg root){
        int l=root.l;
        int r=root.r;
        if(r<start){
            return;
        }
        if(l==r){
            if(money>=root.sum()){
                money-=root.sum();
                cnt++;
            }
            return;
        }

        int mid=l+(r-l)/2;

        if(money>=root.sum()&&l>=start){
            cnt+=(r-l+1);
            money-=root.sum();
            return;
        }

        if(money<root.min()){
            return;
        }

        if(root.setTo!=-1){
            root.left.update(l,mid,root.setTo);
            root.right.update(mid+1,r,root.setTo);
            root.min=Math.min(root.left.min,root.right.min);
            root.max=Math.max(root.left.max,root.right.max);
            root.sum=root.left.sum+root.right.sum;
            root.setTo=-1;
        }

        dfs(start,root.left);
        dfs(start,root.right);
    }



    class Seg{
        int l,r;
        int min=Integer.MAX_VALUE;
        int max=Integer.MIN_VALUE;
        long sum=0;
        int setTo=-1;
        Seg left=null,right=null;
        public Seg(int l,int r,int A[]){
            this.l=l;
            this.r=r;
            if(l!=r){
                int mid=l+(r-l)/2;
                if(l<=mid)left=new Seg(l,mid,A);
                if(r>=mid+1)right=new Seg(mid+1,r,A);
                this.min=Math.min(left.min,right.min);
                this.max=Math.max(left.max,right.max);
                this.sum=left.sum+right.sum;
            }else{
                this.min=A[l];this.max=A[l];
                this.sum=A[l];
            }
        }

        public long query1(int s,int e){//min
            if(e<0||s<0)return 0;
            if(this.setTo!=-1){
                return this.setTo;
            }
            if(l==s&&r==e){
                return min;
            }

            int mid=l+(r-l)/2; //left :  to mid-1,
            if(e<=mid){
                return left.query1(s,e);
            }
            else if(s>=mid+1){
                return right.query1(s,e);
            }else{
                return Math.min(left.query1(s,mid),right.query1(mid+1,e));
            }
        }

        public long query2(int s,int e){//sum
            if(e<0||s<0)return 0;

            if(this.setTo!=-1){
                return this.sum();
            }
            if(l==s&&r==e){
                return this.sum;
            }

            int mid=l+(r-l)/2; //left :  to mid-1,
            if(e<=mid){
                return left.query2(s,e);
            }
            else if(s>=mid+1){
                return right.query2(s,e);
            }else{
                return left.query2(s,mid)+right.query2(mid+1,e);
            }
        }


        public void update(int s,int e,int val){
            if(e<0||s<0||s>e)return;
            if(l==s&&r==e){//whole subtree : setTo
                this.setTo=val;
                return;
            }
            int mid=l+(r-l)/2;
            if(e<=mid){
                left.update(s,e,val);
                if(setTo!=-1){
                    left.update(l,s-1,setTo);
                    left.update(s+1,mid,setTo);
                    right.update(mid+1,r,setTo);
                }
            }
            else if(s>=mid+1){
                right.update(s,e,val);
                if(setTo!=-1){
                    left.update(l,mid,setTo);
                    right.update(mid+1,s-1,setTo);
                    right.update(e+1,r,setTo);
                }
            }else{
                left.update(s,mid,val);
                right.update(mid+1,e,val);
                if(setTo!=-1){
                    left.update(l,s-1,setTo);
                    right.update(e+1,r,setTo);
                }
            }
            this.min=Math.min(left.min(),right.min());
            this.max=Math.max(left.max(),right.max());
            this.sum=left.sum()+right.sum();
            this.setTo=-1;
        }

        public int min() {
            if (setTo!=-1) return setTo;
            return min;
        }
        public int max() {
            if (setTo!=-1) return setTo;
            return max;
        }
        public long sum() {
            if (setTo!=-1) return (r-l+1)*(setTo+0l);
            return sum;
        }
    }

}

