#include<iostream>
#include<time.h>

using namespace std;

int** buildboard(int size);
void pizurNekudot(int **board, int size);
void print(int **arr, int size, int generation);
void ongoing(int **board, int size);
bool rules(int **board, int size, int rowkey, int colkey, bool alive);
void swaparr(int **board, int **temp, int size);
bool alldead(int **board, int size);


int main()
{
    srand(time(NULL));
    int size;
    cin >> size;
    int **board = buildboard(size);

    pizurNekudot(board, size);
    print(board, size, 0);
    ongoing(board, size);
    system("PAUSE");
}

int** buildboard(int size)// create 2d array as a board
{
    int ** board = new int*[size];
    for (int i = 0; i < size; i++)
    {
        board[i] = new int[size];
    }
    for (int i = 0; i < size; i++)
    {
        for (int g = 0; g < size; g++)
        {
            board[i][g] = 0;
        }
    }
    return board;
}

void pizurNekudot(int **board, int size)// randomly select 25% of the board
{
    int randomRow, randomCol;

    for (int i = 0; i < (size*size) / 4; i++)
    {
        int randomRow = rand() % size;
        int randomCol = rand() % size;
        if (board[randomRow][randomCol] == 1)
        {
            i--;
        }
        board[randomRow][randomCol] = 1;
    }
}

void print(int **arr, int size, int generation) // print the array & generation
{
    cout << "generation" << generation << endl;
    for (int i = 0; i < size; i++)
    {
        for (int g = 0; g < size; g++)
        {
            cout << arr[i][g] << " ";
        }
        cout << endl;
    }
    cout << endl << endl << endl;
}

bool rules(int **board, int size, int rowkey, int colkey, bool alive)//get an element and return if he need to be alive or dead by the rules of the game
{
    int alives;

    //only if the element is corner
    if (rowkey == size-1 && colkey == 0)
    {
        alives = board[rowkey - 1][colkey] + board[rowkey - 1][colkey + 1] + board[rowkey][colkey + 1];
    }
    if (rowkey == 0 && colkey == size-1)
    {
        alives = board[rowkey + 1][colkey] + board[rowkey + 1][colkey - 1] + board[rowkey + 1][colkey];
    }
    if (rowkey == 0 && colkey == 0)
    {
        alives = board[rowkey + 1][colkey] + board[rowkey + 1][colkey + 1] + board[rowkey][colkey + 1];
    }
    if (rowkey == size-1 && colkey == size-1)
    {
        alives = board[rowkey - 1][colkey] + board[rowkey - 1][colkey - 1] + board[rowkey][colkey - 1];
    }

    // only if the element is edge
    if(rowkey == size -1 && (colkey!= 0 && colkey != size-1))
    {
        alives = board[rowkey - 1][colkey] + board[rowkey - 1][colkey - 1] + board[rowkey][colkey + 1] + board[rowkey - 1][colkey + 1] + board[rowkey][colkey - 1];
    }
    if (rowkey == 0 && (colkey != 0 && colkey != size - 1))
    {
        alives = board[rowkey + 1][colkey + 1] + board[rowkey + 1][colkey] + board[rowkey + 1][colkey - 1] + board[rowkey][colkey - 1] + board[rowkey][colkey + 1];
    }
    if (colkey == size-1 && (rowkey != 0 && rowkey != size-1))
    {
        alives = board[rowkey + 1][colkey] + board[rowkey][colkey - 1] + board[rowkey + 1][colkey - 1] + board[rowkey - 1][colkey] + board[rowkey - 1][colkey - 1];
    }
    if (colkey == 0 && (rowkey != 0 && rowkey != size - 1))
    {
        alives = board[rowkey - 1][colkey + 1] + board[rowkey][colkey + 1] + board[rowkey + 1][colkey + 1] + board[rowkey - 1][colkey] + board[rowkey + 1][colkey];
    }

    //only if the element isnt edge & corner
    if (colkey != 0 && colkey != size-1 && rowkey != 0 && rowkey != size - 1)
    {
        alives = board[rowkey - 1][colkey + 1] + board[rowkey][colkey + 1] + board[rowkey + 1][colkey + 1] + board[rowkey - 1][colkey] + board[rowkey + 1][colkey] +
            board[rowkey - 1][colkey - 1] + board[rowkey][colkey - 1] + board[rowkey + 1][colkey - 1];
    }

    if (alive)
    {
        if (alives >= 4)
            return false;
        if (alives <= 1)
            return false;
        return true;
    }
    else
    {
        if (alives == 3)
            return true;
        return false;
    }

}

void swaparr(int **board, int **temp, int size) // copy the temp array to the board array
{
    for (int i = 0; i < size; i++)
    {
        for (int g = 0; g < size; g++)
        {
            board[i][g] = temp[i][g];
        }
    }
}

bool alldead(int **board, int size) //returns true if all of the cells are dead
{
    for (int i = 0; i < size; i++)
    {
        for (int g = 0; g < size; g++)
        {
            if (board[i][g] == 1)
                return false;
        }
    }
    return true;
}

void ongoing(int **board, int size) //runs as soon as the game starts
{
    int generation = 1;
    bool all_dead = false;
    int **temp = new int *[size];
    for (int i = 0; i < size; i++)
    {
        temp[i] = new int[size];
    }

    for (int i = 0; i < size; i++)
    {
        for (int g = 0; g < size; g++)
        {
            temp[i][g] = board[i][g];
        }
    }

    while (generation <= 50 && !all_dead)
    {
        for (int i = 0; i < size; i++)
        {
            for (int g = 0; g < size; g++)
            {
                if (rules(board,size,i,g,board[i][g] == 1))
                {
                    temp[i][g] = 1;
                }
                else
                {
                    temp[i][g] = 0;
                }
            }
        }
        swaparr(board, temp, size);
        print(board, size, generation);
        all_dead = alldead(board, size);
        generation++;
    }

    if (!all_dead)
    {
        cout << "HAPPY WORLD" << endl;
    }
    else
    {
        cout << "SAD WORLD" << endl;
    }
}