Triviador is a war between two Kings. A king can attack an enemy region at each step. When a king attacks a region, he conquers all the enemy regions connected to it(not just the immediate ones). All the 8 regions around any region are connected to it. The kings get alternate chances to attack. King1 gets the chance to attack first. Assume both kings are intelligent and find who will conquer the whole territory at the end of the war. It can be proved that one of the Kings can win for sure if he is intelligent!


Input Specification:

The first line is an integer t, denotes the number of test cases. In each test case the first line consists of two integers denoting the number of rows and columns in the territory (each cell is a region). Then the description of each cell follows. Every region contains a character ‘X’ if it is owned by king1 or ‘O’ otherwise.

Output Specification:
For each test case output the result in a single line ‘X’ if king1 wins or ‘O’ if king2 wins.


Input Constraints:




Sample input:


3 3





3 5





4 4





Sample Output:





Explanation of testcase 1 and 2:

Case 1: King1 has two possibilities to attack. But after attacking any of them, he will lose surely when king2 attacks back.

Case 2: King1 can attack any of the four enemy positions. He conquers all the connected enemy positions. So this is a one step victory.

Try the 1D version of this problem :
Try the 3D version of this problem :

hide comments
nadstratosfer: 2018-02-21 15:41:57

Take care of random blanklines in input when solving with Python. Great problem and not easy at all, my solution needed a not-so-basic algo as well as a certain assumption that I can't prove. Generating many testcases and analyzing them helped.

vengatesh15: 2017-03-11 14:40:41

simple one AC in 1 go:-)

cegprakash: 2016-10-21 14:53:57

zeronfinity : King 2 has already won the game in ur case.

zeronfinity: 2016-10-20 09:50:04


When my code outputted X for this input, it got WA. When it outputted O, it became AC. Shouldn't the correct output be X?

Aditya Jain: 2014-08-17 11:53:50

i hav got ac......but how to improve my runtime? Is there anyway someone can contact others on spoj?
PS: I'm new on spoj

Last edit: 2014-08-17 11:54:27
Mitch Schwartz: 2014-04-24 17:00:57

@Valentin Ambaroski: My AC code gives "O" for that case, but I'm not sure if such a case appears in the actual test data.

Valentin Ambaroski: 2014-04-23 15:19:41

I have this case as the begging
Who is the winner for this case?

Last edit: 2014-04-23 15:19:57
Mitch Schwartz: 2014-04-10 16:58:37

@Mladen Krcmarevic: If you think the problem statement is unclear, please specify. If you want debugging help, you may try the forum. (Although if you're doing this as part of BubbleCup, that might be against the rules, I don't know.) For here, no, I will not give more test cases, because that would be a spoiler. A good definition of spoiler from urban dictionary: "When someone reveals a previously unknown aspect of something which you likely would have rather learned on your own." Yes, there really are people who would rather work on problems without getting lots of hints and extra test cases when reading comments. Please be respectful of those users. My previous comment giving a (trivial) test case was just to clarify the meaning of "connected" -- as I recall, the problem statement was different at that time, and the meaning of "connected" less clear. (Similar to QWERTY04.)

krcma96: 2014-04-10 15:00:20

Ok, thanks Mitch Schwartz, but could you post some more test cases, I'd really appreciate it

Mitch Schwartz: 2014-04-09 22:03:41

@Mladen Krcmarevic: The judge does not halt on first failure, so it's possible to see e.g. "Running...(10)" even if your code failed for the first data set. And please don't ask for spoilers in the comments. Thanks.

Added by:cegprakash
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64