Dwarves

Interview

Time limit2sMemory limit512 MB

Summary

Given strict size comparisons between named dwarves, decide whether the statements are mutually consistent.

Level: Medium5 of 10
Topics: Graph, Topological sort, DFS, Hash map
Solved: No attempts yet

Problem

A loud argument broke out among the dwarves of Dwarfland. The government wanted to issue an identity card to every inhabitant.

Most dwarves accept that they are small, but they do not like being measured. So the government let them replace the height field on the card with a relative dwarf size field. To produce the cards, the government interviewed the dwarves about their relative sizes. The government suspects that at least one of the interviewed dwarves lied.

Decide whether the collected statements prove that at least one dwarf lied.

Input

The first line contains the number of statements $n$ ( $1 \le n \le 10^5$ ).

Each of the next $n$ lines describes the size relation between two dwarves. A line has the form s1 < s2 or s1 > s2, with one space between each name and the comparison sign. s1 < s2 means that dwarf s1 is smaller than dwarf s2, and s1 > s2 means that s1 is taller than s2. s1 and s2 are two different names.

A dwarf name consists of at most 20 letters from A to Z and a to z, and it contains no spaces. Upper case and lower case letters count as different letters. At most $10^4$ different dwarves appear.

Output

Print impossible if the statements are not consistent, and possible otherwise.

Examples2

Example 1

Input

3
Dori > Balin
Balin > Kili
Dori < Kili

Expected output

impossible

Example 2

Input

3
Dori > Balin
Balin > Kili
Dori > Kili

Expected output

possible