Всем известно, что в Берляндии есть n городов, образующих Серебряное кольцо — пары городов с номерами i и i + 1 (1 ≤ i < n), а так же n и 1 соединены дорогами. Правительство Берляндии решило построить m новых дорог. Уже подготовлен план постройки — список пар городов, которые нужно соединить дорогами. Каждая дорога будет представлять собой непрерывную линию, находящуюся внутри, либо снаружи кольца. Дороги не будут иметь общих точек с кольцом (кроме двух ее концов).
Теперь разработчикам плана интересно, можно ли построить дороги так, чтобы они не пересекались (заметим, что дороги могут пересекаться своими концами). Если это возможно сделать, то какие дороги должны находиться внутри кольца, а какие снаружи?
Выходные данные
Если невозможно построить дороги так, чтобы они пересекались только в концах, выведите Impossible. Иначе выведите m символов. i-ый символ должен быть i, если дорогу нужно проводить внутри кольца, или o — если дорогу нужно проводить снаружи кольца. Если решений несколько, выведите любое.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 2
1 3
2 4
|
io
|
|
2
|
6 3
1 3
3 5
5 1
|
ooo
|