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<cstdio>
#include<cassert>
#include<cstring>
#include<cmath>
using namespace std;
const int maxl = 3e5 + 10;
const int maxn = 600 + 10; 
typedef long long ll;
inline ll sqr(ll x) { return x * x;}
int n;
int col1[maxn][maxn]; // color
int col2[maxn][maxn];
ll sqt[maxl];
int cr[2];
void dfs(int col[][maxn],int r,int c,int k,ll d){
	col[r][c] = k;
	for(ll i = -r;r + i < 2 * n;i++){
		if(d - sqr(i) < 0) continue;
		ll j = sqt[d - sqr(i)];
		if(j == -1) continue;
		if(j + c < n * 2){
			if(col[r + i][c + j] == -1)  dfs(col,r + i,c + j,k ^ 1,d);	
		} 
		if(c - j >= 0){
			if(col[r + i][c - j] == -1) dfs(col,r + i,c - j,k ^ 1,d);
		}
		
	}
}
int main(){
	memset(col1,-1,sizeof(col1));
	memset(col2,-1,sizeof(col2));
	memset(sqt,-1,sizeof(sqt));
	ll d1,d2;
	scanf("%d%lld%lld",&n,&d1,&d2);
	for(ll i = 0;i * i < maxl;i++) sqt[i * i] = i;
	for(int i = 0;i < 2 * n;i++) for(int j = 0;j < 2 * n;j++)if(col1[i][j] == -1) dfs(col1,i,j,0,d1);
	for(int i = 0;i < 2 * n;i++) for(int j = 0;j < 2 * n;j++) if(col2[i][j] == -1) dfs(col2,i,j,0,d2);
	int cnt = 0;
	for(int i = 0;i < 2 * n;i++){
		for(int j = 0;j < 2 * n;j++){
			if(cnt < n * n && col1[i][j] == col1[0][0] && col2[i][j] == col2[0][0]){
				printf("%d %d\n",i,j);
				++cnt;
			}
		}
	}
	assert(cnt == n * n); 
	return 0;
}