Matrix Rotation to Sorted Rows

Given an \(N \times N\) matrix, determine whether there exists a rotation (by 90-degree increments) that makes every row sorted in non-decreasing order. The allowed rotations are by 90, 180, or 270 degrees clockwise.

More formally, let \(A\) be the given matrix and let \(A_k\) denote the matrix obtained by rotating \(A\) by \(k \times 90^\circ\) clockwise (where \(0 \leq k \leq 3\)). The task is to check if there exists an integer \(k\) such that every row of \(A_k\) is sorted in non-decreasing order. If such an orientation exists, output Possible; otherwise, output Impossible.

inputFormat

The first line contains an integer (N) representing the number of rows (and columns) of the matrix. Each of the next (N) lines contains (N) space-separated integers denoting a row of the matrix.

outputFormat

Output a single line containing either Possible if there exists a rotation where every row is sorted in non-decreasing order, or Impossible if no such rotation exists.## sample

3
1 3 5
2 3 4
3 5 6

Possible