In Connect Four, there is a grid which sits vertically and has 7 columns (numbered 1 to 7 from left to right) and 6 rows. Connect Four is a two player game: one player is red, and the other is blue. The players take turn placing a piece of their colour into one of the columns, where it falls down until it hits the bottom of the board, or another piece. You cannot place a piece in a column if it already has 6 pieces in it. A player wins when they have 4 pieces of their colour in consecutive positions ("4 in a row") either vertically, horizontally or diagonally.

You and your friend are playing a game of Connect Four, where you are red and your friend is blue. Your friend has gone to the bathroom and you want to take this opportunity to make several moves (only with your red pieces) so that you have 4 in a row. To make it look less suspicious, you wish to perform the smallest possible number of moves which results in you winning.

Input Format

There are 6 lines of input, each with 7 characters, describing the initial state of the Connect Four board. Each character is either R (meaning your piece), B (meaning your opponent's piece) or . (meaning an empty cell).

Constraints

For all test cases:

  • You are guaranteed that neither player has won the game yet.
  • You are guaranteed all pieces are either at the bottom of their column, or on top of another piece (i.e. there are no floating pieces).
  • You and your friend both regularly cheat, so there is no guarantee that you have both played the same number of pieces.

Additionally:

  • For test cases worth 50%, it is possible to win in one move.

Output Format

Output a single line, a sequence of moves of minimum length which results in you winning. If there are multiple such sequences, you can output any of them.

If there is no way you can win, instead output the single integer -1.

Sample Input 0

.......
.......
...R...
...B...
..BRR..
.BRBRBR

Sample Output 0

5 5 

Explanation 0

There are multiple ways to win in two moves. These include:

  • Placing in column 5 then column 6 (making 4 in a row diagonally).
  • Placing in column 5 twice (making 4 in a row vertically).
  • Placing in column 6 then column 7 (making 4 in a row horizontally).

Sample Input 1

.......
.......
.......
.......
.......
.......

Sample Output 1

1 1 1 1 

Explanation 1

The board is empty and you can win by either placing 4 pieces in one column, or placing 1 piece in 4 adjacent columns.

Sample Input 2

...B...
RRBBRRB
BBRRBBR
RRBBRRB
BBRRBBR
RRBBRRB

Sample Output 2

-1

Explanation 2

There is no way to win, regardless of how many pieces you place.

Line: 1 Col: 1
  1. Challenge Walkthrough
    Let's walk through this sample challenge and explore the features of the code editor.1 of 6
  2. Review the problem statement
    Each challenge has a problem statement that includes sample inputs and outputs. Some challenges include additional information to help you out.2 of 6
  3. Choose a language
    Select the language you wish to use to solve this challenge.3 of 6
  4. Enter your code
    Code your solution in our custom editor or code in your own environment and upload your solution as a file.4 of 6
  5. Test your code
    You can compile your code and test it for errors and accuracy before submitting.5 of 6
  6. Submit to see results
    When you're ready, submit your solution! Remember, you can go back and refine your code anytime.6 of 6
  1. Check your score