Takahashi is doing a research on sets of points in a plane. Takahashi thinks a set S of points in a coordinate plane is a good set when S satisfies both of the following conditions:

* The distance between any two points in S is not \sqrt{D_1}.
* The distance between any two points in S is not \sqrt{D_2}.



Here, D_1 and D_2 are positive integer constants that Takahashi specified.

Let X be a set of points (i,j) on a coordinate plane where i and j are integers and satisfy 0 ≤ i,j < 2N.

Takahashi has proved that, for any choice of D_1 and D_2, there exists a way to choose N^2 points from X so that the chosen points form a good set. However, he does not know the specific way to choose such points to form a good set. Find a subset of X whose size is N^2 that forms a good set.

Constraints

* 1 ≤ N ≤ 300
* 1 ≤ D_1 ≤ 2×10^5
* 1 ≤ D_2 ≤ 2×10^5
* All values in the input are integers.

Input

Input is given from Standard Input in the following format:


N D_1 D_2


Output

Print N^2 distinct points that satisfy the condition in the following format:


x_1 y_1
x_2 y_2
:
x_{N^2} y_{N^2}


Here, (x_i,y_i) represents the i-th chosen point. 0 ≤ x_i,y_i < 2N must hold, and they must be integers. The chosen points may be printed in any order. In case there are multiple possible solutions, you can output any.

Examples

Input

2 1 2


Output

0 0
0 2
2 0
2 2


Input

3 1 5


Output

0 0
0 2
0 4
1 1
1 3
1 5
2 0
2 2
2 4
#include <bits/stdc++.h>

#define For(i, j, k) for (int i = j; i <= k; i++)
#define Forr(i, j, k) for (int i = j; i >= k; i--)

using namespace std;

const int N = 3.6e5 + 10;
const int dx[4] = {1, 1, -1, -1}, dy[4] = {-1, 1, -1, 1};

int col[N];
int n;
vector<int> G[N];

int id(int x, int y) {
	return x * n + y + 1;
}

int sqr[N];
bool vis[N];

void DFS(int o, int s, int w) {
	vis[o] = true;
	col[o] |= s * w;
	for (int x : G[o]) if (!vis[x]) DFS(x, s ^ 1, w);
}

void getcol(int d, int w) {
	For(i, 1, n * n) G[i].clear(), vis[i] = false;
	For(i, 0, n - 1) For(j, 0, n - 1)
		for (int k = 0; k * k <= d; ++k) if (k * k == d || sqr[d - k * k]) {
			int s = sqr[d - k * k];
			For(u, 0, 3) {
				int x = i + dx[u] * k, y = j + dy[u] * s;
				if (x >= n || y >= n || x < 0 || y < 0) continue;
				G[id(i, j)].push_back(id(x, y));
			}
		}
	For(i, 1, n * n) if (!vis[i]) DFS(i, 0, w);
}

int p, q;
vector<int> ans[4];

int main() {

	For(i, 1, 600) sqr[i * i] = i;
	scanf("%d%d%d", &n, &p, &q);

	n *= 2;
	getcol(p, 1);
	getcol(q, 2);
	For(i, 1, n * n) ans[col[i]].push_back(i);
	For(i, 0, 3) if (int(ans[i].size()) >= (n / 2) * (n / 2)) {
		For(j, 0, (n / 2) * (n / 2) - 1) printf("%d %d\n", (ans[i][j] - 1) / n, (ans[i][j] - 1) % n);
		return 0;
	}

	return 0;
}