이진수열과 쿼리

길이 $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$.