eolymp
bolt
Try our new interface for solving problems
Problems

Fruits

Fruits

Time limit 1 second
Memory limit 64 MiB

Petro sells very exotic fruits at the marked. Petro owns N such fruits, each of some positive weight. Petro doesn’t know the weights. Besides that, Petro owns a balance scale. He can place in left and right pans some fruits. The scale shows whether total weight of fruits in each pan is equal, or one pan outweighed other pan. After several such weightings, the Petro wants to predict the result of the next weighting before performing it.

Write a program that will help Petro to know what the scales will show, when performing the next weighing.

Input data

The first line of the input file contains two integers N and M (2N20, 0M50). Each of following M lines defines one of implemented weighting and has following format: firstly, numbers of fruits in left pan are given, then one of symbols "<", "=", ">", determining the weighting result, and lastly, numbers of fruits in right pan are given. In the last line in similar way forthcoming weighting is given, but its result is unknown and indicated by the symbol "?". Within one weighting, any fruit can be located either left pan, or right pan, or is not involved in weighing.

Output data

In the output file you should write all possible results of forthcoming weighing. In the case of several possible results you should keep the order "<", "=", ">". If input data is contradictory, you should write "Impossible".

Source International Collegiate Programming Contest, Ukraine, Quarter-Final,May 19, 2011