AT_agc043_e [AGC043E] Topology

[problemUrl]: https://atcoder.jp/contests/agc043/tasks/agc043_e 正整数 $ 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 $ を満たす必要がある。 もとの問題で条件を満たす閉曲線が存在するならば、この出力形式のもとでも存在することが証明できる。

### 補足 $ 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 $ 座標を負にすることが可能です。 !\[\](https://img.atcoder.jp/agc043/d44ca639698b4c14bb84b90da5442ca6.png) $ S\ =\ \{0\} $ のときはどのようにしても閉曲線上のすべての点の $ y $ 座標を負にすることはできません。 !\[\](https://img.atcoder.jp/agc043/5a960a0c4167e8593b6c8f8af685253d.png) ### Sample Explanation 2 出力は図のような閉曲線を表しています。 !\[\](https://img.atcoder.jp/agc043/283e490d520a451f1b15160900c9b545.png)