#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <vector>
#include <stack>

using namespace std;

// Define the 3x3 glider patterns (4 different directions, 4 phases each)
const int gliders[4][4][3][3] = {
    // Right
    {{{0, 1, 0}, {0, 0, 1}, {1, 1, 1}}, // Glider 0
    {{1, 0, 1}, {0, 1, 1}, {0, 1, 0}}, // Glider 1
    {{0, 0, 1}, {1, 0, 1}, {0, 1, 1}}, // Glider 2
    {{1, 0, 0}, {0, 1, 1}, {1, 1, 0}}}, // Glider 3

    // Down right
    {{{0, 1, 0}, {1, 0, 0}, {1, 1, 1}}, // Glider 4
    {{1, 0, 1}, {1, 1, 0}, {0, 1, 0}}, // Glider 5
    {{1, 0, 0}, {1, 0, 1}, {1, 1, 0}}, // Glider 6
    {{0, 0, 1}, {1, 1, 0}, {0, 1, 1}}}, // Glider 7

    // Down left
    {{{1, 1, 1}, {1, 0, 0}, {0, 1, 0}}, // Glider 8
    {{0, 1, 0}, {1, 1, 0}, {1, 0, 1}}, // Glider 9
    {{1, 1, 0}, {1, 0, 1}, {1, 0, 0}}, // Glider 10
    {{0, 1, 1}, {1, 1, 0}, {0, 0, 1}}}, // Glider 11

    // Up left
    {{{1, 1, 1}, {0, 0, 1}, {0, 1, 0}}, // Glider 12
    {{0, 1, 0}, {0, 1, 1}, {1, 0, 1}}, // Glider 13
    {{0, 1, 1}, {1, 0, 1}, {0, 0, 1}}, // Glider 14
    {{1, 1, 0}, {0, 1, 1}, {1, 0, 0}}}  // Glider 15
};

const int BOARD_SIZE = 20;
int board[BOARD_SIZE][BOARD_SIZE] = {0};
int board2[BOARD_SIZE][BOARD_SIZE] = {0};

// Stores placed glider positions
vector<pair<int, int> > placedGliders;

// Function to check if a glider can be placed at (r, c)
bool canPlace(int r, int c) {
    // Ensure 3x3 region is within board and unoccupied
    if (r + 2 >= BOARD_SIZE || c + 2 >= BOARD_SIZE) return false;

    // Ensure it does not touch the border
    if (r == 0 || c == 0 || r + 2 == BOARD_SIZE - 1 || c + 2 == BOARD_SIZE - 1) return false;

    // Ensure the placement follows the Manhattan distance constraint
    for (auto &p : placedGliders) {
        if (abs(p.first - r) + abs(p.second - c) < 6) return false;
    }

    return true;
}

// Function to place a glider at the specified position
void placeGlider(int r, int c, const int glider[3][3]) {
    for (int i = 0; i < 3; ++i)
        for (int j = 0; j < 3; ++j)
            board[r + i][c + j] = glider[i][j];
    pair<int, int> x1;
    x1.first=r;
    x1.second=c;
    placedGliders.push_back(x1);
}

// Function to perform a DFS to count connected live cells
int dfs(int x, int y, vector<vector<bool> > &visited) {
    // Directions for 8-connected neighbors
    int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
    int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
    
    stack<pair<int, int> > s;
    pair<int, int> x1;
    x1.first=x;
    x1.second=y;
    s.push(x1);
    visited[x][y] = true;

    int count = 0;

    while (!s.empty()) {
        auto [currX, currY] = s.top();
        s.pop();
        count++;

        for (int i = 0; i < 8; i++) {
            int newX = currX + dx[i];
            int newY = currY + dy[i];

            if (newX >= 0 && newX < BOARD_SIZE && newY >= 0 && newY < BOARD_SIZE &&
                !visited[newX][newY] && board[newX][newY] == 1) {
                visited[newX][newY] = true;
                pair<int, int> x1;
            x1.first=newX;
            x1.second=newY;
            s.push(x1);
            }
        }
    }
    return count;
}

// Function to check if a configuration is stable
bool isStable(int previousBoard[BOARD_SIZE][BOARD_SIZE]) {
    for (int i = 0; i < BOARD_SIZE; ++i) {
        for (int j = 0; j < BOARD_SIZE; ++j) {
            if (board[i][j] != previousBoard[i][j]) {
                return false;
            }
        }
    }
    return true;
}

// Function to count connected cells and check if the count exceeds 10
bool checkContinuousPattern() {
    vector<vector<bool> > visited(BOARD_SIZE, vector<bool>(BOARD_SIZE, false));
    int totalCount = 0;

    for (int i = 0; i < BOARD_SIZE; ++i) {
        for (int j = 0; j < BOARD_SIZE; ++j) {
            if (board[i][j] == 1 && !visited[i][j]) {
                // Perform DFS to count connected cells
                int count = dfs(i, j, visited);
                if (count > totalCount) {
                    totalCount = count; // Store the maximum count of connected cells
                }
            }
        }
    }

    return totalCount > 10; // Only return true if connected cells exceed 10
}

// Function to update the board using the rules of Conway's Game of Life
void updateBoard() {
    int newBoard[BOARD_SIZE][BOARD_SIZE] = {0}; // Initialize new board to zero
    for (int i = 0; i < BOARD_SIZE; ++i) {
        for (int j = 0; j < BOARD_SIZE; ++j) {
            int aliveNeighbors = 0;

            // Count alive neighbors
            for (int dX = -1; dX <= 1; ++dX) {
                for (int dY = -1; dY <= 1; ++dY) {
                    if (dX == 0 && dY == 0) continue; // Skip the cell itself
                    int newRow = i + dX;
                    int newCol = j + dY;
                    if (newRow >= 0 && newRow < BOARD_SIZE && newCol >= 0 && newCol < BOARD_SIZE) {
                        aliveNeighbors += board[newRow][newCol];
                    }
                }
            }

            // Apply Game of Life rules
            if (board[i][j] == 1) {
                newBoard[i][j] = (aliveNeighbors == 2 || aliveNeighbors == 3) ? 1 : 0;
            } else {
                newBoard[i][j] = (aliveNeighbors == 3) ? 1 : 0;
            }
        }
    }

    // Copy newBoard back to board
    for (int i = 0; i < BOARD_SIZE; ++i) {
        for (int j = 0; j < BOARD_SIZE; ++j) {
            board[i][j] = newBoard[i][j];
        }
    }
}

// Function to print the board with required spacing
void printBoard() {
    for (int i = 0; i < BOARD_SIZE; ++i) {
        for (int j = 0; j < BOARD_SIZE; ++j) {
            cout << (board2[i][j] ? 'O' : '.');
        }
        cout << endl;
    }
    for(int i = 0; i < BOARD_SIZE; ++i)
        cout << '.';
    cout << endl;
    for(int i = 0; i < BOARD_SIZE; ++i)
        cout << '.';
    cout << endl;
    for(int i = 0; i < BOARD_SIZE; ++i)
        cout << '.';
    cout << endl;
}

void copyBoard() {
    for (int i = 0; i < BOARD_SIZE; ++i) {
        for (int j = 0; j < BOARD_SIZE; ++j) {
            board2[i][j] = board[i][j];
        }
    }
}

// Main loop where gliders are placed and the simulation runs
int main() {
    srand(static_cast<unsigned>(time(0)));

    while (true) {
        // Reset the board and placed gliders
        for (int i = 0; i < BOARD_SIZE; ++i) {
            for (int j = 0; j < BOARD_SIZE; ++j) {
                board[i][j] = 0;
            }
        }
        placedGliders.clear();

        // Attempt to place one glider from each direction
        for (int dir = 0; dir < 4; ++dir) {
            int gliderIndex = rand() % 4; // Randomly select one of the four phases of the current direction
            int startRow, startCol;

            // Try to place the glider
            while (true) {
                startRow = rand() % (BOARD_SIZE - 3); // Random row
                startCol = rand() % (BOARD_SIZE - 3); // Random column

                // Try placing the glider if possible
                if (canPlace(startRow, startCol)) {
                    placeGlider(startRow, startCol, gliders[dir][gliderIndex]);
                    break;
                }
            }
        }

        copyBoard();

        // Simulate until stable or 200 generations
        int generationCount = 0;
        while (true) {
            int previousBoard[BOARD_SIZE][BOARD_SIZE] = {0}; // Store the current state
            for (int i = 0; i < BOARD_SIZE; ++i) {
                for (int j = 0; j < BOARD_SIZE; ++j) {
                    previousBoard[i][j] = board[i][j]; // Store current state
                }
            }

            updateBoard();
            // Check for border cells during the evolution
            bool onBorder = false;
            for (int i = 0; i < BOARD_SIZE; ++i) {
                if (board[0][i] == 1 || board[BOARD_SIZE - 1][i] == 1 || board[i][0] == 1 || board[i][BOARD_SIZE - 1] == 1) {
                    onBorder = true;
                    break;
                }
            }
            if (onBorder) {
                break; // Skip to next configuration
            }

            if (isStable(previousBoard)) {
                if (checkContinuousPattern()) {
                    printBoard(); // Print the stable board
                }
                break; // Stop after printing the first stable configuration
            }

            generationCount++;
            if (generationCount >= 200) {
                break;
            }
        }
    }

    return 0;
}