In-place Sorting

시간 제한2초메모리 제한512 MB

요약

각 수의 6과 9를 뒤집어 수열을 비감소 순서로 만들고, 가능한 뒤집기 조합이 없으면 impossible을 출력한다.

난이도: 보통10점 중 5점
유형: 그리디, 정렬, 문자열
정답자: 아직 제출이 없습니다

문제

Woe is you -- for your algorithms class you have to write a sorting algorithm, but you missed the relevant lecture! The subject was in-place sorting algorithms, which you deduce must be algorithms that leave each input number in its place and yet somehow also sort the sequence.

Of course you cannot change any of the numbers either, then the result would just be a different sequence. But then it hits you: if you flip a 6 upside-down, it becomes a 9, and vice versa! Certainly no one can complain about this since you changed none of the digits! The deadline to hand in the exercise is in five hours. Try to implement this sorting algorithm before then!

입력

The input consists of:

A line with an integer $n$ ( $2 \leq n \leq 10\\,000$ ), the number of integers in the input sequence.
$n$ lines, the $i$ th of which contains a positive integer $x\_i$ ( $1\leq x\_i \leq 10^{18}$ ), the $i$ th number of the sequence.

출력

If the sequence cannot be sorted in non-decreasing order by flipping some of the digits $6$ or $9$ in the input1, output "impossible". Otherwise, output "possible" followed by the sorted sequence -- each number on its own line.

If there are multiple valid solutions, you may output any one of them.

1Flipping any of the digits of $n$ is not allowed.

예제4

예제 1
입력
```
4
9
7
7
9
```
예상 출력
```
possible
6
7
7
9
```
예제 2
입력
```
4
97
96
66
160
```
예상 출력
```
possible
67
69
99
190
```
예제 3
입력
```
3
80
97
79
```
예상 출력
```
impossible
```
예제 4
입력
```
2
197
166
```
예상 출력
```
possible
167
169
```