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>
typedef long long ll;
ll gi(){
	ll x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch))f^=ch=='-',ch=getchar();
	while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
	return f?x:-x;
}
std::mt19937 rnd(time(NULL));
#define rand rnd
#define pr std::pair<int,int>
#define fi first
#define se second
template<class T>void cxk(T&a,T b){a=a>b?a:b;}
template<class T>void cnk(T&a,T b){a=a<b?a:b;}
#ifdef mod
int pow(int x,int y){
	int ret=1;
	while(y){
		if(y&1)ret=1ll*ret*x%mod;
		x=1ll*x*x%mod;y>>=1;
	}
	return ret;
}
template<class Ta,class Tb>void inc(Ta&a,Tb b){a=a+b>=mod?a+b-mod:a+b;}
template<class Ta,class Tb>void dec(Ta&a,Tb b){a=a>=b?a-b:a+mod-b;}
#endif
int n,D1,D2,N,x[360001],y[360001],c[2][360001];
std::vector<int>vec[4];
void getcol(int D,int*c){
	int A=1;
	while(D%4==0)D>>=2,A<<=1;
	for(int i=1;i<=N;++i)
		if(D%4==1)c[i]=((x[i]/A)+(y[i]/A))&1;
		else c[i]=(x[i]/A)&1;
}
int main(){
#ifdef LOCAL
	freopen("in.in","r",stdin);
	//freopen("out.out","w",stdout);
#endif
	n=gi(),D1=gi(),D2=gi(),N=n*n*4;
	for(int i=1;i<=N;++i)x[i]=(i-1)/(2*n),y[i]=(i-1)%(2*n);
	getcol(D1,c[0]),getcol(D2,c[1]);
	for(int i=1;i<=N;++i)vec[(c[0][i]<<1)|c[1][i]].push_back(i);
	for(int i=0;i<4;++i)
		if(vec[i].size()>=n*n){
			N=n*n;
			for(int j:vec[i]){
				printf("%d %d\n",x[j],y[j]);
				if(!--N)break;
			}
			exit(0);
		}
	return 0;
}
