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 翻译