{"raw_statement":[{"iden":"problem statement","content":"Given are a positive integer $N$ and a sequence of length $2^N$ consisting of $0$s and $1$s: $A_0,A_1,\\ldots,A_{2^N-1}$. Determine whether there exists a closed curve $C$ that satisfies the condition below for all $2^N$ sets $S \\subseteq {0,1,\\ldots,N-1 }$. If the answer is yes, construct one such closed curve.\n\n*   Let $x = \\sum_{i \\in S} 2^i$ and $B_S$ be the set of points ${ (i+0.5,0.5) | i \\in S }$.\n*   If there is a way to continuously move the closed curve $C$ without touching $B_S$ so that every point on the closed curve has a negative $y$\\-coordinate, $A_x = 1$.\n*   If there is no such way, $A_x = 0$.\n\nFor instruction on printing a closed curve, see Output below."},{"iden":"notes","content":"$C$ is said to be a closed curve if and only if:\n\n*   $C$ is a continuous function from $[0,1]$ to $\\mathbb{R}^2$ such that $C(0) = C(1)$.\n\nWe say that a closed curve $C$ can be continuously moved without touching a set of points $X$ so that it becomes a closed curve $D$ if and only if:\n\n*   There exists a function $f : [0,1] \\times [0,1] \\rightarrow \\mathbb{R}^2$ that satisfies all of the following.\n    *   $f$ is continuous.\n    *   $f(0,t) = C(t)$.\n    *   $f(1,t) = D(t)$.\n    *   $f(x,t) \\notin X$."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 8$\n*   $A_i = 0,1 \\quad (0 \\leq i \\leq 2^N-1)$\n*   $A_0 = 1$"},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$A_0A_1 \\cdots A_{2^N-1}$"},{"iden":"sample input 1","content":"1\n10"},{"iden":"sample output 1","content":"Possible\n4\n0 0\n0 1\n1 1\n1 0\n0 0\n\nWhen $S = \\emptyset$, we can move this curve so that every point on it has a negative $y$\\-coordinate.\n![image](https://img.atcoder.jp/agc043/d44ca639698b4c14bb84b90da5442ca6.png)\nWhen $S = {0}$, we cannot do so.\n![image](https://img.atcoder.jp/agc043/5a960a0c4167e8593b6c8f8af685253d.png)"},{"iden":"sample input 2","content":"2\n1000"},{"iden":"sample output 2","content":"Possible\n6\n1 0\n2 0\n2 1\n1 1\n0 1\n0 0\n1 0\n\nThe output represents the following curve:\n![image](https://img.atcoder.jp/agc043/283e490d520a451f1b15160900c9b545.png)"},{"iden":"sample input 3","content":"2\n1001"},{"iden":"sample output 3","content":"Impossible"},{"iden":"sample input 4","content":"1\n11"},{"iden":"sample output 4","content":"Possible\n0\n1 1"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}