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>
using namespace std;
const int maxn = 300;
int n, a[maxn][2], acnt, d1, d2;
int co[maxn * 2][maxn * 2][2];

void dfs(int x, int y, int d) {
	for (int i = -1; i <= 1; i += 2)
		for (int j = -1; j <= 1; j += 2)
			for (int k = 1; k <= acnt; ++k) {
				int xx = x + i * a[k][0], yy = y + j * a[k][1];
				if (xx >= 0 && xx < n * 2 && yy >= 0 && yy < n * 2 && !co[xx][yy][d]) {
					co[xx][yy][d] = 3 - co[x][y][d]; dfs(xx, yy, d);
				}
			}
}


void add(int v, int d) {
	acnt = 0;
	for (int i = 0; i * i <= v; ++i) {
		int d = v - i * i, dd = sqrt(d) + 0.5;
		if (dd * dd == d) {
			a[++acnt][0] = i; a[acnt][1] = dd;
		}
	}
	for (int i = 0; i < n * 2; ++i)
		for (int j = 0; j < n * 2; ++j) {
			if (!co[i][j][d]) {
				co[i][j][d] = 1; dfs(i, j, d);
			}
		}
}

int main() {
	scanf("%d%d%d", &n, &d1, &d2);
	add(d1, 0); add(d2, 1);
	for (int i = 1; i <= 2; ++i)
		for (int j = 1; j <= 2; ++j) {
			int cnt = 0;
			for (int k = 0; k < n * 2; ++k)
				for (int l = 0; l < n * 2; ++l)
					if (co[k][l][0] == i && co[k][l][1] == j) ++cnt;
			if (cnt >= n * n) {
				cnt = 0;
				for (int k = 0; k < n * 2; ++k)
					for (int l = 0; l < n * 2; ++l)
						if (co[k][l][0] == i && co[k][l][1] == j) {
							printf("%d %d\n", k, l);
							if (++cnt == n * n) return 0;
						}
			}
		}
}
