More cases has been added on Mar 21, 2025, so that any tiny imperfections will be discovered.

Background

Gomoku (Five in a row) is a board game where two players compete against each other, with each side taking turns placing a piece in each round. After finishing Homework 2 in 2025 Spring's CS100, two students Frisk and Chara decided to apply the same rules to a well-known similar game: Gravity-Flavored Yonmoku (Four in a row when considering gravity) (It's the name they call the game). In Gravity-Flavored Yonmoku, Blue(O) player (Frisk) first move.

In this problem, Given a Gravity-Flavored Yonmoku game board, you should determine whether the gameboard is valid. If so, you should determine whether the next player could win in one move ， you only need to check one step forward. If not, you should determine who violated the rules such that the gameboard is invalid.

Description

On a $7×7$ Gravity-Flavored Yonmoku board, the rules are as follows:

Gravity Rules

Every piece must be placed in one of the seven columns if it's not filled with already-placed pieces. Every time a piece is placed in a column, it will begin from the top of the board. Then it will drop to the space below if there isn't a piece on the place below or it touches the bottom of the gameboard, because of the gravity.

Winning Rules

1. Four consecutive pieces must be formed in one of the following directions:

   • Horizontal : Four consecutive pieces in the same row (e.g., XXXX).
   • Vertical : Four consecutive pieces in the same column (e.g., O vertically aligned in four consecutive cells).
   • Diagonal : Four consecutive pieces in a diagonal line, either from top-left to bottom-right (\) or top-right to bottom-left (/).

2. Example Board Scenarios

   • Red wins (horizontal four in a row): ..XXXX.
   • Blue wins (diagonal four in a row):

O...
XO..
XXO.
OOXO

Format

Input

$7$ Lines, each line with $7$ characters consists of only X, O, ., denoting the Gravity-Flavored Yonmoku board.

Output

If the gameboard is invalid because either side violated the rules to place more than one piece in a row, output Invalid Gameboard! Bad Frisk!/Invalid Gameboard! Bad Chara!

If the gameboard is invalid because it violated the gravity rule while the players placed the pieces legally, output Invalid Gameboard! Bad Gravity!

If the gameboard is valid and there is already a player won the game, output AlreadyWin!

If the gameboard is valid and the next move of the game could win the game, you should output two lines. The first line should output Win!, and the second line should output one integer x, denoting the column of the position of the next move which could win the game. If there are multiple positions could win the game, output the smallest of them.

If the gameboard is valid and the next move of the game cannot win the game, you should output one line CannotWin!

Samples

.......
.......
.......
.......
.......
.XXX...
.OOO...

Win!
1

.......
.......
.......
.......
...XX..
..OXOOX
.OXOOOX

CannotWin!

.......
.......
.......
.......
..XXXXO
..OXOOX
.OXOOOX

AlreadyWin!

.......
.......
.......
.....OX
...XXXX
..OXOOX
.OXOOOX

Invalid Gameboard! Bad Chara!

XX...OO
.X...O.
XX...OO
.X...O.
XX...OO
.X...O.
..X.O..

Invalid Gameboard! Bad Gravity!

Limitation

1s, 1024KiB for each test case.