K-th Set Bit

You are given a binary array of size n consisting of 0s and 1s, where the array elements are numbered from 1 to n. You need to process q queries, where each query can be of two types:
  1. Query type 1: Find the index of the k-th occurrence of 1 in the array.
  1. Query type 2: Update the value at a specific index of the array.
Write a program to answer the queries efficiently.

Input

The input consists of two integers n and q on the first line, separated by a space, representing the size of the binary array and the number of queries, respectively.
The second line contains n binary elements of the array.
The next q lines represent the queries. Each query is represented by a query type (1 or 2) followed by the necessary parameters:
  • For query type 1: an integer k (1 ≀ k ≀ n).
  • For query type 2: an integer index p (1 ≀ p ≀ n) and a value ( or ) to update at that index.

Output

For each query of type 1, print the index of the k-th occurrence of 1 in the array. If there is no k-th occurrence, print -1.

Examples

Input
Output
6 4 1 0 1 1 0 1 1 2 2 1 0 1 4 1 3
3 -1 6
Β 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue