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 ll long long
#define ld long double
#define db double
#define pint pair<int,int>
#define mk(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define eb(x,y) emplace_back(x,y)
#define fi first
#define se second
#define Rep(x,y,z) for(int x=y;x<=z;x++)
#define Red(x,y,z) for(int x=y;x>=z;x--)
using namespace std;
char buf[1<<12],*pp1=buf,*pp2=buf,nc;int ny;
//inline char gc() {return pp1==pp2&&(pp2=(pp1=buf)+fread(buf,1,1<<12,stdin),pp1==pp2)?EOF:*pp1++;}
inline char gc(){return getchar();}
inline int read(){
	int x=0;for(ny=1;nc=gc(),(nc<48||nc>57)&&nc!=EOF;)if(nc==45)ny=-1;if(nc<0)return nc;
	for(x=nc-48;nc=gc(),47<nc&&nc<58&&nc!=EOF;x=(x<<3)+(x<<1)+(nc^48));return x*ny;
}
int n;char s[1<<10];vector<pint>ans;
inline string rev(string a){reverse(a.begin(),a.end());return a;}
inline void Solve(int sta){
	int cnt=0;for(int i=0;i<n;i++)cnt+=sta>>i&1;
	if(cnt==1){
		int t=0;for(;t<n;t++)if(sta>>t&1)break;
		Rep(i,1,t)ans.eb(i,0);ans.eb(t,1),ans.eb(t+1,1),ans.eb(t+1,0);
		Red(i,t,0)ans.eb(i,0);
		return;
	}
	string S;S.clear();int i=n-1;
	for(;i>=0;i--)if(sta>>i&1)break;S.pb(i+'a'),S.pb(i+'A');
	for(i--;i>=0;i--)if(sta>>i&1)S=(char)('a'+i)+S+(char)('a'+i)+(char)('A'+i)+rev(S)+(char)('A'+i);
	int now=0;
	for(auto o:S){
		int opt,p,d;
		if(isupper(o))opt=1,p=o-'A';else opt=0,p=o-'a';
		if(now<=p){d=0;Rep(i,now+1,p)ans.eb(i,0);}
		else{d=1;Red(i,now-1,p+1)ans.eb(i,0);}
		if(d&&opt)ans.eb(p,0),now=p;
		else if(d&&!opt)ans.eb(p+1,1),ans.eb(p,1),ans.eb(p,0),now=p;
		else if(!d&&opt)ans.eb(p+1,0),now=p+1;
		else if(!d&&!opt)ans.eb(p,1),ans.eb(p+1,1),ans.eb(p+1,0),now=p+1;
	}Red(i,now-1,0)ans.eb(i,0);
}
int main(){
//	freopen("std.in","r",stdin);
//	freopen("std.out","w",stdout);
	n=read(),scanf("%s",s);
	if(s[0]=='0')return puts("Impossible"),0;
	for(int i=0;i<1<<n;i++){
		if(s[i]=='1'){
			for(int j=0;j<n;j++)if(i>>j&1)
				if(s[i^(1<<j)]=='0')return puts("Impossible"),0;
		}else{
			for(int j=0;j<n;j++)if(!(i>>j&1))
				if(s[i^(1<<j)]=='1')return puts("Impossible"),0;
		}
	}
	ans.eb(0,0);
	for(int i=0;i<1<<n;i++)if(s[i]=='0'){
		bool flg=1;
		for(int j=0;j<n;j++)if((i>>j&1)&&s[i^(1<<j)]=='0')flg=0;
		if(flg)Solve(i);
	}puts("Possible");cout<<ans.size()-1<<'\n';
	for(auto o:ans)cout<<o.fi<<' '<<o.se<<'\n';
	return 0;
}