Problem: 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

Solution (in CPP):

Solution:
#include <bits/stdc++.h>

#define debug(...) fprintf(stderr, __VA_ARGS__)

#ifndef AT_HOME
#define getchar() IO::myGetchar()
#define putchar(x) IO::myPutchar(x)
#endif

namespace IO {
	static const int IN_BUF = 1 << 23, OUT_BUF = 1 << 23;

	inline char myGetchar() {
		static char buf[IN_BUF], *ps = buf, *pt = buf;
		if (ps == pt) {
			ps = buf, pt = buf + fread(buf, 1, IN_BUF, stdin);
		}
		return ps == pt ? EOF : *ps++;
	}

	template<typename T>
	inline bool read(T &x) {
		bool op = 0;
		char ch = getchar();
		x = 0;
		for (; !isdigit(ch) && ch != EOF; ch = getchar()) {
			op ^= (ch == '-');
		}
		if (ch == EOF) {
			return false;
		}
		for (; isdigit(ch); ch = getchar()) {
			x = x * 10 + (ch ^ '0');
		}
		if (op) {
			x = -x;
		}
		return true;
	}

	inline int readStr(char *s) {
		int n = 0;
		char ch = getchar();
		for (; isspace(ch) && ch != EOF; ch = getchar())
			;
		for (; !isspace(ch) && ch != EOF; ch = getchar()) {
			s[n++] = ch;
		}
		s[n] = '\0';
		return n;
	}

	inline void myPutchar(char x) {
		static char pbuf[OUT_BUF], *pp = pbuf;
		struct _flusher {
			~_flusher() {
				fwrite(pbuf, 1, pp - pbuf, stdout);
			}
		};
		static _flusher outputFlusher;
		if (pp == pbuf + OUT_BUF) {
			fwrite(pbuf, 1, OUT_BUF, stdout);
			pp = pbuf;
		}
		*pp++ = x;
	}

	template<typename T>
	inline void print_(T x) {
		if (x == 0) {
			putchar('0');
			return;
		}
		static int num[40];
		if (x < 0) {
			putchar('-');
			x = -x;
		}
		for (*num = 0; x; x /= 10) {
			num[++*num] = x % 10;
		}
		while (*num){
			putchar(num[*num] ^ '0');
			--*num;
		}
	}

	template<typename T>
	inline void print(T x, char ch = '\n') {
		print_(x);
		putchar(ch);
	}

	inline void printStr_(const char *s, int n = -1) {
		if (n == -1) {
			n = strlen(s);
		}
		for (int i = 0; i < n; ++i) {
			putchar(s[i]);
		}
	}

	inline void printStr(const char *s, int n = -1, char ch = '\n') {
		printStr_(s, n);
		putchar(ch);
	}
}
using namespace IO;

const int N = 8;

int n;
char a[1 << N | 5];

std::vector<std::pair<int, int>> get(int S, int lst) {
	int k = 0;
	while (!(S >> k & 1)) {
		++k;
	}
	std::vector<std::pair<int, int>> res;
	if (S == (1 << k)) {
		for (int i = lst; i < k; ++i) {
			res.push_back({i, 1});
		}
		res.push_back({k, 1});
		res.push_back({k, 0});
		for (int i = k - 1; i >= lst; --i) {
			res.push_back({i, 1});
		}
		return res;
	}
	std::vector<std::pair<int, int>> t = get(S ^ (1 << k), k + 1);
	for (int i = lst; i < k; ++i) {
		res.push_back({i, 1});
	}
	res.push_back({k, 1});
	for (auto i : t) {
		res.push_back(i);
	}
	res.push_back({k, 1});
	res.push_back({k, 0});
	std::reverse(t.begin(), t.end());
	for (auto i : t) {
		res.push_back(i);
	}
	res.push_back({k, 0});
	for (int i = k - 1; i >= lst; --i) {
		res.push_back({i, 1});
	}
	return res;
}

void solve() {
	read(n);
	readStr(a);
	for (int i = 1; i < (1 << n); ++i) {
		if (a[i] == '1') {
			for (int j = i; j; j = (j - 1) & i) {
				if (a[j] == '0') {
					printStr("Impossible");
					return;
				}
			}
		}
	}
	std::vector<std::pair<int, int>> res;
	for (int i = 1; i < (1 << n); ++i) {
		if (a[i] == '0') {
			bool flag = 1;
			for (int j = i; j; j = (j - 1) & i) {
				if (i != j && a[j] == '0') {
					flag = 0;
					break;
				}
			}
			if (!flag) {
				continue;
			}
			std::vector<std::pair<int, int>> t(get(i, 0));
			for (auto v : t) {
				res.push_back(v);
			}
		}
	}
	int x = 0, y = 0;
	std::vector<std::pair<int, int>> ans(1, {0, 0});
	for (auto v : res) {
		if (y != v.second) {
			y = v.second;
			ans.push_back({x, y});
		}
		if (x == v.first) {
			++x;
		} else {
			--x;
		}
		ans.push_back({x, y});
	}
	if (y) {
		y = 0;
		ans.push_back({x, y});
	}
	printStr("Possible");
	print((int)ans.size() - 1);
	for (auto v : ans) {
		print(v.first, ' '), print(v.second);
	}
}

int main() {
	int T = 1;
	// read(T);
	while (T--) {
		solve();
	}
}