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 (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.