#B4237. Determine the Order of Three Coins

    ID: 11894 Type: Default 1000ms 256MiB

Determine the Order of Three Coins

Determine the Order of Three Coins

There are three coins labeled A, B, and C with distinct weights. You are given a weighing tool that, in each measurement, can both measure the weight of a coin and clearly compare the weights of any two coins. In this problem, you are given three pairwise comparisons between the coins (each in the format X < Y or X > Y, where X and Y are coin labels). For example, A < B indicates that coin A is lighter than coin B.

Your task is to determine the order of the coins from the lightest to the heaviest based on these three comparisons. If the given comparisons are contradictory (i.e. they cannot all be true at the same time), output Impossible.

The comparisons imply the following conditions in LaTeX format:

\(A \lt B, \quad B \lt C, \quad A \lt C\)

Note that the given comparisons can be in any order.

inputFormat

The input consists of three lines. Each line contains a comparison in one of the following forms:

  • X < Y
  • X > Y

Here, X and Y are coin labels (A, B, and C). There are no extra spaces in the input.

outputFormat

If the comparisons are consistent, output a single string representing the coins in order from the lightest to the heaviest without any spaces. Otherwise, output Impossible.

sample

A<B
B<C
A<C
ABC