#include <bits/stdc++.h>
using namespace std;

int ask(int, int);
int solve(int, int);

int n,k;

int calc1(int x)
{
	x %= n;
	return ask(x,(x+k-1)%n)*2-k;
}

int calc2(int x)
{
	if(x==n-1)
		return 0;

	return ask(0,x)*2-x;
}

int calc(int l,int r)
{
	if(l>r)
		return calc(l,r+n);

	if(l==r)
		return l;

	int mid=(l+r)/2, val=calc1(mid);
	if(val<0)
		return calc(mid+1,r);
	if(val>0)
		return calc(l,mid-1);
	return mid;
}

vector <int> vec;

int calcsmall(int l,int r)
{
	if(l==r)
		return vec[l];

	int mid=(l+r)/2, val=calc2((vec[mid]+k-1)%n);
	if(val<=0)
		return calcsmall(l,mid);
	return calcsmall(mid+1,r);
}

int calcbig(int l,int r)
{
	if(l==r)
		return vec[l];

	int mid=(l+r)/2, val=calc2((vec[mid]+k-1)%n);
	if(val>=0)
		return calcbig(l,mid);
	return calcbig(mid+1,r);
}

int solve(int N,int K)
{
	n=N, k=K;
	if(k==n)
		return 0;

	if(k%2==1)
		k--;

	if(k==0)
		return 0;

	vec.clear();
	vec.push_back(0);
	for(int i=k;i!=0;i=(i+k)%n)
		vec.push_back(i);

	int val=calc1(vec.back());
	if(val==0)
		return vec.back();

	int id1, id2;
	if(val>0)
	{
		id2=vec.back(), vec.pop_back();
		if(calc1((id2+n/2)%n)<=0)
			id1=(id2+n/2)%n;
		else
			id1=calcsmall(0,vec.size()-1);
	}
	else
	{
		id1=vec.back(), vec.pop_back();
		if(calc1((id1+n/2)%n)>=0)
			id2=(id1+n/2)%n;
		else
			id2=calcbig(0,vec.size()-1);
	}

	return calc(id1,id2)%n;
}