K-th Set Bit (K-esimo bit impostato)

Vi viene fornito un array binario di dimensione n, composto da 0 e 1, i cui elementi sono numerati da 1 a n. Dovete gestire q query, ognuna delle quali può essere di due tipi:

1. Query di tipo 1: trovare l’indice della k-esima occorrenza di 1 nell’array.

2. Query di tipo 2: aggiornare il valore in una determinata posizione dell’array.

Scrivete un programma in grado di rispondere a queste query in modo efficiente.

Input

L’input è costituito da due interi n e q sulla prima riga, separati da uno spazio, che rappresentano la dimensione dell’array binario e il numero di query, rispettivamente.

La seconda riga contiene i n elementi binari dell’array.

Le successive q righe descrivono le query. Ogni query è caratterizzata da un tipo (1 o 2) seguito dai parametri necessari:

• Per la query di tipo 1: un intero k (1 ≤ k ≤ n).

• Per la query di tipo 2: un indice intero p (1 ≤ p ≤ n) e un valore (0 o 1) da aggiornare in quella posizione.

Output

Per ogni query di tipo 1, stampate l’indice della k-esima occorrenza di 1 nell’array. Se la k-esima occorrenza non esiste, stampate -1.

Esempi