問題文

正整数 $N$ と、長さ $2^N$ の $0$ か $1$ からなる数列 $A_0,A_1,\\ldots,A_{2^N-1}$ が与えられます。 $2^N$ 個すべての $S \\subseteq \\{0,1,\\ldots,N-1 \\}$ について、以下の条件を満たす閉曲線 $C$ が存在するか判定し、存在する場合はひとつ構成してください。

• $x = \\sum_{i \\in S} 2^i$ とする。また、点集合 $B_S$ を $\\{ (i+0.5,0.5) | i \\in S \\}$ と定義する。
• 閉曲線 $C$ を $B_S$ を通らずに連続的に動かして、閉曲線上のすべての点の $y$ 座標を負にするような方法が存在するならば、$A_x = 1$ である。
• 閉曲線 $C$ を $B_S$ を通らずに連続的に動かして、閉曲線上のすべての点の $y$ 座標を負にするような方法が存在しないならば、$A_x = 0$ である。

出力方法に関しては、"出力" のチャプターを読んでください。

補足

$C$ が閉曲線であるとは、次のように定義される。

• $C$ は \[0,1\] から $\\mathbb{R}^2$ への連続関数であり、$C(0) = C(1)$ を満たす。

閉曲線 $C$ を点集合 $X$ を通らずに閉曲線 $D$ に連続的に動かせるとは、次のように定義される。

• 次の条件を満たす関数 $f : \[0,1\] \\times \[0,1\] \\rightarrow \\mathbb{R}^2$ が存在する。
  • $f$ は連続。
  • $f(0,t) = C(t)$
  • $f(1,t) = D(t)$
  • $f(x,t) \\notin X$

制約

• $1 \\leq N \\leq 8$
• $A_i = 0,1 \\quad (0 \\leq i \\leq 2^N-1)$
• $A_0 = 1$

---

入力

入力は以下の形式で標準入力から与えられる。

$N$ $A_0A_1 \\cdots A_{2^N-1}$

出力

条件を満たす閉曲線が存在しないならば Impossible と出力せよ。

存在するならば、まず $1$ 行目に Possible と出力せよ。 その後、以下の形式で構成した閉曲線を出力せよ。

$L$ $x_0$ $y_0$ $x_1$ $y_1$ $:$ $x_L$ $y_L$

これは、閉曲線として $(x_0,y_0),(x_1,y_1),\\ldots,(x_L,y_L)$ をこの順に通る閉折れ線を選ぶことを意味する。

出力は次の条件を満たしている必要がある。

• $0 \\leq x_i \\leq N$, $0 \\leq y_i \\leq 1$, $x_i,y_i$ は整数 $\\quad$ ($0 \\leq i \\leq L$)
• $|x_i-x_{i+1}| + |y_i-y_{i+1}| = 1$ $\\quad$ ($0 \\leq i \\leq L-1$)
• $(x_0,y_0) = (x_L,y_L)$

また、閉曲線の長さ $L$ は、 $0 \\leq L \\leq 250000$ を満たす必要がある。

もとの問題で条件を満たす閉曲線が存在するならば、この出力形式のもとでも存在することが証明できる。

---

入力例 1

1
10

出力例 1

Possible
4
0 0
0 1
1 1
1 0
0 0

$S = \\emptyset$ のときは閉曲線上のすべての点の $y$ 座標を負にすることが可能です。

$S = \\{0\\}$ のときはどのようにしても閉曲線上のすべての点の $y$ 座標を負にすることはできません。

---

入力例 2

2
1000

出力例 2

Possible
6
1 0
2 0
2 1
1 1
0 1
0 0
1 0

出力は図のような閉曲線を表しています。

---

入力例 3

2
1001

出力例 3

Impossible

---

入力例 4

1
11

出力例 4

Possible
0
1 1