#include "testlib.h"
#include <iostream>
using namespace std;

// 快速幂计算 a^e mod m
long long mod_pow(long long a, long long e, long long m) {
    long long res = 1;
    a %= m;
    while (e) {
        if (e & 1) res = res * a % m;
        a = a * a % m;
        e >>= 1;
    }
    return res;
}

// 计算勒让德符号 (a/p)，p 为奇素数
int legendre(long long a, int p) {
    long long aa = a % p;
    if (aa == 0) return 0;
    long long res = mod_pow(aa, (p - 1) / 2, p);
    return res == 1 ? 1 : -1;
}

int main(int argc, char* argv[]) {
    registerInteraction(argc, argv);
    int p = inf.readInt();                // 读入隐藏的素数
    const int MAX_QUERIES = 17;
    int queries = 0;

    while (true) {
        string type = ouf.readToken();    // 读入 "?" 或 "!"

        if (type == "?") {
            if (++queries > MAX_QUERIES)
                quitf(_wa, "query limit exceeded");
            long long a = ouf.readLong();  // 读入 a，不检查范围
            if (a < 1 || a > 1000000)
                quitf(_wa, "a out of range: %lld", a);
            int res = legendre(a, p);
            cout << res << endl;           // 返回结果并刷新缓冲区
        } else if (type == "!") {
            long long guess = ouf.readLong(); // 读入猜测，不检查范围
            if (guess < 2 || guess > 1000000)
                quitf(_wa, "guess out of range: %lld", guess);
            if (guess == p)
                quitf(_ok, "correct. total guesses: %d", queries);
            else
                quitf(_wa, "wrong answer: guessed %lld, actual %d", guess, p);
        } else {
            quitf(_wa, "invalid token: %s", type.c_str());
        }
    }
    return 0;
}