MYQ8 - The National Game

no tags 

Prasanna and Nithin had mastered Thuvax's national game, TicTacToe.
 
TicTacToe is a board game for two players, x and o, who take turns (alternatively) marking the spaces in a 3×3 grid with their signs 'x' and 'o' respectively. The x player goes first. The player who succeeds in placing three of his signs in a horizontal, vertical, or diagonal row wins the game and the game stops there.

While returning from a TicTacToe tournament, Prasanna and Nithin find a tictactoe like grid. They decide to continue playing from the state the board was in. Help Nithin find whether the next person to move will win/lose or whether the game will result in a tie (assuming both players play optimally), or if such a state is invalid.

Input

First line of the input contains a number T (1<=T<=10^6), followed by 4*T lines. The first line of each testcase is empty and the next 3 lines show the state of the game.

Output

Print win/lose/tie/invalid for each testcase on a separate line.

Example

Input:
3 
 
oox
.x.
..x
 
xox
xoo
oxx
 
o..
...
... Output: lose
tie
invalid

Explanation:
Case 1: Player x can win by placing x in either last cell of the middle row, or the first cell of the last row. So the next player, o, cant prevent him from winning from this state.
Case 2: It is completed game, as you can see no one has won. So, it has ended in a tie.
Case 3: Player x should have started the game. Hence such a state can never be reached.

hide comments
hodobox: 2016-07-09 04:07:50

Enjoyed :)

Ashish Lavania: 2014-01-30 15:30:47

I really cant figure out on which test cases why program fails. I would find it extremely helpful if you could provide some test cases or the number of test cases for which my program fails.
Edit : Found it.

Last edit: 2014-03-15 14:15:47
:D: 2012-03-26 20:22:30

Time limits are 1s-30s. There is at least one test for each 1s and 30s time limits, but there also may by some case with 5s limit.

lucyfer: 2012-03-12 16:08:52

The Time limit is 30s, but the judge gives TLE within 5 secs. Is something wrong?

Mitch Schwartz: 2012-03-08 01:07:20

Correct sample output is:

lose
tie
invalid


Added by:jack(chakradarraju)
Date:2012-02-14
Time limit:1s-7.485s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Bytecode 2012