AT_agc043_e [AGC043E] Topology

给定一个正整数 $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$。 - 如果不存在上述方法，则 $A_x = 0$。 关于输出方式，请阅读“输出格式”章节。

输入通过标准输入给出，格式如下： > $N$ $A_0A_1\cdots A_{2^N-1}$

如果不存在满足条件的闭曲线，则输出 `Impossible`。 如果存在，首先输出一行 `Possible`。然后，按照以下格式输出你构造的闭曲线： > $L$ $x_0$ $y_0$ $x_1$ $y_1$ $\cdots$ $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$ 为整数，$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)$ 此外，闭曲线的长度 $L$ 需满足 $0 \leq L \leq 250000$。 可以证明，如果原问题中存在满足条件的闭曲线，则在此输出格式下也一定存在。

### 补充说明 闭曲线 $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$，$0 \leq i \leq 2^N-1$ - $A_0 = 1$ ### 样例解释 1 当 $S = \emptyset$ 时，可以将闭曲线上的所有点的 $y$ 坐标变为负数。  当 $S = \{0\}$ 时，无论如何都无法使闭曲线上的所有点的 $y$ 坐标变为负数。  ### 样例解释 2 输出表示如图所示的闭曲线。  由 ChatGPT 4.1 翻译