import copy
import time
from enum import Enum
from functools import cache

text = """
O#...OO.#.#..##.#..#O.OO...O##OO.......#......O.O...O..........O..#O..O.#.#.O.....##O.#O.##.........
.OOO..OOO.O.#.....#.....#.#.....O..#..OO..#.....O#O##..##O#.OO....O##.OOO..O...#....O....#O..#...O..
OOO#...O#...##.OOOO##.O..#.....O...#.O..#...#.O..OO..##.#....O#O..#O#..##...O.OO..#.#........#O....O
O..#..#...#.O##.......OO#.#....O.##.O..O.O#.O..O#.....#...O..OO.O.#......O.###.........#.......##...
..O.O.O..#O..OOOO..#..#..O..O#O...O....#.O#........OOO#.O...O..O#.#.O........#......#O.O...OO.#.O..O
#..O.#..##....#...O..........#..O.#..##.O.....O.O.O..O..O.O.#.OO#.#..##.........#OO.O....##...#..##.
OO.O#.#.O...O..#..#OO..O.............O.........O.#.......#OO#.O.#OOO.##OOO..OO#.....O#.O.#O.O##OO...
.##...##O.....O..OO..O#.O.O.#....OOO.O.O#..#O#..#.O.OO...####O#......#.#O..O.O....#..O....#.#.#.O#.#
.....#O..O.O.#......#..........#.OO...O.#O.O.....O.#OO.#.#.O#......OO..O.O.....#...O.O..OO...#O.O#..
.O..#....#....OOO.O.#....O#O###....O.O#OO.............#...OOO.....#....O..O.......###............O..
..#O.#....###..O...#.....OO#O.....#....###..O#.......#OO....O.O...#....#.O.O.#..O.##O...O..O#...##..
O...O.#O.#O#....O.O#.......#............OO.....O.#O..O#O....O##O.OO..#..O..#O..O#O...##O.O.O.O#..O.#
O#.O......#.......O....#...O.....#O#.#..O...O.###O.OO#.........O.....O..O...#.#O.....OO#..O.#...#...
.#...O.......O.#.....O.......O.O..#....#..O#O.#..O.#..##.......##....O.#.....O........OO.O...O.....O
..O..#.#O.O#...#.......#O#OO.#O....O...#O..O.O.#O.OO#......OO#....#...O.#...#O.#...O.#.OO#..O.#OO.O#
.O.......O...#.......#....O..O......O.O.O#O.#O...O.#.....O..O...#OOO#..O...O##..OOO#....#..........O
OO#..##O.O.O.O.#....O#.O#O.##..O......#.#.O.O..O.O...OO#.......#..O.#O.O#.OO....#O#O.O.O.#.O#O#.....
#O#.O.......##OOO..OO...O#..#..O.O.##.O#....#OO....#...OO.#..#..O.......O#O.......#.O.O............O
..O.OO.O#..OOO....OO.O...#.#.......#.O.......O..OOO.##.##.#...#.O.....O..O.......O.O.#..............
OO#.....O.O.#.#...#.#.....O....#.#O..O......#..#..O...#.#....O#..OO....O.#.....O...O.#.O..#.........
....O.#.O...O#....#.O.#.......O#.#.O##......#...O.#..O#..#.#O.O...#.....O......#O#.#.#O....O..O.O#.#
.....###.O.O.O#.O.......O..OO#...#.#...#..O......#O....O...OOOO..O...#.#.#.#.O#..O.......OO.....#.#.
...O.O...#O..O..#..O#.O....#O..#..O...#.O.O.OO....#O#O#.OOO##..#O..OOO#.O.O..O....#...O#..O...#O....
.##.O...O..O.#.#OOO..O..O...O........#O.OO#..#OO......O....O.##...#..O#..O#...#..O.....O...##...O...
.O.#.O#OO.#...O....#.O.O..OO.O#O...O#..##...O.O...#...O#OOO.....O.........O......#.O.#...........OO.
O....O#O...#.OO#...#.........####..........O.#...#...O.O.O#.O..............##....O..O..O..#.#...##.#
..O.OO.#.OO#..O.#O....O......O.............#...##...#.O..#..O###.#......O..##.O.........O.#........O
O...#....#.......OO...O#O.......#.....#....OOO.#...OO.#O..O.#......#.##O....OO....O#.#.O..O...O..O..
...#...#....O.#..OOOO#..O#..#.##O.#.#.O..#.O....OOO....#..#..#....OOO...#.O.O...#.#.#O.O..O.#..O....
...O#.#...O.#.##O..O#..O.....OO#O...#.OO#..OO#O..OOO.O...#...O.#.O....O#...OOO..O...O....O....#.#..O
#........#..O.###.#...O#.O#O.........##..O.O.#O.O.###O....##.#.#.#..O.#O....#OO#O.....O.........O.##
O.O....#O.....O#...O#.....O##.OOO.#O.O..O....O..O...O....#...O.........O.#.O..#.#.O.O#O...#.#...O..O
.O..O##.O........O.OOO#O...#....O.OOOO#O..O..............O..O.O.O...#..........#......O..O.O.#......
.O....#OO#OO...#...O.##O.....#O.#.O.O...O.....OO#.O.......O#...#O..O#OOO.........##.....##...#...##O
.O#..OO....OOO..#.......OOO...##....OO..O.O..........##...#.#...#....O..#....O..........#.#.#O#.#.O.
##.......#O...O#.OO.#..O.O.O....#........#.O..........O.O.O..O.....#.OO#...#O#.O.OO..OO.O#..##....O.
....#..#..#O.##O.#....#.#.OO.......##..O#.#.##......O.O.OO..##...O.#....#..O.#....#.O....#...#O..O..
..O....#...OOO.#O..#..#...O..OOO..O#..#O......#..O...#.O..O.....#O...O#......#.......#O.O.........O#
#.OO....O....###....#OOO..O.#..#........#OO.....#O..........#O...#..O.OO..#......##O..O##.........#.
....#..O..........O.#.#..O.O.#....O..O....O..OO#....O.......OOO.....O.O.O..#....#.....O.O#.O#.##..O.
#.O...OO..#....O.O..O...#O..O#.#O.#...O.....##..O...O##...O........#O..#O..O#.O.#.......O#.#...#.OO#
.#.OOO#....#..O........OO....O#..###.O....O...O...O#.#O..#.OO........##..#..#...O..#.......OO...O#..
.....OOO.#.O....O....#....O..O.O.O.O....O...#OO....#.OO#OO...O.OOOO.O...O.O....#OO...#O.#O..O....#..
.#.#..........#O..OOO...#..O...#.............OO....#O...O#..O...#........O..#O#....OO.....OO##.O...#
..OOO.OOO##.##O#...O.O..O......O#O..O##...##....O.#........O....##...O#O..O#.O...O.O...O....O.......
..###.OO#..#.O.#....#..O..OO..O.###....O....#..O.O#.#......OO.....O#....O.OO....OO.O.O.O#........O..
#O###.#......O......O......#...O#.O.O...O#OO.O#....O..#..O#.OO...O..O..#..#.#...#..##OO...OO....O..O
..O...#..#O##O...#..#.#OO........O.#....O....................#...........#.....O..#...O#.#.O.O..#.#.
O...#.O...#O..#..O.O.#.....O.#....O.O...##......#..#..OO...#..O..OOOOO..O..O...#..O.OO...O.O#O.#....
........#...O.#.....O.O..O....#....#O......#..#........#O#.....#O##..OO.O...#......#OO.O#.O........O
.O..##..O#....#....OO.#O.#O#OO#O.#..OOO#.......OO....O.#.....O....#..#..##...#O.....#....O..O....O..
...##O..O.#.O..#.O.....#..O#.##OO#O#...O.##..#..#......O.##O.OO...O.#..#.O....#..O....O.O.........#.
...O..O.#..O.#O#......O.#OO.O.##.##..O###.#.O........O..O..O#...#.O...O.....##....O.OO..#..O..#..O#.
O....O......#..#O#.O....O...O.....#.O##O.O...#O.#O...O...#O...O.O#O...#O.#.#....#.#.#O....O.....OO..
.O.##..###....OO................OOO.....#.#.OO.O...O#.OO.#..O........#...O.O#.O..O.O..O.O...O....O..
...OOOO..O.#..O.#...O.##.O.O##.#..O.##..#.....##....O.O....O.O.##O.OO.#O.........#.##.O#...O.O..O...
...O.O..#O.#..OO.#.#O#OO..#OO.O......O.O.OO....#..OO.......#O..O.##....O.O..##O#.#....OO.....#.O...#
OO.....O....#O...O#.#..O...O#.#.O..#OO....O..#..OOO...O.........O....#.###O.OO....O....O............
..O..O.....#O.#O#OO..##.O.........#..##.##.O..O#O#..O.O..O..O...###.....OO.......#.##..#O##..O#O..O.
#O.#O...OOOO.O.###....#O..#O#O#.OO.....#O..#..#...O.#O.....#O....###.O....#..O...O..O....#......#...
O##...#.....#..O.#.O.#.......#..O#.....#.O.O.#...O..O....OO.....#.O###.#.....OO....#OO..OOO..#......
..O......#...#O..OO#O#OO....O.O.OOO.#O.OO.O......#....O##..O#.OO.##.#...O.##.....#...####.......##..
.......OO#.O.O.#.O.......#O#........#O..##OO#.#O..##..OO.##OO....#..O......#..#.O..#...#.O.....OO...
###.OO.O.O#..O.......#OO#.....#..O.O..O.O.......#..#O.##..#O..#..#...#O#......OO##O#OOO#...O#....O.#
#O#.O.........#..O.#..#..#..............O..O..#..O##....O.##..O..O#..O.....#OO..O.#.......O....OO...
#O#O....O#.#.O..O..#...#..#.#...#O.....O..##..#....O#.#.O.O.O...O.#...#.O....O#....#.....#.#..#...#O
O...O........O.#..OOOO..#...O#O....##.O..#.......#..O..#..#O.#...OO..#.O..##..#...O#O.##.....#..#.O.
O..#.##.......O..O......#..#.#.O...O#.O.......O#.O.O#O..#.O#.OOOOO.#OO.#.OO#....O....#...O####OO...#
#O..O....O..#O..O.OO.#.O.##...#O#.....O...#.....#......##......O#O#.........#..#.O...O.O..........#.
OOO.#.O.....O..OO.O#.#..#.#..#.............O#.......OOO#OO.O.#.#O...O.#..#...#..O...#.O#....O..O..##
OO#........#.O.O....O#O...#O.#..#.#...#......##.......#..#..#.#.#.......O...##...O#...O..O.......O..
O..#O......O....#O.O#..O........#......##..#...#O...OO....#.#...O........O.#O.......O.....O...#..O..
..#O#.......O..O..O..........#...OO.#..OOO....O....#OOO#..O.....#.O#....O...#O.......#..#.O...#..##.
...#O...O.OOO...O#.....#..#....##..#....#OO..O.OO#O.O#..#.O#O#O.....#OO#O...#.#O......O.....OO.....O
..#...O.O.....O...O##O..O.....O..O..#O.O..O....O.#O....#O....O..O.O......O.....#..#....O......#.....
O.#...O..#O.#...O.O.O..#..##...O.O..O#..O...O#....O........O#O.#O.#.O.......#.O.O..O.......OO.#.....
O#...O.O#..#O#...............OO##.#..#...#O....O....#O.OO.O..O#.O.....#O.....O..O...#..#..#...#..O.O
....OO.O#.#.......O..O.O.#..#.O#.O.....#............#....O..O..O..O.O..#..#..O.....#O.#O.#.O...O..#O
.....#...OOO...#.O....O#...#.....O..OO....##O.OOO..#.O...#...O.##.O#O...O.....#.#...O...O.##.#.....O
....##...O#O..O...##O.OOOO...#.#.....OOO..........O.O....O.#O.#..O#..O###...O....#.O#O......OOO..O.O
#..#...OO##OOO.O#....#O#.O.....O#.#...##.#O..OO.#.#.O.O..OO.O#.........##.....O..O#..O......O.....##
..O..OO.##O.##OO...O#.....#O.O..........#.#.......#..#..O....O...#......#..O.#.#...#.....#OO........
O.......#O.....O....OO#.#..O.....OO..#..OOO.O....O##O#O.O....OO#......#.#.O......#.OO.O.#OO....#....
....O...#.O....##.OO.....#O#.O...O....O#.O##.....O.#.O#........OO##...O..#.....O...O.....O...#..O#O.
#.OO.#.O##....#..O....O..#...OO...#....#.##...OO....#O.........O..#......O.OO..#..#..##......#O...#.
O...#.O.##..#.#OO#.O#.O###.O.#...O#..O###.......#....O.#.........O..O..#O#..O.O.O..OO..#.#...O#..O..
......#..##..#..##...O#......#..#.#O#.....#.#.O...#.#O..#O..O.O.#..O.O.O....O....#....OO.#O......#.O
..OO.##.#....O.O...O.#.....##O..#....#..OO#.#...##......#...OO...#.....#...#O..#O...#O......O#...O#.
OOO.O##O...O..O.O#.##O#..OO.#.O..O...O.#O..O..#.#...O.O.......#O##.#..#.#.O.......O..OOO#.O....O#..O
...O...OO.O...OO...O.....O#.#.#O.O.O.O..O..O...OO....O..###...##....#O....O...#.#.##....O....#O.O..#
......#OO.........##.O...#..#.O.#..OO....O..O..O.#OO......OO.O#.......O...#..O.O#..OO.##.##.OOOOO...
........O.....##..O.OO..O#.....O................O........OO#...##.....O#....#...#O.O..O...#.##..#O.O
#OO.O.O.O.O#.OOO....#O#.#....#...#O#O.#.....OOO.....#.O..##.O##..O...........#......#...O.#.#.O.....
.#O.........#.O.##O..#..O.O...OO..#..O.O#OO#..#O.O.O....#......O.....OO#..OO#.O.O..#.#.#OO.#..O.....
...OO.O#O.O#.O.......O#..#OO.O.OO..O#.O.OO.O........O.OO..#..O...#.#.#....#.#.....OO.#.O..OO.....#..
###.....O..#...OO.#OO........O....#O#OO...#.O...#.....#O...#.##..O..#O#..O##.O#.O.....#.O....#O...#.
#O#.##......O....#.O##..#.......#.#..O......O.OOO.#....O##.#.O..OO...O..#...#.###......OO....O#.#.O#
#OOOO#.#...OO..O..O..#..O..O...#OO.O.O.O#.#.##..#....####..O#....#O.OOO..O#O.#...O....#.O......O....
.##OO....#......O..OOO......#..O.....#..O...O..#.#.........OO.O..##.......#.#O#.OO......O#O..O......
........OOO.....OO........O.O.O.#O...#...O...O...O..O..#.....#O..#.#..OO....O...#..##..#O......O.#O#
"""

game = tuple(tuple(line) for line in text.strip().split("\n"))


def display(board):
    for i in range(0, len(board)):
        for j in range(0, len(board[i])):
            print(board[i][j], end="")
        print()

    print("\n\n")


@cache
def rotate_north(game_board):
    board = [list(line) for line in game_board]

    print("computing new board")

    for i in range(0, len(board)):
        for j in range(0, len(board[0])):
            if board[i][j] != "O":
                continue

            destination = i - 1
            while destination > -1 and board[destination][j] == ".":
                destination -= 1

            board[i][j], board[destination + 1][j] = board[destination + 1][j], board[i][j]

    return tuple(tuple(line) for line in board)


@cache
def rotate_south(game_board):
    board = [list(line) for line in game_board]

    print("computing new board")

    for i in range(len(board) - 1, -1, -1):
        for j in range(0, len(board[0])):
            if board[i][j] != "O":
                continue

            destination = i + 1
            while destination < len(board) and board[destination][j] == ".":
                destination += 1

            board[i][j], board[destination - 1][j] = board[destination - 1][j], board[i][j]

    return tuple(tuple(line) for line in board)


@cache
def rotate_east(game_board):
    board = [list(line) for line in game_board]

    print("computing new board")

    for i in range(0, len(board)):
        for j in range(len(board[0]) - 1, -1, -1):
            if board[i][j] != "O":
                continue

            destination = j + 1
            while destination < len(board) and board[i][destination] == ".":
                destination += 1

            board[i][j], board[i][destination - 1] = board[i][destination - 1], board[i][j]

    return tuple(tuple(line) for line in board)


@cache
def rotate_west(game_board):
    board = [list(line) for line in game_board]

    print("computing new board")

    for i in range(0, len(board)):
        for j in range(0, len(board[i])):
            if board[i][j] != "O":
                continue

            destination = j - 1
            while destination > -1 and board[i][destination] == ".":
                destination -= 1

            board[i][j], board[i][destination + 1] = board[i][destination + 1], board[i][j]

    return tuple(tuple(line) for line in board)


@cache
def cycle(board):
    new_game = rotate_north(board)
    new_game = rotate_west(new_game)
    new_game = rotate_south(new_game)
    new_game = rotate_east(new_game)
    return new_game


@cache
def points(board):
    tot = 0
    points = len(board)
    for i in range(len(board) - 1, -1, -1):
        for j in range(0, len(board[i])):
            if board[i][j] == "O":
                tot += points - i
    return tot


combinations_and_transformed = {}
first_in_repetition = None

cycle_start = None
cycle_width = None

for i in range(0, 1000000000):
    new_game = cycle(game)
    if game in combinations_and_transformed and combinations_and_transformed[game][1] == new_game:
        cycle_start = combinations_and_transformed[game][0]
        cycle_width = i - 1 - combinations_and_transformed[game][0]
        break
    else:
        combinations_and_transformed[game] = (i - 1, new_game)  # we are storing the index of the previous result
    game = new_game

print(f"cycle starts at {cycle_start}")
print(f"cycle width {cycle_width}")
print(f"missing {(1000000000 - cycle_start) % cycle_width}")

for i in range(0, (1000000000 - (cycle_start + cycle_width)) % cycle_width - 1):
    print(points(game))
    game = cycle(game)

print(f"points of the final position: {points(game)}")