We all know Tic-Tac-Toe ends in a predictable draw when both players choose optimal moves. To make the game interesting, a group of mathematicians decided to fill in each square of the board with a smaller Tic-Tac-Toe board to produce what is now called Ultimate Tic-Tac-Toe.

tic-tac-toe

Challenge

Your goal is to play a valid game against a bot. You need to win the game by continually printing the best next move, based on the game rules below. You will lose the test case if you write to an invalid board and/or write to a square that already has an X or O.

For the purposes of these instructions:

  • board = one of the 9 tic-tac-toe game boards
  • square = one of the 81 individual squares

Game Rules

Like the original Tic-Tac-Toe, Player 1 is represented by 'X' (ascii value: 88) and Player 2 is represented by 'O' (ascii value: 79). To start the game, Player 1 places an X on any one of the 81 empty squares, and then players alternate turns.

However, after the initial move, players must play the board that mirrors the square from the previous player.

alt

For example: If Player 1 places an X in the upper-right square of a board, then Player 2 must play the upper-right board.

alt2

Continuing the example: If Player 2 places an O on the lower-middle square, then Player 1 must next play the lower-middle board.

Here are the necessary exceptions:

If the next move is to a board that is full or has already been won, then that player may choose an open square on any board, for that turn.

If a player marks 3 consecutive squares (horizontally, vertically or diagonally) on any given board, he wins that board. The first player to win 3 consecutive boards (horizontally, vertically or diagonally) wins the game.

Input Format

Line 1 indicates the player with the next move and is represented by character 'X' or 'O' for Player 1 or Player 2, respectively.

Line 2 indicates the board to be played (as determined by the previous move), and is represented by 2 spaced integers as follows:

uttt-indexed

If the player is allowed to play any of the 9 boards, the integers will be printed as "-1 -1".

Lines 3 through 11 reflect the contents of all 81 squares in the same order as displayed in the figure. Each square is referenced first by the board in which it is present (0 ≤ x,y ≤ 2) and its position inside it (0 ≤ x,y ≤ 2). i.e., a square (1,1) inside board (0,2) is referred as 0 2 1 1. Each line contains 9 characters, using "X", "O", or "-" to represent the state of a square. Character "-" (ascii value: 45) indicates an open (unmarked) square. The characters are listed in the same order as the boards, in other words: top row (left to right), then middle row (left to right), then bottom row (left to right).

Output

You will indicate a valid next move by a single line containing 4 spaced integers, as follows:

  • The first two integers indicate the board, using the input convention above.

  • The second two integers indicate the square within that board.

For example: An output of "1 1 1 1" would mark the center square of the entire Ultimate game board.

alt5

Sample Input

O
2 2
---------
---------
--X------
---------
---------
---------
---------
---------
---------

Sample Output

2 2 0 0

Explanation

In the previous move, 'X' makes the first move, placing an X on board number "0 0", square "2 2". Now, 'O' is forced to make a move only inside board "2 2". He chooses to mark the square "0 0". The resulting board is shown below.

X
0 0
---------
---------
--X------
---------
---------
---------
------O--
---------
---------

Now, X is forced to mark a cell only inside 0 0 More details of the game are given here

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