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 LL long long
#define db double

using namespace std;
const int N=600+10;
int rd()
{
	int x=0,w=1;char ch=0;
	while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+(ch^48);ch=getchar();}
	return x*w;
}
int n,l1,l2,co[N][N],c2[N][N],st[N][2],tp;
bool vs[N][N];
struct node{int x,y;};
vector<node> ls[4];
queue<node> q;
void wk(int d,int u)
{
	tp=0;
	for(int j=0;j*j<=d;++j)
	{
		int k=sqrt(d-j*j);
		if(k*k+j*j==d) st[++tp][0]=j,st[tp][1]=k;
	}
	memset(vs,0,sizeof(vs));
	for(int i=0;i<n+n;++i)
		for(int j=0;j<n+n;++j)
			if(!vs[i][j])
			{
				vs[i][j]=1,q.push((node){i,j});
				while(!q.empty())
				{
					int x=q.front().x,y=q.front().y;
					q.pop();
					for(int k=1;k<=tp;++k)
						for(int dx=-1;dx<=1;dx+=2)
							for(int dy=-1;dy<=1;dy+=2)
							{
								int xx=x+dx*st[k][0],yy=y+dy*st[k][1];
								if(xx>=0&&xx<n+n&&yy>=0&&yy<n+n&&!vs[xx][yy])
									co[xx][yy]=co[x][y]^1,vs[xx][yy]=1,q.push((node){xx,yy});
							}
				}
			}
}

int main()
{
	n=rd(),l1=rd(),l2=rd();
	wk(l1,0);
	memcpy(c2,co,sizeof(co)),memset(co,0,sizeof(co));
	wk(l2,1);
	for(int i=0;i<n+n;++i)
		for(int j=0;j<n+n;++j)
			ls[co[i][j]<<1|c2[i][j]].push_back((node){i,j});
	int zs=0;
	for(int i=1;i<=3;++i)
		if(ls[zs].size()<ls[i].size()) zs=i;
	for(int i=0;i<n*n;++i) printf("%d %d\n",ls[zs][i].x,ls[zs][i].y);
	return 0;
}
