Coins
You have a balance scale and 12 coins (numbered 1, 2, ..., 12), one of which is counterfeit. The counterfeit coin is either lighter or heavier than the other, "normal" coins. Three weightings are performed on the balance scale. Write a program coins, which attempts to identify the counterfeit coin and determines if it is heavier or lighter.
Input
The data for each weighing is given on a line of the standard input in the form: A B C D x E F G H where A, B, C, D, E, F, G and H are the numbers of eight different coins, and x is one of the characters <, > or =, with the following meaning:
< : The total weight of coins A, B, C and D is less than the total weight of coins E, F, G и H.
> : The total weight of coins A, B, C and D is greater than the total weight of coins E, F, G и H.
= : The total weight of coins A, B, C and D is equal to the total weight of coins E, F, G и H.
Output
The program writes to the standard output the number of the counterfeit coin and the character '+', when it is heavier than the others, or the character '–', when it is lighter.
If the data of the three weighings is contradictory the program has to output "impossible".
If the data is not contradictory but is insufficient for determining the number of the counterfeit coin, or if it is heavier or lighter the program has to output "indefinite".
Constraints
Time limit: 1 second
Memory limit: 64 megabytes
Examples
input 1 2 3 10 > 4 5 6 11 1 2 3 11 > 7 8 9 10 1 4 7 10 < 2 5 8 12 | output 2+ |
input 1 4 6 10 < 5 7 9 12 2 5 4 11 > 6 8 7 10 3 6 5 12 < 4 9 8 11 | output 6- |
input 1 2 3 4 < 5 6 7 8 5 6 7 8 < 9 10 11 12 9 10 11 12 < 1 2 3 4 | output impossible |
input 4 8 10 11 = 1 2 5 7 2 4 7 12 = 8 9 10 11 3 7 10 11 > 6 8 9 12 | output indefinite |