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

/*
    Java might be good for Competitive Programming but Python still rocks!!!!!!!!!


                            pppppppppppppppppppp
                         ppppp  ppppppppppppppppppp
                      ppppppp    ppppppppppppppppppppp
                      pppppppp  pppppppppppppppppppppp
                      pppppppppppppppppppppppppppppppp
                              pppppppppppppppppppppppp
       ppppppppppppppppppppppppppppppppppppppppppppppp  pppppppppppppppppppp
      pppppppppppppppppppppppppppppppppppppppppppppppp  ppppppppppppppppppppp
     ppppppppppppppppppppppppppppppppppppppppppppppppp  pppppppppppppppppppppp
    ppppppppppppppppppppppppppppppppppppppppppppppp    pppppppppppppppppppppppp
   pppppppppppppppppppppppppppppppppppppppppppppp     pppppppppppppppppppppppppp
  ppppppppppppppppppppppppppppppppppppppppppppp      pppppppppppppppppppppppppppp
  pppppppppppppppppppppppppppppppp               pppppppppppppppppppppppppppppppp
  pppppppppppppppppppppppppppp     pppppppppppppppppppppppppppppppppppppppppppppp
  ppppppppppppppppppppppppppp    pppppppppppppppppppppppppppppppppppppppppppppppp
    pppppppppppppppppppppppp  pppppppppppppppppppppppppppppppppppppppppppppppppp
     ppppppppppppppppppppppp  ppppppppppppppppppppppppppppppppppppppppppppppppp
      pppppppppppppppppppppp  ppppppppppppppppppppppppppppppppppppppppppppppp
       ppppppppppppppppppppp  ppppppppppppppppppppppppppppppppppppppppppppp
                              pppppppppppppppppppppppp
                              pppppppppppppppppppppppppppppppp
                              pppppppppppppppppppppp  pppppppp
                              ppppppppppppppppppppp    ppppppp
                                 ppppppppppppppppppp  ppppp
                                    pppppppppppppppppppp
*/

import java.util.*;
import java.lang.*;
import java.io.*;
public final class ProblemE
{
    public static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
    public static long u, answer, value;
    public static int n, i, mid, low, high, t;
    public final static long inf = 1_000_000_001;
    public static long[] tree, lazy;
    public static void main(String[] args) throws IOException
    {
        Reader sc = new Reader();
        n = sc.nextInt();
        int q = sc.nextInt();
        tree = new long[n << 2];
        lazy = new long[n << 2];
        for(i = 1; i <= n; i++) update(1, 1, n, i, i, sc.nextLong());
        while(q-- > 0)
        {
            t = sc.nextInt();
            if(t == 1) update(1, 1, n, 1, sc.nextInt(), sc.nextLong());
            else out.write(result(sc.nextLong(), sc.nextLong()) + "\n");
        }
        out.close();
    }

    public static long result(long w, long v)
    {
        answer = 0;
        while(v > 0 && w <= n)
        {
            low = (int) w; high = n; u = -1;
            while (low <= high)
            {
                mid = (low + high) >> 1;
                value = query(1, 1, n, (int) w, mid);
                if (value <= v)
                {
                    u = mid; low = mid + 1;
                }
                else high = mid - 1;
            }
            if(u != -1)
            {
                v -= query(1, 1, n, (int)w, (int)u);
                answer += (u - w + 1);
            }
            low = (int) (u == -1 ? w + 1: u + 1); high = n; w = -1;
            while(low <= high)
            {
                mid = (low + high) >> 1;
                value = query(1, 1, n, mid, mid);
                if(value <= v)
                {
                    w = mid;
                    high = mid - 1;
                }
                else low = mid + 1;
            }
            if(w == -1) break;
        }
        return answer;
    }

    public static void update(int node, int low, int high, int start, int end, long value)
    {
        if(lazy[node] > 0)
        {
            tree[node] = Math.max(tree[node], lazy[node] * (high - low + 1));
            if(low != high)
            {
                lazy[node << 1] = Math.max(lazy[node << 1], lazy[node]);
                lazy[(node << 1) + 1] = Math.max(lazy[(node << 1) + 1], lazy[node]);
            }
            lazy[node] = 0;
        }
        if(low > high || start > end || low > end || start > high)
            return;
        if(start <= low && end >= high)
        {
            tree[node] = Math.max(tree[node], value * (high - low + 1));
            if(low != high)
            {
                lazy[node << 1] = Math.max(lazy[node << 1], value);
                lazy[(node << 1) + 1] = Math.max(lazy[(node << 1) + 1], value);
            }
            return;
        }
        int mid = (low + high) >> 1;
        update(node << 1, low, mid, start, end, value);
        update((node << 1) + 1, mid + 1, high, start, end, value);
        if(tree[node << 1] + tree[(node << 1) + 1] >= inf) tree[node] = inf;
        else tree[node] = tree[node << 1] + tree[(node << 1) + 1];
    }

    public static long query(int node, int low, int high, int start, int end)
    {
        if(lazy[node] > 0)
        {
            tree[node] = Math.max(tree[node], lazy[node] * (high - low + 1));
            if(low != high)
            {
                lazy[node << 1] = Math.max(lazy[node << 1], lazy[node]);
                lazy[(node << 1) + 1] = Math.max(lazy[(node << 1) + 1], lazy[node]);
            }
            lazy[node] = 0;
        }
        if(low > high || start > end || low > end || start > high)
            return 0;
        if(start <= low && end >= high)
            return tree[node];
        int mid = (low + high) >> 1;
        long left = query(node << 1, low, mid, start, end);
        if(left >= inf) return inf;
        long right = query((node << 1) + 1, mid + 1, high, start, end);
        if(right >= inf) return inf;
        return left + right;
    }

    static class Reader
    {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;

        public Reader()
        {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public Reader(String file_name) throws IOException
        {
            din = new DataInputStream(new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public String readLine() throws IOException
        {
            byte[] buf = new byte[64]; // line length
            int cnt = 0, c;
            while ((c = read()) != -1)
            {
                if (c == '\n')
                    break;
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }

        public int nextInt() throws IOException
        {
            int ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do
            {
                ret = ret * 10 + c - '0';
            }  while ((c = read()) >= '0' && c <= '9');

            if (neg)
                return -ret;
            return ret;
        }

        public long nextLong() throws IOException
        {
            long ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');
            if (neg)
                return -ret;
            return ret;
        }

        public double nextDouble() throws IOException
        {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();

            do {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');

            if (c == '.')
            {
                while ((c = read()) >= '0' && c <= '9')
                {
                    ret += (c - '0') / (div *= 10);
                }
            }

            if (neg)
                return -ret;
            return ret;
        }

        private void fillBuffer() throws IOException
        {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }

        private byte read() throws IOException
        {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }

        public void close() throws IOException
        {
            if (din == null)
                return;
            din.close();
        }
    }

    public static class Print
    {
        Print()
        {}

        void integer(int... arr) throws IOException
        {
            for(int value: arr)
            {
                out.write(value+" ");
                out.flush();
            }
            out.write("\n");
            out.flush();
        }

        void string(String... arr) throws IOException
        {
            for(String value: arr)
            {
                out.write(value+" ");
                out.flush();
            }
            out.write("\n");
            out.flush();
        }

        void character(char... arr) throws IOException
        {
            for(char value: arr)
            {
                out.write(value+" ");
                out.flush();
            }
            out.write("\n");
            out.flush();
        }

        void long_int(long... arr) throws IOException
        {
            for(long value: arr)
            {
                out.write(value+" ");
                out.flush();
            }
            out.write("\n");
            out.flush();
        }
    }

    static class FastScanner
    {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer("");
        String next()
        {
            while (!st.hasMoreTokens())
                try
                {
                    st=new StringTokenizer(br.readLine());
                } catch (IOException e)
                {
                    e.printStackTrace();
                }
            return st.nextToken();
        }

        int nextInt()
        {
            return Integer.parseInt(next());
        }
        int[] readArray(int n)
        {
            int[] a=new int[n];
            for (int i=0; i<n; i++) a[i]=nextInt();
            return a;
        }
        long nextLong()
        {
            return Long.parseLong(next());
        }
    }
}
