AtCoder Grand Contest 043 - Topology

Given are a positive integer N and a sequence of length 2^N consisting of 0s and 1s: 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.

* Let x = \sum_{i \in S} 2^i and B_S be the set of points \\{ (i+0.5,0.5) | i \in S \\}.
* 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.
* If there is no such way, A_x = 0.



For instruction on printing a closed curve, see Output below.

Constraints

* 1 \leq N \leq 8
* A_i = 0,1 \quad (0 \leq i \leq 2^N-1)
* A_0 = 1

Input

Input is given from Standard Input in the following format:


N
A_0A_1 \cdots A_{2^N-1}


Output

If there is no closed curve that satisfies the condition, print `Impossible`.

If such a closed curve exists, print `Possible` in the first line. Then, print one such curve in the following format:


L
x_0 y_0
x_1 y_1
:
x_L y_L


This represents the closed polyline that passes (x_0,y_0),(x_1,y_1),\ldots,(x_L,y_L) in this order.

Here, all of the following must be satisfied:

* 0 \leq x_i \leq N, 0 \leq y_i \leq 1, and x_i, y_i are integers. (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).



Additionally, the length of the closed curve L must satisfy 0 \leq L \leq 250000.

It can be proved that, if there is a closed curve that satisfies the condition in Problem Statement, there is also a closed curve that can be expressed in this format.

Examples

Input

1
10


Output

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


Input

2
1000


Output

Possible
6
1 0
2 0
2 1
1 1
0 1
0 0
1 0


Input

2
1001


Output

Impossible


Input

1
11


Output

Possible
0
1 1

Source: atcoder | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())
A = list(map(int, readline().rstrip().decode()))
minimal_sets = []
for n in range(1 << N):
	s = n
	is_min = A[n] == 0
	while s:
		s = s - 1 & n
		if A[n] == 1 and A[s] == 0:
			print('Impossible')
			exit()
		if A[s] == 0:
			is_min = False
	if is_min:
		minimal_sets.append(n)

def make(nums, x):
	if not nums:
		return [(x, 0)]
	path = []
	if len(nums) == 1:
		n = nums[0]
		for i in range(x, n + 1):
			path.append((i, 0))
		path += [(n + 1, 0), (n + 1, 1), (n, 1), (n, 0)]
		for i in range(n - 1, x - 1, -1):
			path.append((i, 0))
		return path
	n = nums[0]
	for i in range(x, n + 1):
		path.append((i, 0))
	P = make(nums[1:], n + 1)
	path += P
	path += [(n, 0), (n, 1), (n + 1, 1), (n + 1, 0)]
	path += P[::-1][1:]
	path += [(n + 1, 1), (n, 1), (n, 0)]
	for i in range(n - 1, x - 1, -1):
		path += [(i, 0)]
	return path
path = [(0, 0)]
for n in minimal_sets:
	path += make([i for i in range(N) if n & 1 << i], 0)[1:]
print('Possible')
print(len(path) - 1)
print('\n'.join(('{} {}'.format(x, y) for (x, y) in path)))


import sys
from heapq import *

def first_1(x):
	if x:
		i = 0
		while x & 1 == 0:
			x >>= 1
			i += 1
		return i

def sep_single(s):
	if s:
		r = 1 << s.bit_length() - 1
		i = s.bit_length() - 1
		while s:
			if r & s:
				yield (-i, r)
				s ^= r
			r >>= 1
			i -= 1

def prepare_to_right(g, x):
	(x0, y0) = g[-1]
	if x0 < x and y0:
		y0 = 0
		g.append((x0, 0))
	while x0 < x:
		x0 += 1
		g.append((x0, 0))

def prepare_to_left(g, x):
	(x0, y0) = g[-1]
	if x + 1 < x0 and y0:
		y0 = 0
		g.append((x0, 0))
	while x + 1 < x0:
		x0 -= 1
		g.append((x0, 0))

def append_to_right(g, x, y):
	prepare_to_right(g, x)
	(x0, y0) = g[-1]
	if y != y0:
		g.append((x, y))
	g.append((x + 1, y))

def subloop_tp_group(g):
	x = 0
	while g & 1 == 0:
		g >>= 1
		x += 1
	loop = [(x + 1, 0)]
	tail = [(x, 0), (x, 1), (x + 1, 1)]
	g >>= 1
	x += 1
	while g:
		while g & 1 == 0:
			g >>= 1
			x += 1
		prepare_to_right(loop, x)
		prepare_to_right(tail, x)
		rev = reversed(loop)
		append_to_right(loop, x, 1)
		loop.append((x + 1, 0))
		loop.extend(rev)
		loop.extend(tail)
		append_to_right(loop, x, 0)
		append_to_right(tail, x, 1)
		g >>= 1
		x += 1
	loop.extend(reversed(tail))
	return loop
N = int(input())
single = 0
tpg = []
for i in range(1 << N):
	a = int(sys.stdin.read(1))
	if bin(i).count('1') == 1:
		if a == 0:
			single |= i
	else:
		b = i & single
		if i and b | a == 0 and all((p & i != p for (n, p) in tpg)):
			heappush(tpg, (-first_1(i), i))
		elif i | a == 0 or (a and (b or any((p & i == p for (n, p) in tpg)))):
			print('Impossible')
			break
else:
	print('Possible')
	loop = []
	for (n, g) in merge(sep_single(single), nsmallest(len(tpg), tpg)):
		subloop = subloop_tp_group(g)
		if loop:
			prepare_to_left(loop, subloop[0][0])
			if loop[-1] == subloop[0]:
				loop.pop()
		loop.extend(subloop)
	if not loop:
		loop.append((0, 0))
	prepare_to_right(loop, loop[0][0])
	print(len(loop) - 1)
	for p in loop:
		print(*p)


res = []
n = int(input())
a = [int(c) for c in input()]

def solve():
	if a[0] == 0:
		return False
	for x in range(1, 2 ** n):
		s = list(filter(lambda i: x >> i & 1, range(n)))
		xl = [x >> i & 1 for i in range(n)]
		if a[x] == 0:
			for d in s:
				y = x ^ 1 << d
				if a[y] == 1:
					break
			else:
				continue

			def move_ceiling(r, dest):
				(i, j) = r[-1]
				if i < dest:
					for i in range(i, dest):
						if xl[i] == 0 and j == 1:
							r.append((i, 0))
							j = 0
						elif xl[i] == 1 and j == 0:
							r.append((i, 1))
							j = 1
						r.append((i + 1, j))
				else:
					for i in range(i, dest, -1):
						if xl[i - 1] == 0 and j == 1:
							r.append((i, 0))
							j = 0
						elif xl[i - 1] == 1 and j == 0:
							r.append((i, 1))
							j = 1
						r.append((i - 1, j))
				return r

			def move_floor(r, dest):
				(i, j) = r[-1]
				if j == 1:
					r.append((i, 0))
				for i in range(i + 1, dest + 1) if i < dest else range(i - 1, dest - 1, -1):
					r.append((i, 0))
				return r
			r = [(s[0] + 1, 1), (s[0], 1), (s[0], 0), (s[0] + 1, 0)]
			cur = s[0] + 1
			for d in s[1:]:
				r0 = [(d + 1, 1)] if cur == d else move_ceiling([(d + 1, 1)], cur)
				r1 = move_ceiling(r.copy(), d + 1)
				r1 = move_floor(r1, cur)
				r1.pop()
				r2 = list(reversed(r))
				r2 = move_floor(r2, d + 1)
				r = r0 + r1 + r2
				cur = d + 1
			r = move_floor(r, n)
			r.reverse()
			r = move_floor(r, n)
			r.pop()
			res.append(r)
		else:
			for d in s:
				y = x ^ 1 << d
				if a[y] != 1:
					return False
	return True
if solve():
	print('Possible')
	r = [(i, j) for r in res for (i, j) in r]
	r.append((n, 0))
	print(len(r) - 1)
	for (i, j) in r:
		print(i, j)
else:
	print('Impossible')


n = int(input())
a = [int(x) for x in input()]
holes = []
for i in range(2 ** n):
	if a[i] == 1:
		continue
	for j in range(i + 1, 2 ** n):
		if j | i == j and a[j] == 1:
			print('Impossible')
			exit()
	if any((k | i == i for k in holes)):
		continue
	else:
		holes.append(i)
print('Possible')
if len(holes) == 0:
	print(0)
	print(1, 1)
	exit()
clockwise = []
for i in range(n):
	locus = []
	for j in range(i + 1):
		locus.append((j, 0))
	locus += [(i, 1), (i + 1, 1), (i + 1, 0)]
	for j in range(i, -1, -1):
		locus.append((j, 0))
	clockwise.append(locus)
m = len(holes)
roops = []
for i in range(m):
	x = holes[i]
	curve = []
	is_first = True
	for j in range(n):
		if x >> j & 1 and is_first:
			curve += clockwise[j]
			is_first = False
		elif x >> j & 1:
			curve = curve + clockwise[j] + curve[::-1] + clockwise[j][::-1]
	roops.append(curve)
ans = []
for x in roops:
	ans += x
L = -1
for (i, x) in enumerate(ans):
	if i > 0 and ans[i] == ans[i - 1]:
		continue
	else:
		L += 1
print(L)
for (i, x) in enumerate(ans):
	if i > 0 and ans[i] == ans[i - 1]:
		continue
	else:
		print(*x)