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:- Query type 1: Find the index of the
k-th occurrence of 1 in the array.
- 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 - 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