eolymp
bolt
Try our new interface for solving problems
Məsələlər

Фрукты

Фрукты

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Ашот торгует на рынке очень редкими экзотическими фруктами. У него есть N таких фруктов, каждый из которых имеет свой положительный вес, неизвестный Ашоту. Кроме того, у него есть чашечные весы. Ашот может положить на одну и на другую чашу весов некоторое количество своих фруктов. Весы при этом покажут равны ли суммарные веса фруктов на обоих чашах, либо одна из них перевешивает. Произведя несколько таких взвешиваний, торговец решил предугадать результат еще одного, не выполняя его.

Напишите программу, которая поможет торговцу узнать результат, который может дать такое взвешивание.

Giriş verilənləri

В первой строке входного файла задаются два целых числа N и M (2N20, 0M50). Каждая из последующих M строк определяет одно из произведенных взвешиваний и имеет следующий формат: в начале перечисляются номера фруктов, находящихся на левой чаше, затем один из символов "<", "=", ">", определяющий результат взвешивания, и в конце – номера фруктов, находящихся на правой чаше. В последней строке в аналогичном формате задается взвешивание, результат которого требуется узнать. На месте результата в этой строке будет символ "?". В рамках одного взвешивания любой фрукт может находиться либо на одной чаше, либо на другой, либо не участвовать во взвешивании совсем.

Çıxış verilənləri

В выходной файл выведите в одну строку без пробелов все возможные результаты невыполненного взвешивания. В случае нескольких возможных результатов выводить следует в таком порядке – "<", "=", ">". В случае, если исходные данные противоречивы, выведите "Impossible".

Mənbə International Collegiate Programming Contest, Ukraine, Quarter-Final,May 19, 2011