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

import java.io.*;
import java.util.*;

public class ques4
{
	public static void main(String[] args)throws Exception{ new ques4().run();} 
	long mod=1000000000+7;
	int n;
	long a[],lazy[],t[],mn[],mx[];
	long ans; long money;
	void solve() throws Exception
	{
		n=ni();
		int q=ni();
		 a=new long[n];
		 t = new long[(4*n)+1];
		 lazy = new long[(4*n)+1];
		 mn = new long[(4*n)+1];
		 mx = new long[(4*n)+1];
		 
		for(int i=0;i<n;i++)
			a[i]=nl();
		build(1,0,n-1);
		for(int i=0;i<q;i++) 
		{
			int type=ni();
			int x=ni();
			long y=nl();
			if(type==1)
			{
				update(1,0,n-1,x-1,y);
			}
			else
			{
				ans=0;
				money=y;
				get(1,0,n-1,x-1);
				out.println(ans);
			}
		}
	}
	void build(int v, int tl, int tr)
	{
		if(tl==tr)
		{
			t[v]=mn[v]=mx[v]=a[tl];
			return;
		}
			int tm=(tl+tr)/2;
			build(2*v,tl,tm);
			build((2*v)+1,tm+1,tr);
			t[v]=(t[2*v]+t[(2*v)+1]);
			mn[v]=Math.min(mn[2*v],mn[(2*v)+1] );
			mx[v]=Math.max(mx[2*v],mx[(2*v)+1] );
	}
	void get(int v,int tl,int tr, int x)  //range sum
	{
		if(x>tr || mn[v]>money)
			return;
		if(x<=tl && t[v]<=money)
		{
			ans+=(tr-tl)+1;
			money-=t[v]; 
			return;
		}
		push(v,tl,tr);
		int tm=(tl+tr)/2;
		get(2*v,tl,tm,x);
		get((2*v)+1,tm+1,tr,x);
	}
	
	void update(int v, int tl, int tr, int x, long y)  
	{
	    if(x<tl||mn[v]>=y)
	    	return;
	    if(tr<=x && mx[v]<=y) 
	    {
	       t[v] = (tr-tl+1)*y;
	       lazy[v] = mx[v]=mn[v]= y;
	       return;
	    } 
	        push(v,tl,tr);
	        int tm = (tl + tr) / 2;
	        update(v*2, tl, tm, x,y);
	        update(v*2+1, tm+1, tr,x,y);
	        t[v] = (t[v*2]+ t[(v*2)+1]);
	        mn[v]=Math.min(mn[2*v], mn[(2*v)+1]);
	        mx[v]=Math.max(mx[2*v], mx[(2*v)+1]);
	}
	
	void push(int v,int tl,int tr) 
	{
	   if(lazy[v]!=0)
	   {
	   lazy[2*v] = mn[2*v]=mx[2*v] = lazy[v];
	   lazy[(2*v)+1] = mn[(2*v)+1]=mx[(2*v)+1] = lazy[v];
	   t[v]       =  (((tl+tr)/2)-tl+1)*lazy[v];
	   t[(2*v)+1] =  (tr-((tr+tl)/2))*lazy[v];
	   lazy[v]=0;
	   }
	}
	
	/*IMPLEMENTATION BY AMAN KOTIYAL, FAST INPUT OUTPUT & METHODS BELOW*/
	
	private byte[] buf=new byte[1024];
	private int index;
	private InputStream in;
	private int total;
	private SpaceCharFilter filter;
	PrintWriter out;
	
	int gcd(int a, int b) 
	{ 
		if (a == 0) 
			return b; 
		return gcd(b%a, a); 
	} 
	long gcd(long a, long b) 
	{ 
		if (a == 0) 
			return b; 
		return gcd(b%a, a); 
	}
	/* for (1/a)%mod = ( a^(mod-2) )%mod  ----> use expo to calc -->(a^(mod-2)) */
	long expo(long p,long q)  /*  (p^q)%mod   */
	{
		long z = 1;
		while (q>0) {
			if (q%2 == 1) {
				z = (z * p)%mod;
			}
			p = (p*p)%mod;
			q >>= 1;
		}
		return z;
	}
	void run()throws Exception
	{
		in=System.in; out = new PrintWriter(System.out);
		solve();
		out.flush();
	}
	private int scan()throws IOException
	{
		if(total<0)
			throw new InputMismatchException();
		if(index>=total)
		{
			index=0;
			total=in.read(buf);
			if(total<=0)
				return -1;
		}
		return buf[index++];
	}
	private int ni() throws IOException 
	{
		int c = scan();
		while (isSpaceChar(c))
			c = scan();
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = scan();
		}
		int res = 0;
		do {
			if (c < '0' || c > '9')
				throw new InputMismatchException();
			res *= 10;
			res += c - '0';
			c = scan();
		} while (!isSpaceChar(c));
		return res * sgn;
	}
	private long nl() throws IOException 
	{
		long num = 0;
		int b;
		boolean minus = false;
		while ((b = scan()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
			;
		if (b == '-') {
			minus = true;
			b = scan();
		}
		
		while (true) {
			if (b >= '0' && b <= '9') {
				num = num * 10 + (b - '0');
			} else {
				return minus ? -num : num;
			}
			b = scan();
		}
	}
	private double nd() throws IOException{
		return Double.parseDouble(ns());
	}
	private String ns() throws IOException {
		int c = scan();
		while (isSpaceChar(c))
			c = scan();
		StringBuilder res = new StringBuilder();
		do {
			if (Character.isValidCodePoint(c))
				res.appendCodePoint(c);
			c = scan();
		} while (!isSpaceChar(c));
		return res.toString();
	}
	private String nss() throws IOException
	{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		return br.readLine();
	}
	private char nc() throws IOException 
	{
		int c = scan();
		while (isSpaceChar(c))
			c = scan();
		return (char) c;
	}
	private boolean isWhiteSpace(int n)
	{
		if(n==' '||n=='\n'||n=='\r'||n=='\t'||n==-1)
			return true;
		return false;
	}
	private boolean isSpaceChar(int c) {
		if (filter != null)
			return filter.isSpaceChar(c);
		return isWhiteSpace(c);
	}
	private interface SpaceCharFilter {
		public boolean isSpaceChar(int ch);
	}
}