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:
#pragma GCC optimize("Ofast")
#include<vector>
#include<queue>
#include<iostream>
#include<fstream>
#include<string>
#include<cassert>
#include<algorithm>
#include<random>
#include<map>
#include<set>
#include <bitset>
#include<ctime>

using namespace std;

//int mod = 998244353;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef vector<int>vi;
typedef vector<ll>vl;
typedef vector<char>vc;
typedef vector<string>vs;
typedef vector<vector<int>>vii;
typedef vector<vector<char>>vvc;
typedef vector<vector<ll>>vll;
typedef vector< pair<ll, ll>>vpll;
typedef vector< pair<ld, ld>>vpld;
typedef vector< pair<int, int>>vpi;
typedef pair<ld, ld>pld;
#define mp make_pair
#define pb push_back

const int mod = 998244353;
int add(int a, int b)
{
	int c = a + b;
	if (c >= mod)
	{
		c -= mod;
	}
	return c;
}
int dif(int a, int b)
{
	int c = a - b;
	if (c < 0)
	{
		c += mod;
	}
	return c;
}
int mlt(int a, int b)
{
	ll c = a * 1LL * b;
	return c % mod;
}
int ibit(int n, int i)
{
	return ((n >> i) & 1);
}
void outp(vii &ou)
{
	for (int i = 0; i < ou.size(); i++)
	{
		for (int j = 0; j < ou[i].size(); j++)
		{
			cout << ou[i][j] << ' ';
		}
		cout << '\n';
	}
}
int bp(int x, int y)
{
	if (y == 0)
	{
		return 1;
	}
	int a = 0;
	if (!(y % 2))
	{
		a = bp(x, y / 2);
	}
	return (y % 2) ? mlt(bp(x, y - 1), x) : mlt(a, a);
}
int obr(int x)
{
	return bp(x, mod - 2);
}
const int maxn = 2000007;
int fact[2000007], ofact[2000007];
void prec()
{
	fact[0] = 1;
	ofact[0] = 1;
	for (int i = 1; i < maxn; i++)
	{
		fact[i] = mlt(fact[i - 1], i);
	}
	//cerr << "sdsds" << endl;
	ofact[maxn - 1] = obr(fact[maxn - 1]);
	for (int i = maxn - 2; i > 0; i--)
	{
		ofact[i] = mlt(ofact[i + 1], i + 1);
	}
}
int c(int a, int b)
{
	if (a == 0)return 1;
	return ((a <= b) && (a >= 0)) ? mlt(fact[b], mlt(ofact[a], ofact[b - a])) : 0;
}
ll gcd(ll x, ll y)
{
	//cerr << x << y << endl;
	if (x == 0)return y;
	return(x > y) ? gcd(y, x) : gcd(y%x, x);
}
int obr2(int n)
{
	int x = fact[n - 1];
	x = mlt(x, ofact[n]);
	return x;
}
void crv(int nn, vpi &v)
{
	cerr << nn << endl;
	if (nn > 0) {
		int n = nn;
		for (int i = 0; i < n; i++)v.pb({ i + 1, 0 });
		v.pb({ n,1 });
		v.pb({ n - 1, 1 });
		for (int i = n - 1; i >= 0; i--)v.pb({ i, 0 });
	}
	if (nn < 0) {
		int n = -nn;
		for (int i = 0; i < n - 1; i++)v.pb({ i + 1, 0 });
		v.pb({ n - 1,1 });
		v.pb({ n , 1 });
		for (int i = n; i >= 0; i--)v.pb({ i, 0 });
	}
}
void solve(istream &cin = std::cin, ostream &cout = std::cout)
{
	vii imb(9);
	imb[0] = { 1 };
	for (int i = 1; i <= 8; i++)
	{
		for (int j = 0; j < imb[i - 1].size(); j++)imb[i].pb(imb[i - 1][j]);
		imb[i].pb(i + 1);
		for (int j = imb[i - 1].size(); j >= 0; j--)imb[i].pb((-1)*imb[i - 1][j]);
		imb[i].pb(-i - 1);
	}
	//cerr << "here" << endl;
	int n;
	cin >> n;
	vi good(1 << n);
	for (int i = 0; i < good.size(); i++)
	{
		char c;
		cin >> c;
		good[i] = c - '0';
	}
	int val = 0;
	//	cerr << 433 << endl;
	for (int a = 0; a < good.size(); a++)
		for (int b = 0; b < good.size(); b++)
			if ((a | b) == b)
				if ((!good[a]) && (good[b]))
				{
					//	cerr << a << ' ' << b << endl;
					val = 1;
				}
	//	cerr << 5 << ' ' << 7 << ' ' << (5 | 7) << endl;
	if (val)cout << "Impossible" << endl;
	else
	{
		cout << "Possible" << endl;
		//cerr << 1111 << endl;
		vpi ay = { { 0,0 } };
		for (int m = 0; m < good.size(); m++)
		{
			//cerr << m << endl;
			if (!good[m])
			{
				cerr << m << endl;
				vi v;
				for (int i = 0; i <= 8; i++)if (ibit(m, i))v.pb(i);
				cerr << m << ' ' << v.size() << endl;
				if (v.size() > 8)cout << "111" << endl;
				for (int i = 0; i < imb[v.size() - 1].size(); i++)
				{
					cerr << imb[v.size() - 1][i] << endl;
					//	cerr << i << endl;
					if (imb[v.size()][i] > 0)crv(v[imb[v.size() - 1][i] - 1] + 1, ay);
					if (imb[v.size()][i] < 0)crv(-v[(-imb[v.size() - 1][i]) - 1] - 1, ay);
				}
			}
		}
		cout << ay.size() - 1 << endl;
		for (int i = 0; i < ay.size(); i++)cout << ay[i].first << ' ' << ay[i].second << endl;
	}
}
int main()
{
	solve();
	int n;
	cin >> n;
}