Мало кто знает, но у Данилы Багрова и Татарина есть ещё один брат, неизвестный широкой публике. Проживает он тихо, мирно в Копейске, вдали от столичной суеты и назойливых папарацци.
Однажды Данила Багров и Татарин решили навестить своего брата. Приехав к нему домой в Копейск, Данила обнаружил в шкафу обширную коллекцию дисков различных рок-групп. На полках лежали диски «Nautilus Pompilius», «Би-2», «АукцЫона», «Смысловых галлюцинаций», «Агаты Кристи» и многих других. Однако Даниле не понравилось, как эти диски были разложены на полках.
Шкаф с полками можно представить в виде прямоугольника n×m, где в каждой клетке лежит один диск. Каждый диск описывается одним числом — некоторым номером группы, которая записала этот диск. Будем считать, что если два диска имеют одинаковое число, то их записала одна и та же группа, а если разные — то их записали разные группы.
Данила хочет добиться того, чтобы в каждом столбце все диски были записаны разными группами. Для этого он может сколько угодно раз переставлять диски произвольным образом на любой полке (то есть внутри любой строки), однако, запрещено менять местами диски с разных полок.
Помогите Даниле и скажите, можно ли такими действиями добиться того, чтобы в каждом столбце все диски были записаны разными группами.
Входных данные
В первой строке через пробел заданы два целых числа n и m — размеры шкафа (1 <= n,m <= 100).
В следующих n строках через пробел записаны m целых чисел a
i,j — номер группы, которая записала диск, лежащий на i-й полке в j-м столбце (1<= a
i,j <=10
9).
Выходные данные
В первой строке выведите Impossible, если Данила не может расставить всё так, чтобы в каждом столбце диски были записаны разными группами, и Possible, если такая расстановка возможна.
В случае, если Данила может добиться желаемого, выведите финальную расстановку дисков в шкафу. Если таких расстановок несколько, выведите любую из них.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
3 4
1 2 2 3
3 2 1 4
2 4 1 3 |
Possible
3 2 1 2
1 3 2 4
2 1 4 3 |
| 2 |
3 3
1 1 1
1 1 1
1 1 1 |
Impossible |