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 pi pair<int,int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ll long long
#define inf 1000000000
using namespace std;
template <class T>
inline void read(T &a)
{static char c;int f=0;
while (((c=getchar())<'0'||c>'9')&&(c!='-'));
if (c=='-') {a=0;f=1;}
else {a=c-'0';}
while ((c=getchar())<='9'&&c>='0') a=(a<<3)+(a<<1)+c-'0';
if (f) a=-a;
}
bool vis[605][605];
int cnt=0,num=0,o=0,d1,d2,n;
int dx[4]={1,-1,1,-1},mod;
int dy[4]={1,1,-1,-1};
pi p[360005],g[360005],ans[100005];
inline bool cmp(pi a,pi b)
{return (a.fi+a.se)%mod<(b.fi+b.se)%mod;}
int main (){
	int i,j,k;
	scanf ("%d%d%d",&n,&d1,&d2);
	for (i=0;i<2*n;i++)
	{for (j=0;j<2*n;j++)
	{p[++num]=mp(i,j);
	if ((i*i+j*j==d1)||(i*i+j*j==d2)) g[++o]=mp(i,j);
	}
	}
	for (mod=2;;mod++)
	{stable_sort(p+1,p+num+1,cmp);
	memset(vis,0,sizeof(vis));cnt=0;
	for (i=1;i<=num;i++)
	{if (vis[p[i].fi][p[i].se]) continue;
	ans[++cnt]=p[i];
	if (cnt>=n*n) break;
	for (j=1;j<=o;j++)
	{for (k=0;k<4;k++)
	{int x=p[i].fi+dx[k]*g[j].fi,y=p[i].se+dy[k]*g[j].se;
	if (x<0||x>=2*n||y<0||y>=2*n) continue;
	vis[x][y]=1;
	}
	}
	}
	if (cnt>=n*n)
	{for (i=1;i<=cnt;i++) printf ("%d %d\n",ans[i].fi,ans[i].se);
	return 0;
	}
	}
	return 0;
}
	