Гномики#7945

Гномики

1 секунда
128 мегабайт
Very easy

Давным-давно в Гномляндии разгорелась ожесточённая дискуссия. Правительство планировало ввести удостоверения личности для всех жителей.

Большинство гномов согласились с тем, что они маленькие, но категорически не хотели, чтобы их измеряли. В ответ на эти возражения правительство разрешило заменить в удостоверении личности поле "высота гнома" на поле "относительная высота гнома". Для оформления удостоверений у гномов брали интервью, в которых они высказывались о своём относительном росте. Однако по неизвестной причине правительство заподозрило, что как минимум один из гномов мог солгать.

Сможете ли вы определить, допускает ли предоставленная информация возможность того, что хотя бы один из гномов сказал неправду?

Input

Первая строка содержит количество утверждений n~(1 \le n \le 10^5).

Следующие строк описывают отношения между гномами. Каждое утверждение задано строкой вида "s_1 < s_2" или "s_1 > s_2", что означает: гном s_1 ниже или выше гнома s_2 соответственно. Здесь s_1 и s_2 — различные имена гномов.

Имя гнома состоит не более чем из букв латинского алфавита (заглавных "A" — "Z" и строчных "a" — "z"). Пробелы в именах не допускаются. Общее число различных гномов не превышает 10^4.

Output

Выведите "impossible", если утверждения противоречат друг другу, иначе выведите "possible".

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading