#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

//typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

ULL mod;

ULL mult(ULL a, ULL b)
{
	return a * b % mod;
}
ULL add(ULL a, ULL b)
{
	return a + b < mod ? a + b : a + b - mod;
}
ULL sub(ULL a, ULL b)
{
	return a - b >= 0 ? a - b : a - b + mod;
}

const int N = 1 << 21;
int was[N];

ULL Q;

bool solve()
{
	fill(was, was + Q, -1);
	ULL a, b;
	cin >> a >> b;
	a %= mod;
	b %= mod;
	
	vector<ULL> vals;
	vals.reserve(3 * Q);
	
	was[a % Q] = SZ(vals);
	vals.PB(a);
	ULL cnt = 2 * Q;

	while(true)
	{
		a = add(mult(a, a), b);
		
		if(was[a % Q] != -1)
		{
			if(cnt)
			{
				ULL prev = vals[was[a % Q]];
				
				ULL d = sub(a, prev);
				
				if (gcd(d, mod) == Q)
					return 1;
				
				
				cnt--;
			}
			else
				return 0;
		}
		was[a % Q] = SZ(vals);
		vals.PB(a);
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int t;
	cin >> mod >> Q >> t;
	
	while(t--)
		cout << solve();
	cout << "\n";
	
	return 0;
}