K番目のセットビット

サイズが n の二進数の配列が与えられます。この配列には 0 と 1 の要素が含まれ、要素は 1 から n まで番号が振られています。ここに対して、合計 q 回のクエリを処理する必要があります。クエリには2つの種類があり、以下のいずれかを行います:

1. クエリタイプ1: 配列の中で 1 が出現する k 番目の位置を見つける。

2. クエリタイプ2: 配列の特定のインデックスにある値を更新する。

効率的にクエリに回答するプログラムを作成してください。

入力 (Input)

最初の行には、配列のサイズを表す整数 n とクエリの数を表す整数 q が、スペース区切りで与えられます。

2 行目には、長さが n の二進数の配列の要素が入力されます。

続く q 行にはクエリの内容が与えられます。各クエリは、クエリタイプ (1 または 2) と、必要なパラメータを続けて指定します:

• クエリタイプ1の場合: k (1 ≤ k ≤ n)

• クエリタイプ2の場合: インデックス p (1 ≤ p ≤ n) と、その位置に更新する値 ( または )

出力 (Output)

クエリタイプ1については、配列の中で 1 が k 回目に現れるインデックスを出力してください。もし k 回目の 1 が存在しない場合は -1 を出力してください。

例 (Examples)