Binary Sequence and Queries

A binary string $A$ of length $N$ is arranged on a circle. Its positions are numbered from $1$ to $N$.

You may perform the following operation any number of times.

• Choose a position $i$.
• Flip all of $A_i,A_{i+1},\cdots,A_{i+K-1}$. Indices are cyclic, so after they continue again from .

Consider the minimum number of operations needed to make every character of the string equal to 0. It may be impossible.

There are $Q$ queries. In the $i$-th query, first flip $A_{p_i}$. Then print the minimum number of operations needed to make the current string all 0. Print -1 if it is impossible.

The operations considered when computing an answer are not actually applied to the string. Between queries, only the single-character flip specified by the query persists.

The input is given from Standard Input in the following format:

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

For each query of each test case, print the answer on its own line.

If the current string cannot be made all 0, print -1.

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