题目描述

正整数 $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$ である。

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

输入格式

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

$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$ を満たす必要がある。

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

题目大意

给定正整数 $N (1\leq N \leq 8)$以及一个长度为 $2^N$ 的 $01$ 序列 $A_0,A_1, \cdots ,A_{2^N-1}$（保证 $A_0=1$）。判断是否存在一条闭合曲线 $C$，它对于所有的 $2^N$ 个集合 $S \subseteq \{0,1, \cdots ,N-1\}$ 都满足以下条件：

• 令 $x=\sum_{i \in S} 2^i$，$B_S$ 是点集 $\{(i+0,5,0,5) \mid i \in S\}$；
• 若 $A_x=1$，则存在一种方法连续地移动闭曲线 $C$ ，使得移动后的 $C$ 上的任意一点的 $y$ 坐标都为负，且在此过程中 $C$ 不碰到 $B_S$；
• 若 $A_x=0$，则不存在这样一种方法。

$C$ 是一条闭曲线，当且仅当：

• $C$ 是一个连续函数 $C: [0,1] \rightarrow \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) \not\in X$

若存在这样的 $C$，请构造一条这样的 $C$ 并输出，格式是：

先输出一个整数 $L$，需满足 $0\leq L \leq 250000$。

接下来的 $L+1$ 行，每行两个整数 $x,y$，表示你构造的闭曲线 $C$ 是一条依次经过这 $L$ 个点的多边形，需满足：

• $0\leq x_i \leq N$，$0\leq y_i \leq 1$，且 $x_i,y_i$ 是整数，其中 $0\leq i \leq L$。
• $|x_i-x_{i+1}|+|y_i-y_{i+1}|=1$，其中 $0\leq i \leq L-1$。
• $(x_0,y_0)=(x_L,y_L)$。

可以证明，如果存在一条闭曲线满足题目中的要求，那么也存在一条闭曲线能够用这种方式表示出来。

1
10

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

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

提示

補足

$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$

Sample Explanation 1

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

Sample Explanation 2

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