#include "hora.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
int n, k, cnt=0;
int pytaj(int l, int r) {
	if(cnt>100) while(true);
	int b=ask(l, r);
	int g=r-l+1;
	if(l>r) g=n-(l-r-1);
	g-=b;
	return b-g;
}
int solve(int N, int K) {
	mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
	n=N; k=K;
	if(n<=34) {
		rep(i, n) {
			ll a=pytaj(i, (i+k-1)%n);
			if(abs(a)==k%2) return i;
		}
		return -1;
	}
	int uj=-1, dod=-1;
	while(uj==-1 || dod==-1) {
		ll x=rng()%n;
		ll a=pytaj(x, (x+k-1)%n);
		if(abs(a)==k%2) return x;
		if(a<0) uj=x; else dod=x;
	}
	while(true) {
		int mid=(uj+dod)/2;
		ll a=pytaj(mid, (mid+k-1)%n);
		if(abs(a)==k%2) return mid;
		if(a<0) uj=mid; else dod=mid;
	}
	return -1;
}