Coin

Interview

Time limit1sMemory limit128 MB

Summary

Determine the fake coin among 12 and whether it is heavier or lighter, given three balance weighing results, or report impossible/indefinite.

Level: Medium5 of 10
Topics: Brute force, Simulation, Implementation
Solved: No attempts yet

Problem

You have a two-pan balance scale and 12 coins numbered 1 through 12. Exactly one of them is a counterfeit, which is either heavier or lighter than a genuine coin. All genuine coins weigh the same.

Given the results of three weighings on the balance scale, write a program that determines which coin is the counterfeit and whether it is heavier or lighter than a genuine coin.

Input

The input consists of three lines. Each line describes one weighing in the following format:

A B C D x E F G H

A, B, C, D, E, F, G, H are the numbers of eight distinct coins, and x is one of <, >, =, with the following meaning:

< : the total weight of A, B, C, D is less than that of E, F, G, H
> : the total weight of A, B, C, D is greater than that of E, F, G, H
= : the total weight of A, B, C, D equals that of E, F, G, H

Output

If the counterfeit can be uniquely identified, print its number followed by + if it is heavier than a genuine coin, or - if it is lighter (for example, 2+).

If the three weighings contradict each other so that no coin can satisfy them, print impossible.

If the weighings are not contradictory but the counterfeit's number, or whether it is heavier or lighter, cannot be uniquely determined, print indefinite.

Examples4

Example 1

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

Expected output

2+

Example 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

Expected output

6-

Example 3

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

Expected output

impossible

Example 4

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

Expected output

indefinite