二値数列とクエリ

長さ $N$ の二進文字列 $A$ が円環状に配置されている。位置には $1$ から $N$ までの番号が付いている。

次の操作を好きな回数行うことができる。

• 位置 $i$ を一つ選ぶ。
• $A_i,A_{i+1},\cdots,A_{i+K-1}$ をすべて反転する。添字は円環状であり、 を超えたら再び から数える。

文字列のすべての文字を 0 にするために必要な操作回数の最小値を考える。不可能な場合もある。

$Q$ 個のクエリが与えられる。$i$ 番目のクエリでは、まず $A_{p_i}$ を反転する。その後、現在の文字列をすべて 0 にするために必要な操作回数の最小値を出力する。不可能なら -1 を出力する。

答えを計算するために仮定した操作は、実際の文字列には適用されない。次のクエリへ引き継がれる変更は、クエリで指定された一文字の反転だけである。

入力は次の形式で標準入力から与えられる。

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

各テストケースの各クエリについて、答えを一行に一つずつ出力する。

現在の文字列をすべて 0 にできない場合は -1 を出力する。

• $1 \le T \le 200\,000$.
• $1 \le K \le N \le 200\,000$.