#include "hora.h"
#include <assert.h>

typedef long long ll;

const int NMAX = 100000;

ll lcm, n;

int
get(ll x, ll s)
{
	int r;
	x %= n;
	r = (x + s - 1ll) % n;
	s = r - x + 1;
	if (s <= 0)
		s += n;

	return 2 * ask(x, r) - s;
}

int
gcd(int a, int b)
{
	while (b) {
		b ^= a;
		a ^= b;
		b ^= a;
		b %= a;
	}
	return a;
}

int
solve(int _n, int k)
{
	int v, j;
	assert(2 <= _n && _n <= NMAX);
	assert(1 <= k && k <= _n);
	ll l, r, mid;
	ll s;
	if (k == 1) return 0;
	n = _n;
	if (k & 1) {
		if (gcd(n, k + 1) > gcd(n, k - 1))
			k++;
		else
			k--;
	}


	lcm = (ll)n * (ll)k / (ll)gcd(n, k);

	v = get(0, k);
	if (!v)
		return 0;
	if (v != -get(n / 2, k)) {
		v = (v > 0) ? 1 : -1;

		l = 1;
		r = lcm / (ll)k - 1ll;
		while (l < r) {
			s = (r - l + 1) / 2;
			if (v * get(l * (ll)k, s * (ll)k) > 0)
				l += s;
			else
				r = l + s - 1;
		}

		l = 1;
		r = (r * (ll)k) % n;
		if (!r) r = n - 1;
	}
	else {
		r = n / 2;
	}

	while (l < r) {
		mid = (l + r) / 2;
		j = get(mid, k);
		if (j * v > 0)
			l = mid + 1;
		else if (j * v < 0)
			r = mid - 1;
		else
			return mid;
	}

	return l;
}