#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()
bool changed=false;
int n, k;
int pytaj(int l, int r) {
	int b=ask(l, r);
	int g=r-l+1;
	if(l>r) g=n-(l-r-1);
	g-=b;
	return b-g;
}
int odpowiedz(int x) {
	if(changed) x=(x+k)%n;
	return x;
}
int solve(int N, int K) {
	mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
	n=N; k=K;
	if(2*k>n) {
		k=n-k;
		changed=true;
	}
	int uj=0, dod=0;
	ll a=pytaj(0, (0+k-1)%n);
	if(abs(a)==k%2) return odpowiedz(0);
	if(a>0) {
		int l=1, r=n/k-1;
		while(r-l+1>1) {
			int mid=(l+r)/2;
			ll x=pytaj(l*k, k*mid);
			if(mid-l+1==1 && abs(x)==k%2) return odpowiedz(l*k);
			if(x<=0) r=mid; else l=mid+1; 
		}
		uj=l*k;
	} else {
		int l=1, r=n/k-1;
		while(r-l+1>1) {
			int mid=(l+r)/2;
			ll x=pytaj(l*k, k*mid);
			if(mid-l+1==1 && abs(x)==k%2) return odpowiedz(l*k);
			if(x>=0) r=mid; else l=mid+1;
		}
		dod=l*k;
	}
	while(true) {
		int mid=(uj+dod)/2;
		ll a=pytaj(mid, (mid+k-1)%n);
		if(abs(a)==k%2) return odpowiedz(mid);
		if(a<0) uj=mid; else dod=mid;
	}
	return -1;
}