使用栈求解迷宫 - 维海的博客

作者在 2011-08-16 15:45:24 发布以下内容

#include<stdio.h>
#include<time.h>
#include<stdlib.h>

#define DOWN  1
#define LEFT  2
#define    UP    3
#define RIGHT 4
#define INITSTACKSIZE 100
#define INCREMENTSIZE 10
#define MARK  5
#define BLIND_ALLEY 6

typedef int ** MazeType;
MazeType Maze;
int Maze_Line,Maze_Column;

typedef struct
{
    int x;
    int y;
} PosType,*PtrtoPos;
PtrtoPos start,end;

typedef struct
{
    int ord;
    PosType seat;
    int direction;
} Record,*PtrtoRecord;

typedef struct
{
    PtrtoRecord base;
    int top;
    int stacksize;
    int length;
} SqStack,*PtrtoStack;

MazeType CreatMaze(void);
PtrtoStack MazePath(MazeType maze,PtrtoPos start,PtrtoPos end);
void Print_Path(PtrtoStack path);
PtrtoStack InitStack(void);
void Push(PtrtoStack ,PtrtoRecord );
void Pop(PtrtoStack ,PtrtoRecord );
void FootPrint(PtrtoPos );
void NextPos(PtrtoPos ,int );
void MarkPrint(PtrtoRecord );
int StackEmpty(PtrtoStack);
void DestroyStack(PtrtoStack);
int Pass(PtrtoPos);
void FreeMaze(MazeType);

void sleep(int x)
{
    clock_t time;
    time=(x*CLOCKS_PER_SEC)+clock();
    while(time>clock())
    {
        ;
    }
}//暂停函数

void pictype(int **Maze,int i,int j)
{
    if(i==start->y&&j==start->x) printf("☆");
    else
    {
        if(*(Maze[i]+j)==1) printf("■");
        if(*(Maze[i]+j)==4) printf("★");
        if(*(Maze[i]+j)==0) printf("□");
        if(*(Maze[i]+j)==5) printf("⊙");
        if(*(Maze[i]+j)==6) printf("▽");
    }

}
void printf_maze_and_path(MazeType Maze)
{
    //Maze[start->y][start->x]=3;
    printf("\n%d %d\n",Maze_Line,Maze_Column);
    for(int i=0; i<Maze_Line; i++)
        for(int j=0; j<Maze_Column; j++)
        {
            if(j==Maze_Column-1)
            {
                pictype(Maze,i,j);
                printf("\n");
            }
            else
            {
                pictype(Maze,i,j);
                //printf(" ");
            }

        }

}
///////////////////////////////////////////////////////////////////////////
int main()
{
    system("color f9");
    PtrtoStack Path;
    Maze=CreatMaze();
    printf("你输入的迷宫如下：\n");
    printf_maze_and_path(Maze);
    Path=MazePath(Maze,start,end);
    printf("坐标路径如下：\n");
    Print_Path(Path);
    printf("路径图如下（▽.代表足迹；⊙.代表路径）：\n");
    printf_maze_and_path(Maze);
    DestroyStack(Path);
    FreeMaze(Maze);

    return 0;
}

void example()
{
    printf("请输入迷宫长和宽：10 10\n");
    printf("请输入迷宫信息（1.墙,0.通路,3.起点,4.终点）：\n");
    printf("1 1 1 1 1 1 1 1 1 1\n");
    printf("1 1 1 0 3 0 0 0 0 1\n");
    printf("1 0 0 0 0 0 0 0 0 1\n");
    printf("1 1 0 0 0 0 1 1 0 1\n");
    printf("1 1 1 1 0 0 0 0 1 1\n");
    printf("1 1 1 1 1 0 0 0 1 1\n");
    printf("1 0 1 0 0 1 0 0 0 1\n");
    printf("1 1 4 0 1 0 0 1 1 1\n");
    printf("1 0 1 0 0 0 0 0 0 1\n");
    printf("1 1 1 1 1 1 1 1 1 1\n");
}

MazeType CreatMaze(void)
{
    start=(PtrtoPos)malloc(sizeof(PosType));
    end=(PtrtoPos)malloc(sizeof(PosType));
    int i,x,y;
    printf("输入样例（1）\n");
    example();
    printf("请输入迷宫长和宽：");
    scanf("%d%d",&Maze_Column,&Maze_Line);
    MazeType maze;
    printf("请输入迷宫信息（1.墙,0.通路,3.起点,4.终点）：\n");
    maze=(MazeType)malloc(sizeof(int *)*Maze_Line);
    for(i=0; i<Maze_Line; i++)
        maze[i]=(int *)malloc(sizeof(int)*Maze_Column);
    for(y=0; y<Maze_Line; y++)
        for(x=0; x<Maze_Column; x++)
        {
            scanf("%d",&maze[y][x]);
            if(maze[y][x]==3)
            {
                start->x=x;
                start->y=y;
            }
            if(maze[y][x]==4)
            {
                end->x=x;
                end->y=y;
            }
        }

    return maze;
}

PtrtoStack MazePath(MazeType Maze,PtrtoPos start,PtrtoPos end)
{
    int curstep=1;
    PtrtoPos curpos;
    PtrtoRecord e;
    PtrtoStack Path;

    curpos=(PtrtoPos)malloc(sizeof(PosType));
    e=(PtrtoRecord)malloc(sizeof(Record));

    curpos->x=start->x;
    curpos->y=start->y;

    Path=InitStack();
    do
    {
        if(Pass(curpos))    //当前位置可以通过
        {
            if(curpos->x==end->x&&curpos->y==end->y)
                return Path;    //到达出口
            FootPrint(curpos);    //留下足迹
            e->ord=curstep;
            e->seat.x=curpos->x;
            e->seat.y=curpos->y;
            e->direction=DOWN;
            Push(Path,e);    //加入路径
            NextPos(curpos,DOWN);    //下一位置变为当前位置
            curstep++;
        }
        else    //当前位置不可通
        {
            if(!StackEmpty(Path))
            {
                Pop(Path,e);
                while(e->direction==RIGHT&&!StackEmpty(Path))
                {
                    MarkPrint(e);
                    Pop(Path,e);
                }
                if(e->direction<RIGHT)
                {
                    e->direction++;
                    Push(Path,e);
                    curpos->x=Path->base[Path->top-1].seat.x;
                    curpos->y=Path->base[Path->top-1].seat.y;
                    NextPos(curpos,e->direction);
                }
            }
        }
    }
    while(!StackEmpty(Path));

    return 0;
}

PtrtoStack InitStack(void)
{
    PtrtoStack p;
    p=(PtrtoStack)malloc(sizeof(SqStack));
    p->base=(PtrtoRecord)malloc(sizeof(Record)*INITSTACKSIZE);
    p->top=0;
    p->stacksize=INITSTACKSIZE;
    p->length=0;
    return p;
}
void Push(PtrtoStack Path,PtrtoRecord e)
{
    if(Path->length>=Path->stacksize)
    {
        Path->base=(PtrtoRecord)realloc(Path->base,sizeof(Record)*(Path->stacksize+INCREMENTSIZE));
        Path->stacksize+=INCREMENTSIZE;
        if(!(Path->base))
        {
            printf("error\n");
            exit(0);
        }
    }
    Path->base[Path->top].ord=e->ord;
    Path->base[Path->top].seat.x=e->seat.x;
    Path->base[Path->top].seat.y=e->seat.y;
    Path->base[Path->top].direction=e->direction;
    Path->top++;
    Path->length++;
}
void Pop(PtrtoStack Path,PtrtoRecord e)
{
    if(StackEmpty(Path))
    {
        printf("Empty Stack\n");
        exit(0);
    }
    Path->top--;
    e->ord=Path->base[Path->top].ord;
    e->seat.x=Path->base[Path->top].seat.x;
    e->seat.y=Path->base[Path->top].seat.y;
    e->direction=Path->base[Path->top].direction;
}

void FootPrint(PtrtoPos point)
{
    Maze[point->y][point->x]=MARK;
    system("CLS");
    printf("\a");
    printf_maze_and_path(Maze);
    sleep((int)1);//暂停一秒
}

void NextPos(PtrtoPos curpos,int direction)
{
    switch(direction)
    {
    case DOWN :
        curpos->y++;
        break;
    case LEFT :
        curpos->x--;
        break;
    case UP :
        curpos->y--;
        break;
    case RIGHT :
        curpos->x++;
        break;
    }
}

void MarkPrint(PtrtoRecord e)
{
    Maze[e->seat.y][e->seat.x]=BLIND_ALLEY;
    system("CLS");
    printf("\a");
    printf_maze_and_path(Maze);
    sleep((int)1);
}

int Pass(PtrtoPos point)
{
    if(Maze[point->y][point->x]==0||Maze[point->y][point->x]==3||Maze[point->y][point->x]==4)
        return 1;
    else
        return 0;
}

void Print_Path(PtrtoStack Path)
{
    if(Path==NULL)
    {
        printf("no path\n");
        exit(0);
    }
    int i=0;
    for(; i<Path->top-1; i++)
        printf("(%d,%d)→",Path->base[i].seat.x,Path->base[i].seat.y);
    printf("(%d,%d);\n",Path->base[i].seat.x,Path->base[i].seat.y);
}

void DestroyStack(PtrtoStack Path)
{
    free(Path->base);
    free(Path);
}

int StackEmpty(PtrtoStack Path)
{
    if(Path->top==0)
        return 1;
    else
        return 0;
}

void FreeMaze(MazeType Maze)
{
    int i;
    for(i=0; i<Maze_Line; i++)
        free(Maze[i]);
    free(Maze);
}
/*
//测试数据//
5 5
1 1 1 1 1
1 3 0 0 1
1 1 1 0 1
1 4 0 0 1
1 1 1 1 1
*/
/*
10 10
1 1 1 1 1 1 1 1 1 1
1 1 1 0 3 0 0 0 0 1
1 0 0 0 0 0 0 0 0 1
1 1 0 0 0 0 1 1 0 1
1 1 1 1 0 0 0 0 1 1
1 1 1 1 1 0 0 0 1 1
1 0 1 0 0 1 0 0 0 1
1 1 0 0 1 0 0 1 1 1
1 4 1 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1
*/
/*
19 19
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 3 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1
1 0 1 1 1 1 0 0 0 0 1 0 1 1 1 1 1 0 1
1 1 0 0 0 1 0 0 1 0 0 0 1 1 1 0 0 1 1
1 1 0 0 0 0 1 0 0 0 0 0 0 1 0 1 1 0 1
1 0 0 1 0 0 1 0 1 1 0 0 0 1 1 0 1 1 1
1 0 1 0 0 0 1 0 0 0 1 1 1 0 0 0 1 0 1
1 0 0 1 1 0 0 0 0 1 0 0 0 1 0 1 0 0 1
1 0 0 1 0 1 0 0 0 1 1 1 1 0 1 0 0 1 1
1 0 0 0 1 1 1 0 1 0 0 0 0 1 1 0 0 0 1
1 0 1 1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 1
1 0 0 0 1 0 1 0 1 0 0 1 0 1 0 0 0 0 1
1 0 0 0 0 1 1 1 1 1 0 0 0 0 0 1 0 0 1
1 0 0 0 0 1 1 1 1 1 0 0 1 1 1 1 0 1 1
1 0 0 0 0 1 1 1 0 0 0 0 1 1 0 0 0 0 1
1 0 0 1 0 1 1 1 1 0 1 0 0 1 0 0 1 0 1
1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 1
1 0 1 0 1 1 0 0 0 0 1 0 0 1 1 4 0 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

100 100
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 0 0 0 1 1 0 1 1 0 0 0 1 0 0 0 1 0 0 0 1 1 1 0 0 0 1 0 0 1 0 0 1 1 0 0 0 0 1 0 0 0 1 0 1 0 0 1 1 0 0 1 0 1 0 0 0 0 1 1 1 0 1 0 0 1 0 1 0 0 0 1 1 1 0 1 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 1 1
1 0 0 0 1 0 0 1 1 1 0 0 0 1 0 1 0 1 0 0 1 0 1 0 0 1 0 0 1 3 0 0 0 1 1 1 1 1 0 0 0 1 0 1 0 0 0 1 0 0 0 0 1 1 1 1 1 0 0 1 1 1 1 0 1 1 0 0 0 0 0 1 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 1 1 1 1 0 1 0 0 1 1
1 1 0 1 1 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 0 1 1 0 1 0 0 1 0 0 1 1 0 0 0 1 1 1 0 0 0 1 0 1 1 0 1 1 0 0 1 1 0 0 0 1 0 0 0 1 1 1 0 1 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 1 1 1 1 0 1 0 1 0 1
1 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 1 1 0 1 1 0 0 0 0 1 0 0 0 0 1 1 0 1 0 1 0 1 0 0 0 0 0 0 0 1 1 0 1 1 1 1 0 1 0 1 1 1 0 1 1 1 0 0 1 0 0 0 1 1 0 1 0 1 0 0 0 0 1 0 1 0 0 1 0 1 1 1 0 0 0 1 0 0 0 1
1 0 0 0 0 1 1 1 0 1 1 1 1 0 1 1 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 1 0 1 0 0 1 1 0 1 0 1 0 0 1 1 0 0 0 0 1 1 1 1 0 0 1 0 0 0 0 1 1 1 1 0 0 0 1 1 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 1
1 0 1 1 1 0 0 0 0 1 0 1 1 0 1 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 1 1 1 0 0 1 0 0 0 0 1 0 0 0 0 1 1 0 1 1 1 1 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 1 0 1 0 1 1 1 0 0 1 1 1 0 1 1 1 1 1 1 0 1 0 0 1 1 0 1 1
1 1 1 0 0 0 0 1 0 1 1 0 1 1 0 0 0 1 1 0 0 1 0 1 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 1 0 0 0 1 1 1 1 0 1 1 1 1 1 1 1 1 0 0 0 0 1 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 1 1 0 1 1 0 0 0 0 1 1 0 1
1 1 0 1 0 0 0 1 0 0 0 0 1 1 0 0 1 1 1 1 1 1 1 0 0 0 0 1 0 0 0 1 1 1 1 0 1 1 1 0 1 1 0 1 0 0 0 1 1 0 0 0 1 1 1 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 1 1 1 1 1 0 1 1 1 0 0 0 1 1 0 1
1 1 0 0 1 0 0 0 0 0 0 1 0 1 1 1 1 0 1 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 1 0 0 0 1 0 0 1 0 0 0 1 1 1 0 0 1 1 1 0 1 1 0 0 0 0 1 1 0 1 0 1 1 1 0 0 0 0 1 0 1 1 0 0 0 1 0 0 1 1 0 1 1 0 0 1 0 0 0 0 1 0 1
1 0 1 0 1 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 1 1 0 1 0 1 1 1 1 1 0 0 0 0 1 1 1 0 1 1 1 1 0 1 0 1 1 1 0 1 0 0 0 0 0 1 0 0 1 1 0 0 1 0 0 1 1 0 0 1 1 1 0 1 0 0 0 0 0 0 0 1 0 1 0 1 1 0 0 1 0 1 0 0 1 0 0 0 1 1
1 0 1 0 1 1 0 0 0 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0 1 0 0 1 1 0 0 0 1 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 1
1 1 0 0 0 0 1 0 1 1 1 0 1 0 1 0 1 1 0 1 0 0 0 0 0 1 0 0 0 1 1 1 1 0 1 1 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 1 1 1 1 0 0 0 1 1 0 1 1 0 0 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 1
1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 1 0 1 1 0 0 0 0 1 1 0 0 0 1 1 1 1 1 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 1 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 1 1 1 1 0 0 0 1 0 0 0 0 0 1 0 1 0 1 0 1
1 0 0 1 1 0 1 0 1 1 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 1 0 0 1 1 1 1 0 0 1 0 0 1 0 1 0 0 0 1 0 0 0 0 1 1 0 0 0 1 0 0 1 0 1 0 0 0 1 1 1 0 0 1 0 1 0 1 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 1
1 0 1 0 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 1 1 0 0 1 1 0 0 1 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 1 0 1 0 0 1 1 1 1 0 0 0 1 1 0 1 0 1 0 0 1 0 0 0 1 0 0 0 1
1 0 1 0 1 0 0 0 1 0 1 1 0 0 1 0 1 0 0 0 0 0 0 0 1 0 1 0 1 1 1 1 1 0 0 0 1 0 1 0 1 0 0 1 1 0 0 1 0 0 0 1 1 1 0 1 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 1 0 1 0 0 1 0 1 1 0 0 1 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1
1 1 0 0 1 1 0 0 1 0 0 0 0 1 0 0 1 0 0 0 1 1 0 0 1 0 0 1 1 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 1 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 1 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 1
1 0 0 0 1 1 0 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 0 1 1 1 1 0 0 1 0 0 0 0 0 1 0 0 1 1 0 0 1 0 1 0 1 1 0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 1 1 1 0 0 0 0 0 0 1 0 1 1 1 1 1
1 0 0 0 1 1 0 0 1 1 0 0 1 0 1 0 1 0 0 1 0 1 0 1 1 0 1 0 0 1 1 1 1 0 1 1 1 1 1 0 1 0 0 1 1 1 1 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 1 1 0 1 0 1 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 1
1 0 0 1 1 0 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 1 1 0 1 1 1 1 0 0 0 0 1 1 0 0 1 0 0 1 1 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 0 0 0 0 0 1 1 0 1 1 1 0 0 0 1 1 0 0 0 1 0 0 0 0 0 1 1 1 1
1 0 1 0 1 1 1 1 1 0 0 1 1 0 1 0 0 0 1 1 0 0 0 0 1 1 0 0 0 1 0 0 1 1 0 0 1 0 0 0 1 1 1 0 0 1 1 1 0 0 0 0 1 0 1 1 0 0 0 1 1 1 0 1 0 1 1 1 0 0 0 1 0 0 0 1 1 0 0 0 1 0 1 1 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 1
1 0 0 0 0 0 0 1 0 0 1 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 0 0 0 0 1 0 1 1 1 1 1 0 1 1 0 0 0 1 1 0 0 0 0 0 0 1 1 0 1 0 1 0 0 0 0 0 0 1 1 1 0 0 1 0 1 0 0 0 1 0 0 1 0 1 1 0 0 0 1 1 1 1 0 0 1
1 1 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 1 1 0 1 1 1 1 0 1 0 1 1 1 1 1 0 1 1 0 0 0 1 1 1 0 0 0 0 1 0 0 1 1 0 1 1 1 0 0 0 0 1 1 0 0 0 1 1 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1
1 0 1 0 0 0 0 1 1 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 1 0 0 1 0 1 1 0 0 0 0 0 0 1 0 1 1 1 1 1 1 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 1 1 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 1 0 0 0 1 1 1
1 1 0 1 1 1 1 0 0 0 1 1 1 1 1 0 0 0 1 0 0 1 0 0 1 1 1 0 1 0 0 0 0 1 1 1 1 0 0 1 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 1 1 0 0 0 0 0 0 1 1 0 0 0 1 0 1 0 1 0 1 0 0 0 1 1 1 0 1 0 1 0 0 1
1 1 1 0 1 0 0 1 0 1 0 0 0 1 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 1 0 1 1 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1
1 0 1 1 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 0 1 1 0 0 0 0 0 0 0 1 0 1 1 1 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 1 1 0 0 0 1 0 1 0 0 0 1 1 0 1 0 0 1 1 0 0 1 1 0 1 1 0 1 1 0 0 0 0 1 1 1
1 1 0 0 0 1 1 0 1 1 0 0 0 0 1 1 0 1 1 0 0 1 1 0 0 1 0 1 0 1 1 1 0 1 1 1 1 0 0 1 0 1 0 0 1 0 1 1 0 1 0 1 1 1 0 0 0 1 0 1 0 0 0 0 1 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 1
1 0 1 1 1 0 0 0 0 1 0 0 0 0 0 1 0 1 1 0 0 0 1 0 0 1 0 1 0 0 1 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 0 0 1 1 1 0 1 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 1 1 0 1 0 0 1 1 1 1 0 1 1 0 0 1 0 0 0 0 0 1 1 1 0 0 1 0 1 1
1 0 0 1 1 0 0 0 0 0 0 1 0 1 0 0 0 1 0 1 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 1 1 1 1 0 1 1 1 0 0 1 1 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 1 1 0 1 1 1 0 0 0 0 1 0 0 1 1 0 0 0 1 0 1 0 0 0 0 1 0 0 0 1
1 1 0 0 1 0 0 1 1 1 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 1 0 1 1 0 1 0 0 1 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 1 0 1 1 0 0 1 1 0 0 1 1 0 1 0 0 0 1 0 0 1 1 1 0 0 1 0 1 1 1
1 1 1 0 0 1 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 0 0 1 0 1 0 1 0 0 1 0 1 0 0 1 0 1 0 0 0 0 1 1 1 0 0 1 0 1 0 0 0 1 0 1 0 1 0 1 0 0 1 1 0 1 0 0 0 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 0 0 0 1 1 0 1 1 0 0 1 1 1
1 0 0 0 0 0 1 0 1 0 0 0 1 1 0 0 0 1 0 0 1 1 0 1 0 0 0 0 1 0 1 1 1 0 0 1 0 0 0 1 1 1 0 0 0 1 1 0 1 1 0 1 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 1 1 1 0 0 1 0 0 1 1 0 0 0 1 1 0 1 0 0 0 0 0 0 0 1
1 0 0 1 0 0 0 1 1 1 1 1 1 0 1 1 0 0 0 1 1 1 1 0 1 1 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 1 1 1 1 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 1 1 1 0 0 0 0 1 1 0 0 0 1
1 1 0 0 0 0 0 0 0 1 0 0 0 1 1 0 1 1 0 1 1 0 0 1 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 0 0 1 0 0 0 0 1 0 0 1 0 0 1 0 0 1 1 0 0 0 1 0 0 0 0 1 1 0 1 0 0 0 0 1 1 1 1 0 1 1
1 1 0 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 1 0 0 0 1 1 0 1 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 1 0 0 0 1 1 1 1 0 1 0 0 0 1 1 1 1 1 0 0 0 1 0 0 0 1 1 1 0 0 1 0 0 1 0 0 0 0 1 1 0 0 0 1
1 1 0 0 0 0 1 1 0 0 0 1 0 1 1 0 0 0 1 1 0 0 1 1 0 1 1 1 1 0 0 0 0 0 1 0 1 1 0 0 0 1 0 1 0 1 0 0 1 0 1 0 0 1 0 0 0 0 0 1 0 1 1 1 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 1 0 0 0 1 0 1 1 0 0 1 0 0 0 1 0 1
1 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 1 0 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 1 0 0 1 1 1 0 1 0 1 1 1 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 1 1 1 0 1 0 0 1 1 0 1 0 1 1 0 1 1 1 0 0 0 0 0 0 1
1 0 1 0 0 1 0 1 1 0 1 0 1 0 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 1 1 0 0 1 0 0 0 1 0 0 1 0 1 1 0 0 0 0 1 0 1 0 0 1 0 1 0 0 0 0 1 0 1 1 0 1 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 1 1
1 1 0 0 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 1 1 0 1 1 0 1 0 1 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 0 1 0 0 0 1 0 0 1 1 0 1 0 0 0 1 1 0 0 0 0 1 0 0 1 0 0 1 1 0 1 1 1 0 0 0 0 0 1 0 1 1 0 1 1 0 1 1 0 0 0 0 0 1 1
1 0 0 0 1 0 0 0 1 0 1 0 0 0 0 1 1 0 1 0 0 1 1 1 1 1 1 0 0 1 1 0 1 0 1 1 0 1 1 1 0 0 0 0 0 0 1 1 0 1 0 1 0 0 0 0 1 0 1 1 1 1 1 0 0 0 0 0 1 1 0 0 0 0 1 0 0 1 0 1 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 0 0 0 1 1
1 1 0 0 0 1 1 0 1 1 0 0 0 1 1 0 0 0 1 1 1 0 0 1 1 0 0 1 1 0 0 0 1 1 1 1 0 0 1 0 0 1 0 0 0 0 0 1 1 0 0 1 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 1 1 0 1
1 1 1 0 0 0 1 0 0 1 1 0 0 0 1 1 0 0 0 1 1 1 1 1 1 0 0 1 0 1 0 1 1 1 0 1 0 1 1 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 1 1 1 0 0 1 1 0 0 0 0 1 1 0 1 0 1 1 1 1 1 0 0 0 1 1 0 0 0 0 0 1 0 0 1 0 1 1 0 0 0 1
1 0 1 0 0 1 1 0 1 0 0 1 1 1 1 0 1 1 0 1 0 1 1 1 1 1 1 0 0 1 0 0 1 1 1 0 0 0 1 1 0 0 0 0 1 0 0 1 1 0 0 0 0 1 1 0 1 0 0 0 0 1 0 0 0 1 0 1 1 0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 1 0 1 0 0 1 1 0 0 0 1 0 1
1 0 1 0 1 0 0 1 0 0 0 1 1 0 1 1 0 1 0 1 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 0 0 0 1 1 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 1 0 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 0 1
1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 1 0 0 1 0 0 1 0 1 0 0 1 1 0 1 0 1 1 1 0 0 1 0 0 0 0 1 0 1 0 1 0 0 0 1 0 0 1 1 0 1 0 0 0 0 0 0 1 1 1 0 0 0 1 0 1 1 0 0 1 0 0 1 0 0 1 0 1 0 1 0 0 0 0 0 1 1 0 1 1 1 0 0 1
1 0 0 1 1 1 1 1 0 1 1 0 0 1 0 0 0 1 0 1 1 0 0 0 1 1 1 0 0 0 1 0 0 0 0 1 0 0 1 0 0 1 1 1 1 1 1 1 1 0 1 1 1 0 0 0 1 1 1 0 0 1 1 0 1 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 1 1 0 1 0 0 1
1 1 0 1 0 0 1 1 1 1 0 1 1 0 1 1 1 0 1 0 1 1 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 1 1 0 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 1 1 1 0 1 1 0 0 1 1 0 0 1 0 1 1 1 1 1 0 0 0 0 1 0 1 0 0 0 1 0 1 1 0 1 0 1 1 0 0 1
1 0 0 0 0 0 0 1 0 0 1 0 1 0 0 1 0 1 0 0 0 1 0 0 1 0 1 0 0 1 1 0 0 0 0 1 0 1 0 1 0 1 0 1 1 0 0 0 0 0 0 1 0 1 1 1 0 1 1 1 1 0 1 1 0 0 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 1 1 0 0 0 0 1 0 0 1
1 1 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 1 0 0 0 1 0 0 1 0 1 1 0 1 1 1 0 0 1 0 1 0 1 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 1 0 1 0 0 1 1 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1
1 0 0 1 0 0 1 1 0 0 1 0 0 1 0 0 0 1 0 0 1 1 0 0 0 0 1 0 1 0 1 0 0 0 1 0 1 0 0 0 0 1 1 1 0 0 1 0 1 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 1 1 1 1 0 0 0 1 0 0 1 0 0 0 0 0 1 0 1 0 1 1 0 1 0 0 1 0 0 0 0 1 0 1 1
1 1 1 0 0 1 1 0 1 1 1 1 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0 1 0 1 0 1 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 1 0 0 1 1 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 1 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1
1 0 1 0 0 1 0 0 0 0 1 0 1 0 0 0 1 1 1 0 0 1 1 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 1 0 0 0 1 0 1 0 0 1 0 1 1 0 0 0 0 0 0 1 0 0 1 0 1 0 1 0 1 1 1 0 0 1 1 0 0 0 0 1 1
1 0 1 0 0 0 0 1 1 1 1 0 1 1 0 0 0 1 0 1 1 1 1 0 0 1 0 0 1 1 0 1 1 1 0 0 1 1 1 1 0 1 1 1 1 1 0 0 0 1 1 0 0 0 1 0 0 0 1 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 1 0 1 1 0 0 1 0 1 0 1 0 0 1 1 1 1 1 0 1 0 0 0 0 1 1
1 1 1 1 1 0 1 1 1 0 0 1 0 0 1 1 0 1 0 1 0 0 0 1 1 1 1 0 0 0 0 1 1 0 1 0 1 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 1 0 1 1 1 0 1 0 0 0 1 0 1 0 0 0 1 0 0 1 0 1 0 1 0 0 1 0 0 0 0 0 0 1
1 1 0 1 0 1 0 1 1 1 0 0 0 1 0 0 0 1 0 1 0 0 0 1 0 0 1 1 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 1 1 0 0 1 1 0 1 0 0 1 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 1 0 1 1 0 0 1 0 0 1 0 0 1 0 1 1
1 1 0 0 0 0 0 0 0 0 1 1 0 1 0 1 1 0 0 0 1 1 1 0 1 0 0 1 1 0 0 1 0 0 0 0 1 0 0 1 1 0 0 1 0 0 0 1 1 0 0 1 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 1 0 1 1 1 1 1 0 0 0 0 1 0 0 0 1 1 1 1 1 0 1 0 1 1 1 1 1
1 1 1 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 1 0 1 1 0 1 1 0 1 0 0 0 1 1 0 0 0 1 1 0 1 0 1 1 0 0 1 1 0 0 0 1 0 0 1 1 0 1 0 1 1 0 1 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1 1 0 0 0 1 0 0 0 0 1 0 0 1 1 1 0 0 1 1
1 1 1 1 0 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 1 0 1 0 1 0 0 0 0 0 1 0 1 1 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 1 1 0 0 0 1 1 1 1 0 1 1 1
1 1 1 0 0 1 0 1 1 0 0 0 1 1 1 0 1 0 0 1 0 0 0 0 0 1 1 0 1 0 1 0 0 0 1 0 0 1 0 1 1 1 0 1 0 0 0 1 1 1 1 0 1 0 0 1 0 1 0 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 0 0 1 0 1 1
1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1 1 0 1 1 1 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 1 1 1 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 1 0 0 1 0 0 1 0 0 0 1 0 1 1 0 1 0 0 1
1 0 0 0 0 1 0 1 0 1 0 1 0 1 1 0 1 0 0 0 1 0 0 1 1 0 0 1 1 1 0 0 1 1 1 1 0 0 0 1 0 0 0 1 0 1 0 0 1 0 1 1 0 1 1 0 0 0 1 0 1 1 0 1 1 1 0 0 1 1 0 0 0 0 0 0 0 1 0 1 0 0 0 1 1 1 1 0 1 1 0 0 1 1 1 1 1 1 0 1
1 0 0 1 0 1 1 0 0 1 1 0 0 1 1 0 0 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 1 0 1 1 0 0 1 0 0 1 1 0 1 1 0 1 1 1 1 0 0 0 1 0 0 0 0 1 0 0 1 0 1 0 1 1 0 0 0 0 1 0 1 0 0 0 1 1 0 0 1 0 0 1 1 0 0 1 0 1 0 0 1 1 1 1 1
1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 1 1 1 0 0 0 0 1 1 0 1 0 0 0 1 0 0 0 1 0 1 0 1 0 1 1 0 1 1 1 1 0 1 1 0 1 1 1 1 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 1
1 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 1 1 1 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 1 1 0 1 1 0 1 1 1 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 1 1 1 0 1 0 1 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 1 0 0 0 0 0 1 0 0 1 0 1
1 1 0 1 1 0 0 1 0 0 0 0 0 1 1 1 1 0 0 1 0 0 1 1 0 1 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 1 0 1 0 0 1 1 0 1 1 0 0 0 0 1 1 0 0 0 1 1 0 1 0 1 0 0 1 0 1 0 1 1 0 0 0 1 1 0 1 1 1
1 1 0 1 1 1 0 0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 0 1 0 1 0 1 0 0 0 0 0 0 1 1 1 1 0 1 1 1 0 0 1 0 1 0 1 0 1 0 0 1 0 0 1 0 1 1 0 0 1 1 1 1 0 1 0 0 0 1 1 0 0 0 0 1 1 0 0 1 1 0 0 0 1 1 0 0 1 0 1 1 1
1 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 1 1 1 0 1 0 0 1 0 0 1 0 0 0 1 0 0 0 0 1 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 1 1 0 1 1 1 1 1 1 0 1 0 1 0 1 0 0 0 0 0 1 0 1 0 0 0 0 1 1 1 0 0 0 0 1 0 1 1 1 0 0 1 0 0 1 1 1
1 1 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 1 1 0 0 1 0 1 0 1 0 0 1 1 1 0 1 1 0 1 1 1 1 0 1 0 0 0 0 0 0 1 0 1 0 0 1 1 0 1 1 0 0 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 0 0 1 1 1 1 0 0 0 1 1 0 0 0 1 0 0 1
1 0 0 0 1 0 1 0 1 0 0 0 0 0 0 1 0 1 1 1 0 0 1 1 1 1 0 0 1 0 0 1 0 0 0 1 0 1 0 1 0 1 0 0 0 1 0 1 1 0 0 0 1 0 1 0 0 0 0 1 0 1 1 1 0 1 1 0 0 0 1 0 1 0 1 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1
1 0 1 0 0 1 0 1 0 0 0 0 0 1 0 0 0 1 1 0 1 0 0 1 0 1 0 0 1 1 0 0 0 0 1 0 1 0 1 0 1 1 0 0 1 1 1 0 1 0 1 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 1 1 1 1 0 1 0 1 1 0 1 1 1 0 1 0 0 1 0 1 0 1 1 1 0 0 0 0 1 0 0 0 0 1
1 0 0 1 1 1 0 1 0 1 1 0 1 0 0 1 0 0 0 1 1 0 0 1 0 0 0 0 0 1 1 0 0 1 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 1 0 0 0 1 0 0 0 1 1 0 0 0 0 1 0 1 1 0 0 0 0 1 0 1 1 0 1 0 1 0 0 0 1
1 0 0 0 1 0 1 0 1 0 1 0 1 0 0 1 1 1 1 0 0 0 1 1 1 0 0 0 0 0 0 0 1 0 0 1 1 1 1 0 1 0 1 1 0 1 1 1 0 0 0 1 0 0 0 0 1 0 1 1 1 1 0 0 1 0 0 1 1 0 0 1 0 0 1 0 1 0 1 1 1 0 1 0 1 0 0 0 0 1 1 0 1 0 0 1 0 1 0 1
1 0 0 1 1 0 1 1 0 1 1 1 0 1 1 0 1 0 1 0 1 0 0 0 0 1 1 1 0 0 1 1 1 1 1 0 0 1 1 1 1 0 1 0 0 0 0 1 1 0 1 1 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 1 1 0 0 1 0 0 0 0 0 0 0 0 1 1 1 1 0 1 0 1
1 0 0 1 0 0 0 1 1 1 0 0 1 1 0 0 1 1 1 0 1 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 1 0 1 1 0 0 0 0 1 1 0 1 1 0 1 0 0 0 0 0 0 0 1 1 1 1 0 1 0 0 0 0 0 1 1 0 1 0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 0 1
1 0 0 0 1 1 0 0 0 1 1 0 1 1 1 1 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 1 0 1 0 1 0 1 1 1 0 1 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 1 0 0 1 1 0 0 0 1 1 0 1 1 1 1 0 0 1 0 0 0 0 0 0 0 0 1 1 1
1 1 0 0 0 0 1 1 1 1 0 1 0 1 0 1 0 1 0 1 0 0 0 1 1 0 0 1 1 1 1 0 1 0 0 0 1 0 1 1 1 0 0 1 0 0 0 1 0 1 1 1 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 1 0 1 0 0 1 1 1 0 1 1 0 0 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1
1 1 1 1 0 0 0 1 0 0 1 0 0 0 1 1 1 0 0 1 1 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 1 0 0 1 1 0 0 0 0 1 1 0 0 1 1 0 0 0 1 0 1 1 0 0 0 0 0 1 0 1 1 0 1 0 0 1 1 1 0 1 1 0 0 1 1 0 0 1 0 0 0 0 1
1 0 0 0 0 1 1 0 0 1 0 0 1 1 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 1 0 1 0 1 0 0 1 1 1 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 1 1 1 0 0 1 1 1 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 1
1 0 0 0 0 0 1 0 0 1 0 0 0 0 1 1 0 1 1 0 1 1 1 0 1 0 0 1 1 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 0 1 1 1 0 1 1 0 0 0 1 1 0 0 0 0 0 0 1 0 1 1 0 0 1 0 1 0 0 0 0 0 1 1 0 1 0 0 0 1 1 0 0 1 1 0 0 0 0 0 0 1 1
1 0 0 0 0 0 0 1 0 0 0 1 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 1 1 1 0 0 0 1 1 1 0 0 0 0 1 0 1 1 0 1 0 1 1 0 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 1 0 0 0 0 1 0 0 1 0 1 0 0 1 1 0 1 1 1 1
1 1 0 0 0 1 1 1 1 0 1 0 0 1 0 0 0 1 0 1 1 1 0 1 1 0 1 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 1 1 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 1 1 1 1 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1
1 0 1 0 1 1 0 1 0 1 0 1 0 0 0 0 1 1 0 1 1 1 0 1 1 0 1 1 1 1 0 0 0 0 1 1 0 1 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 1 1 0 1 1 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 1 0 0 0 0 1 0 0 1 0 1 1
1 0 1 1 1 1 0 0 0 0 1 0 1 1 0 0 0 1 1 0 0 0 0 1 1 0 0 1 0 0 1 0 0 0 0 0 0 1 1 1 0 0 1 1 0 1 0 1 1 0 0 0 0 0 0 0 1 1 0 1 0 0 1 1 0 0 1 0 0 0 1 1 0 1 0 1 0 1 1 1 0 1 1 1 1 1 1 0 1 0 0 1 0 0 1 0 0 0 0 1
1 1 0 1 1 0 0 0 1 0 0 0 0 0 1 0 1 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 1 0 0 0 0 1 1 0 0 0 0 1 1 1 0 1 0 0 0 1 0 0 0 1 0 0 1 1 1 0 1 0 0 0 0 1 1 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 1 1 0 1
1 1 1 1 1 0 0 0 0 1 1 1 0 1 0 0 1 0 0 1 0 0 1 0 0 0 1 0 0 1 1 0 1 1 0 0 1 0 1 1 0 1 0 1 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 1 1 1 0 0 1 1 0 0 0 1 0 0 0 0 0 1
1 0 0 0 0 1 0 0 1 0 1 1 1 1 1 0 1 0 1 1 0 1 1 0 1 1 0 1 0 1 1 1 1 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 1 0 1 0 1 0 0 1 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 1 0 0 0 1
1 0 1 0 0 1 0 1 1 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 1 1 0 1 1 0 0 1 0 0 1 0 1 0 0 1 0 1 0 1 1 0 1 0 0 1 0 0 0 0 1 1 1 1 1 0 1 0 1 1 0 1 1 1 1 0 1 1 0 1 0 1 1 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 1 1 1
1 0 0 0 0 1 0 0 0 0 1 1 0 1 1 1 1 0 0 0 0 0 0 1 0 0 1 0 1 0 0 1 1 0 0 1 0 1 0 1 0 0 1 0 0 1 0 1 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 1 1 0 0 1 0 0 1 1 0 0 0 0 1 1 0 1
1 0 0 1 0 0 1 1 0 1 1 1 0 1 0 1 1 0 1 0 1 0 1 0 0 1 0 0 0 1 1 0 1 0 1 0 0 1 0 0 1 0 0 1 0 1 0 0 1 0 0 0 0 1 0 0 0 1 1 1 0 0 1 0 0 0 0 0 1 1 0 0 0 1 1 1 0 0 0 0 1 0 1 0 0 1 1 1 0 0 0 1 1 1 0 0 0 0 1 1
1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 1 0 1 1 1 1 1 0 1 1 0 1 0 1 1 0 1 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 1 1 1 0 1 1 0 0 0 0 1 1 0 0 1 1 1 1 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 1 1 1
1 1 0 0 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 1 0 0 0 1 0 0 1 1 0 0 1 1 0 1 0 1 0 0 1 0 1 1 0 1 0 0 0 0 0 1 0 0 1 0 0 1 1 1 0 0 1 1 0 0 0 0 1 0 0 1 1 0 1 0 1 0 0 1 1 0 0 0 0 1 0 1 1 0 0 1 0 1 1 1 4 1 0 0 1
1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 1 1 1 0 1 0 1 0 0 1 1 0 0 1 1 1 0 0 0 0 0 1 0 0 1 1 1 1 1 1 1 0 1 0 1 1 1 0 0 0 0 1 0 1 1 1 1 0 0 0 0 1 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 1 0 1
1 0 1 1 1 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 1 0 1 1 0 1 0 1 0 0 1 0 0 0 1 0 1 1 1 0 0 0 1 1 1 0 0 1 0 1 0 1 0 0 0 0 1 1 1 0 0 0 0 0 1 1 0 0 0 1 0 1 1 0 1 0 1 0 1 1 1 0 0 0 1 1 0 1 0 1 0 1 1 0 1 0 0 0 0 1
1 0 0 0 1 0 1 0 1 0 1 0 1 0 1 1 1 1 0 0 1 0 1 0 0 1 0 0 0 0 0 1 0 1 1 0 1 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 1 0 0 1 1 1 0 0 0 0 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 1
1 0 1 0 1 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 1 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 1 0 0 1 1 0 1 0 0 0 1 1 1 0 1 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 1 1 1
1 1 1 1 0 1 1 0 0 0 1 0 1 1 0 0 1 0 0 0 0 1 0 1 0 0 1 1 1 0 1 1 0 0 1 1 1 1 0 1 1 1 1 0 1 0 0 0 0 0 1 0 1 0 1 0 1 0 0 1 0 1 0 0 1 0 0 1 1 0 0 0 1 0 0 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 1 1 1 0 0 0 0 0 0 1
1 0 1 0 1 1 1 0 1 1 0 0 1 1 0 0 0 1 0 0 0 0 1 0 1 1 1 0 0 1 0 0 0 1 0 1 0 0 0 0 1 0 1 0 1 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 1 0 1 0 1 1 1 0 1 0 1 1 0 0 0 1 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
*/