eolymp
bolt
Try our new interface for solving problems
Problems

Dwarves

Dwarves

Time limit 1 second
Memory limit 128 MiB

Once upon a time, there arose a huge discussion among the dwarves in Dwarfland. The government wanted to introduce an identity card for all inhabitants.

Most dwarves accept to be small, but they do not like to be measured. Therefore, the government allowed them to substitute the field "height" in their personal identity card with a field "relative dwarf size". For producing the ID cards, the dwarves were being interviewed about their relative sizes. For some reason, the government suspects that at least one of the interviewed dwarves must have lied.

Can you help find out if the provided information proves the existence of at least one lying dwarf?

Input data

The first line contains the number n~(1 \le n \le 10^5) of statements. The next n lines describing the relations between the dwarves. Each relation is described by one line with "s_1 < s_2" or "s_1 > s_2", telling whether dwarf s_1 is smaller or taller than dwarf s_2. s_1 and s_2 are two different dwarf names.

A dwarf name consists of at most 20 letters from "A" to "Z" and "a" to "z". A dwarf name does not contain spaces. The number of dwarves does not exceed 10^4.

Output data

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

Examples

Input example #1
3
Dori > Balin
Balin > Kili
Dori < Kili
Output example #1
impossible
Input example #2
3
Dori > Balin
Balin > Kili
Dori > Kili
Output example #2
possible
Source 2016 German Collegiate Programming Contest (GCPC), Problem A