Few people know, but Danila Bagrov and Tatarin have another brother, unknown to the general public. He lives quietly, peacefully in Kopeysk, far from the bustle of the capital and annoying paparazzi.
One day Danila Bagrov and Tatarin decided to visit their brother. Arriving at his home in Kopeysk, Danila found in the closet an extensive collection of discs from various rock bands. On the shelves were CDs of Nautilus Pompilius, Bi-2, Auctionon, Semantic Hallucinations, Agatha Christie, and many others. However, Danila did not like the way these discs were laid out on the shelves.
A cabinet with shelves can be represented as a rectangle nxm, where each cell contains one disk. Each disc is described by a single number — some number of the group that recorded this disc. We will assume that if two discs have the same number, then they were recorded by the same group, and if different — they were recorded by different bands.
Danila wants to ensure that all discs in each column are recorded in different groups. To do this, he can rearrange disks as many times as he likes arbitrarily on any shelf (that is, inside any row), however, it is forbidden to swap disks from different shelves.
Help Danila and tell me if it is possible to ensure that all discs in each column are written in different groups.
Input
The first line contains two space-separated integers n and m — cabinet dimensions (1 <= n,m <= 100).
The next n lines contain m space-separated integers a
i,j — number of the group that recorded the disc lying on the i-th shelf in the j-th column (1<= a
i,j <=10
9).
Imprint
In the first line print Impossible if Danila can't arrange everything in such a way that disks are written in different groups in each column, and Possible if such arrangement is possible.
If Danila can achieve what she wants, print the final arrangement of disks in the cabinet. If there are several such arrangements, print any of them.
Examples
| # |
Input |
Output |
| 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 |