配点 : $1400$ 点

問題文

正整数 $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$
• $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
10

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

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

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

2
1000

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

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

2
1001

Impossible

1
11

Possible
0
1 1