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 <algorithm>  
#include <iostream>  
#include <sstream>  
#include <string>  
#include <vector>  
#include <queue>  
#include <set>  
#include <map>  
#include <cstdio>  
#include <cstdlib>  
#include <cctype>  
#include <cmath>  
#include <cstring>
#include <list>  
#include <cassert>
#include <climits>
#include <bitset>
#include <chrono>
#include <random>
using namespace std;

#define PB push_back  
#define MP make_pair  
#define SZ(v) ((int)(v).size())  
#define FOR(i,a,b) for(int i=(a);i<(b);++i)  
#define REP(i,n) FOR(i,0,n)  
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)  
#define REPE(i,n) FORE(i,0,n)  
#define FORSZ(i,a,v) FOR(i,a,SZ(v))  
#define REPSZ(i,v) REP(i,SZ(v))  
std::mt19937 rnd((int)std::chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); }

const int MAXN = 8;
struct P { int x, y; P() {} P(int x, int y) :x(x), y(y) {} };

int n;
char s[(1 << MAXN) + 1];
vector<P> ans;

bool solve() {
	if (s[0] == '0') return false;
	vector<int> todo;
	REP(mask, 1 << n) {
		bool anysub = false;
		for (int sub = 0; sub < mask; sub = (sub + (1 << n) - 1 - mask + 1)&mask) if (s[sub] == '0') anysub = true;
		if (s[mask] == '1' && anysub) return false;
		if (s[mask] == '0' && !anysub) todo.PB(mask);
	}
	ans.clear();
	//printf("TODO:"); REPSZ(i, todo) printf(" %x", todo[i]); puts("");
	REPSZ(i, todo) {
		int mask = todo[i];
		vector<int> cur; REP(j, n) if (mask&(1 << j)) cur.PB(j);
		vector<P> path;
		for (int j = SZ(cur) - 1; j >= 0; --j) {
			int x = cur[j];
			if (SZ(path) == 0) {
				path.PB(P(x, 1)); path.PB(P(x + 1, 1)); path.PB(P(x + 1, 0)); path.PB(P(x, 0));
			} else {
				vector<P> oldpath = path; path.clear();
				FOR(xx, x, oldpath[0].x) path.PB(P(xx, 1));
				REPSZ(k, oldpath) path.PB(oldpath[k]);
				for (int xx = oldpath[0].x; xx >= x; --xx) path.PB(P(xx, 1));
				path.PB(P(x, 0));
				path.PB(P(x + 1, 0));
				FORE(xx, x + 1, oldpath[0].x) path.PB(P(xx, 1));
				for (int k = SZ(oldpath) - 1; k >= 0; --k) path.PB(oldpath[k]);
				for (int xx = oldpath[0].x - 1; xx >= x + 1; --xx) path.PB(P(xx, 1));
				path.PB(P(x + 1, 0));
				path.PB(P(x, 0));
			}
		}
		REP(xx, path[0].x) ans.PB(P(xx, 1));
		REPSZ(k, path) ans.PB(path[k]);
		for (int xx = path[0].x; xx >= 1; --xx) ans.PB(P(xx, 1));
	}
	ans.PB(P(0, 1));
	return true;
}

void run() {
	scanf("%d", &n);
	scanf("%s", s); assert(strlen(s) == (1 << n));
	if (!solve()) { printf("Impossible\n"); return; }
	printf("Possible\n");
	printf("%d\n", SZ(ans) - 1);
	REPSZ(i, ans) printf("%d %d\n", ans[i].x, ans[i].y);
}

void verify() {
	int len = SZ(ans) - 1;
	REP(i, len) {
		P a = ans[i], b = ans[i + 1];
		int dx = b.x - a.x, dy = b.y - a.y;
		assert(abs(dx) + abs(dy) == 1);
	}
	assert(ans[0].x == ans[len].x&&ans[0].y == ans[len].y);
	vector<int> seq;
	REP(i, len) {
		P a = ans[i], b = ans[i + 1];
		int dx = b.x - a.x, dy = b.y - a.y, lx = min(a.x, b.x), ly = min(a.y, b.y);
		if (abs(dx) == 1) seq.PB(2 * lx + ly);
	}
	//printf("seq:"); REPSZ(i, seq) printf(" %d", seq[i]); puts("");
	REP(mask, 1 << n) {
		vector<int> nseq;
		REPSZ(i, seq) { int x = seq[i] / 2; if (mask&(1 << x)) nseq.PB(seq[i]); }
		//printf("\tnseq:"); REPSZ(i, nseq) printf(" %d", nseq[i]); puts("");
		vector<int> rem;
		REPSZ(i, nseq) {
			if (SZ(rem) > 0 && nseq[i] == rem.back()) rem.pop_back(); else rem.PB(nseq[i]);
		}
		bool have = SZ(rem) == 0;
		bool want = s[mask] == '1';
		assert(have == want);
	}
}

void stress() {
	REP(rep, 100000) {
		n = 4; // rnd() % 3 + 1;
		REP(i, 1 << n) s[i] = '0' + rnd() % 2; s[1 << n] = '\0';
		bool have = solve();
		if (have) {
			printf("done %d: %s (%s)\n", n, s, have ? "POSSIBLE" : "IMPOSSIBLE");
			//printf("%d\n", SZ(ans) - 1); REPSZ(i, ans) printf("%d %d\n", ans[i].x, ans[i].y);
			verify();
		}
	}
}


int main() {
	run();
	//stress();
	return 0;
}