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 MN 600
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
pair<int,int> q[MN+5];
int n,d,D,s[MN+5][MN+5],vis[MN+5][MN+5],num[4],top;
void Mark(int x,int y,int c,int S)
{
    if(S) s[x][y]|=c;vis[x][y]=1;
    for(int j=1;j<=top;++j)
        for(int dx=-1;dx<=1;dx+=2) for(int dy=-1;dy<=1;dy+=2)
        {
            int nx=x+dx*q[j].first,ny=y+dy*q[j].second;
            if(nx>0&&ny>0&&nx<=n<<1&&ny<=n<<1&&!vis[nx][ny]) Mark(nx,ny,c,S^1);
        }
}
void Solve(int d,int c)
{
    top=0;
    for(int i=0;i*i<=d;++i)
    {
        int j=d-i*i,flag=-1;
        for(int k=0;k*k<=j;++k) if(k*k==j) flag=k;
        if(flag>=0) q[++top]=make_pair(i,flag);
    }
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n<<1;++i) for(int j=1;j<=n<<1;++j) if(!vis[i][j]) Mark(i,j,c,0);
}
int main()
{
    n=read();d=read();D=read();
    Solve(d,1);Solve(D,2);
    for(int i=1;i<=n<<1;++i) for(int j=1;j<=n<<1;++j) ++num[s[i][j]];
    for(int k=0;k<4;++k) if(num[k]>=n*n)
    {
        int left=n*n;
        for(int i=1;i<=n<<1;++i) for(int j=1;j<=n<<1;++j)
            if(s[i][j]==k&&left) --left,printf("%d %d\n",i-1,j-1);
        return 0;
    }
    return 0;
}