Problem Statement

Cat Snuke likes drawing pictures.  He came up with a new way to draw interesting pictures. First, he
chooses an integer n and two permutations of integers between 0 and 2^n-1, inclusive, p and q. Then,
he prepares a board divided into 2^n x 2^n cells. The cell at the intersection of the i-th row and
the j-th column (both 0-based) is called cell (i, j). He paints the cell (i, j) black if (p[i] AND
q[j]) is nonzero. Otherwise he paints the cell white. (Here AND is the bitwise AND operator).  You
are given an int n and a String[] picture. The j-th character of the i-th element of picture
represents the color of the cell (i, j): '1' represents black and '0' white. Determine whether Snuke
can draw this picture using the method described above. Return "Possible" if this is possible and
"Impossible" otherwise.


Method signature: String isPossible(int n, String[] picture)
Time limit (s): 2.000
Memory limit (MB): 256


Constraints

- n will be between 1 and 6, inclusive.
- picture will contain exactly 2^n elements.
- Each element of picture will contain exactly 2^n elements.
- Each character in picture will be either '0' or '1'.


Examples

0)

2
{"0011",
 "1010",
 "0000",
 "1011"}
Returns: "Possible"

For example, Snuke can draw this picture by choosing the two permutations p = {1, 2, 0, 3} and q = {2, 0, 3, 1}.


1)

2
{"0011",
 "1000",
 "0001",
 "1011"}
Returns: "Impossible"

Snuke can't draw this picture.


2)

1
{"01",
 "00"}
Returns: "Possible"


3)

3
{"01010011",
 "11110111",
 "11110011",
 "00000000",
 "11110101",
 "11010111",
 "11110000",
 "11000101"}
Returns: "Possible"


4)

4
{"0000000000000000",
 "0000011111100000",
 "0000000110000000",
 "0000000110000000",
 "0000000110000000",
 "0000000000000000",
 "0000011111000000",
 "0000110000000000",
 "0000110000000000",
 "0000011111000000",
 "0000000000000000",
 "0000001111100000",
 "0000011000110000",
 "0000011000110000",
 "0000001111100000",
 "0000000000000000"}
Returns: "Impossible"
TCO.

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.