#include "hora.h"
#include<bits/stdc++.h>
#define LL long long
#define LLL __int128
#define uint unsigned
#define ldb long double
#define uLL unsigned long long
using namespace std;
int n,k;
map<pair<int,int>,int>Q;
inline int qry(int l,int r){
    l%=n,r%=n;
    if(l==r)return 0;
    r=(r+n-1)%n;
    if(Q.count({l,r}))return Q[{l,r}];
    return Q[{l,r}]=ask(l,r)*2-(r-l+1+n)%n;
}
int solve(int _n,int _k){
    n=_n,k=_k,Q.clear();
    if(k&1)--k;
    vector<int>A;
    for(int i=k;i;i=(i+k)%n)A.emplace_back(i);
    int Lc=qry(0,k),l=0,r=A.size()-1;
    int L=0,R=n/2,Rc=qry(R,R+k);
    if(!Lc)return 0;
    if(!Rc)return R;
    if((Lc>0)==(Rc>0)){
        while(l<r){
            const int mid=(l+r)>>1;
            int v=qry(A[l],A[mid]+k);
            if(Lc>0?v<0:v>0)r=mid;
            else l=mid+1;
        }
        R=A[l],Rc=qry(R,R+k);
        if(!Rc)return R;
    }
    while(L<R){
        const int mid=(L+R)>>1;
        int v=(L+1==mid&&mid==R-1?0:qry(mid,mid+k));
        if(!v)return mid;
        if((v>0)==(Lc>0))L=mid,Lc=v;
        else R=mid,Rc=v;
    }
    return -1;
}