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 <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <time.h>
#include <stdlib.h>
#include <string>
#include <bitset>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <sstream>
#include <stack>
#include <iomanip>
#include <assert.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef pair<int,int> pii;
typedef long long ll;
typedef double ld;
typedef vector<int> vi;
#define fi first
#define se second
#define fe first
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define Edg int M=0,fst[SZ],vb[SZ],nxt[SZ];void ad_de(int a,int b){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;}void adde(int a,int b){ad_de(a,b);ad_de(b,a);}
#define Edgc int M=0,fst[SZ],vb[SZ],nxt[SZ],vc[SZ];void ad_de(int a,int b,int c){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;vc[M]=c;}void adde(int a,int b,int c){ad_de(a,b,c);ad_de(b,a,c);}
#define es(x,e) (int e=fst[x];e;e=nxt[e])
#define esb(x,e,b) (int e=fst[x],b=vb[e];e;e=nxt[e],b=vb[e])
const int MOD=1e9+7;
#define SZ 666666
int n;
char a[SZ];
bool v[SZ];
vi neg(vi x)
{
	reverse(x.begin(),x.end());
	for(auto&y:x) y=-y;
	return x;
}
vi operator + (vi a,const vi&b)
{
	for(auto x:b) a.pb(x);
	return a;
}
vi operator - (vi a,const vi&b)
{
	return a+neg(b);
}
vi cs(vi a,int l,int r)
{
	if(l==r)
		return {a[l]};
	int m=(l+r)>>1;
	vi L=cs(a,l,m),R=cs(a,m+1,r);
	return L+R-L-R;
}
vi CL(vi t)
{
	return t;
}
vi v1{1},v2{2};
vi AND(vi p,vi q)
{
	return CL(p+p+v1+p+p-v1+v2-q-v2-q+v2-q-v2-q);
}
int main()
{
	cin>>n>>a;
	bool ok=1;
	vi g;
	for(int i=0;i<(1<<n);++i) if(a[i]=='0'&&!v[i])
	{
		for(int j=0;j<(1<<n);++j) if((j&i)==i)
			v[j]=1,ok&=a[j]=='0';
		vi t;
		for(int j=0;j<n;++j) if(i&(1<<j)) t.pb(j+1);
		vi w=cs(t,0,t.size()-1);
		g=g+w;
	}
	if(!ok)
	{
		puts("Impossible");
		return 0;
	}
	puts("Possible");
	vector<pii> v;
	v.pb(pii(0,0));
	for(auto c:g)
	{
		int x=abs(c);
		if(c>0)
		{
			v.pb(pii(x-1,0));
			v.pb(pii(x-1,1));
			v.pb(pii(x,1));
			v.pb(pii(x,0));
		}
		else
		{
			v.pb(pii(x,0));
			v.pb(pii(x,1));
			v.pb(pii(x-1,1));
			v.pb(pii(x-1,0));
		}
	}
	v.pb(pii(0,0));
	vector<pii> vt;
	for(int i=0;i<v.size();++i)
	{
		pii A=v[i],B=v[(i+1)%v.size()];
		vt.pb(A);
		int g=abs(A.fi-B.fi)+abs(A.se-B.se);
		if(g)
		{
			for(int j=1;j<=g;++j)
			{
				pii s(A.fi+(B.fi-A.fi)/g*j,
				A.se+(B.se-A.se)/g*j);
				vt.pb(s);
			}
		}
	}
	vt.erase(unique(vt.begin(),vt.end()),vt.end());
	v=vt;
	printf("%d\n",int(v.size())-1);
	for(auto c:v) printf("%d %d\n",c.fi,c.se);
}