#include "hora.h"
#include <bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

int N;

int query(int L, int R) {
    int res = ask(L, R);
    int len = (R - L + N) % N + 1;
    return res * 2 - len;
}

int solve(int N, int K) {
    ::N = N;
    if (K == 1 || K == N) {
        return 0;
    }
    if (K % 2 == 1) {
        K--;
    }
    int M = N / std::gcd(N, K);
    int a = query(0, K - 1);
    if (a == 0) {
        return 0;
    }
    int x = 0;
    {
        int lo = 1, hi = M;
        while (hi - lo > 1) {
            int m = (lo + hi) / 2;
            int l = 1LL * lo * K % N;
            int r = (1LL * m * K - 1) % N;
            if ((query(l, r) > 0) != (a > 0)) {
                hi = m;
            } else {
                lo = m;
            }
        }
        x = 1LL * lo * K % N;
    }
    
    int lo = 0, hi = x;
    int b = query(x, (x + K - 1) % N);
    if (b == 0) {
        return x;
    }
    while (true) {
        int m = (lo + hi) / 2;
        if (hi - lo == 2) {
            return m;
        }
        int c = query(m, (m + K - 1) % N);
        if (c == 0) {
            return m;
        }
        if ((a > 0) != (c > 0)) {
            b = c;
            hi = m;
        } else {
            a = c;
            lo = m;
        }
    }
    return -1;
}