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 N=605;
int vis[N][N],a[N][N],d1,d2,n,c1,c2;
int fx[4][2],v,cnt[4],q1;
void make(int c1){
	memset(fx,0,sizeof fx);
	if (c1&1){
		fx[0][0]=1<<(c1/2);
		fx[0][1]=1<<(c1/2);
	}
	else fx[0][0]=1<<(c1/2);
	for (int i=1;i<=3;i++){
		fx[i][0]=-fx[i-1][1];
		fx[i][1]=fx[i-1][0];
	}
}
int inmap(int x,int y){
	return (0<=x&&x<2*n)&&(0<=y&&y<2*n);
}
void dfs(int x,int y,int z){
	a[x][y]+=z*v;
	vis[x][y]=1;
	for (int i=0;i<4;i++){
		int xx=x+fx[i][0],yy=y+fx[i][1];
		if (inmap(xx,yy)){
			if (!vis[xx][yy])
				dfs(xx,yy,z^1);
		}
	}
}
int main(){
	cin>>n>>d1>>d2;
	while (d1%2==0)c1++,d1/=2;
	while (d2%2==0)c2++,d2/=2;
	make(c1);v=1;
	for (int i=0;i<2*n;i++)
	for (int j=0;j<2*n;j++)
		if (!vis[i][j])dfs(i,j,0);
	make(c2);v=2;
	memset(vis,0,sizeof vis);
	for (int i=0;i<2*n;i++)
	for (int j=0;j<2*n;j++)
		if (!vis[i][j])dfs(i,j,0);	
	for (int i=0;i<2*n;i++)
	for (int j=0;j<2*n;j++)
		cnt[a[i][j]]++;
	for (int i=0;i<4;i++)
		if (cnt[i]>=n*n)q1=i;
	int ccnt=0;
	for (int i=0;i<2*n;i++)
	for (int j=0;j<2*n;j++){
		if (a[i][j]==q1){
			ccnt++;
			printf("%d %d\n",i,j);
			if (ccnt==n*n)return 0;
		}
	}
}