URI Online Judge | 2689

Game of the Miao

By Samuel Lucas Santos Gomes, IFSULDEMINAS BR Brazil

Timelimit: 1

A long time happens the secret game of miao. Most people say that the game is annoying and very difficult because no one managed to win the famous prize, but even so Webscript Junior (WBJ) decided to try. The game works as follows: a scarecrow shows a picture with suitcases, where there will only be one suitcase with the miao. Not even the scarecrow remembers in which briefcase he kept it and WBJ only has an opportunity to take this "MIAO!" home. WBJ picked up the contents of the suitcases that were already chosen by other players to see if there was any pattern.

After many research, WBJ concluded that the award-winning case was in an i-th position of a sequence, so he introduced the game to some friends to see how the game and the scarecrow behaved with each move and thereby gain more information for his research. The most relevant information is that, in addition to luck, the suitcases where the subtraction of the indexes is different from the difference that most repeats, serves as a standard to define which are the possible prize-winning suitcases.

For more accurate information, WBJ asked for his help. He wants a program that generates a list of suitcases where possibly would be the prize. He gives you 9 suitcases on a grid (3x3). Your program generates the list and he just had to hit the number of the suitcase, within the possible suitcases that he would have as a reference generated by your program.

For example:
Let's assume that the suitcases that WBJ chose were:
78 7 8
9 7 8
8 7 9

The difference is calculated as follows: the first element is calculated with the next, and the other two with its previous one ignoring the signal, thus the difference between the suitcases looks like this:

71 71 1
2 2 1
1 1 2

The first number is a result of 78 minus 7, the second is 7 minus 78, and the third is 8 less. The process repeats itself in the other lines. Then we conclude that the difference that repeats the most is the number 1, the next step is to verify if the difference between the numbers is not the one that repeats the most. The difference for the first number is calculated with the second and third, the difference of the second number is calculated with the first and last, so the difference of the last with the previous two. If the result of these differences is 1, the number is not displayed, for example: the second number less the third of the cases that WBJ gave you is 1, then the second number is not valid and the same is the case with the third. The end result looks like this:

Possible suitcases: 78;


WBJ left P lists with a 3x3 area, where he is sure that the prize bag will be in it. are three rows, each row with three integers less than 100.


With that he asked you to see the possible suitcases. Display a message "Possíveis maletas: " ("Possible suitcases") and then the selected suitcases, separated by "," and in the end a ";" and the break line.

Input Sample Output Sample

2 4 5
8 9 10
1 6 3
7 3 1
9 5 6
4 8 4
3 1 4
7 2 6
9 8 10
78 7 8
9 7 8
8 7 9

Possiveis maletas: 2, 1, 6, 3;
Possiveis maletas: 1, 6;
Possiveis maletas: 4, 7, 2, 6, 9;
Possiveis maletas: 78;