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 target("avx")  // CPU 処理並列化
// #pragma GCC optimize("O3")  // CPU 処理並列化
// #pragma GCC optimize("unroll-loops")  // 条件処理の呼び出しを減らす
// #define BEGIN_STACK_EXTEND(size) void * stack_extend_memory_ = malloc(size);void * stack_extend_origin_memory_;char * stack_extend_dummy_memory_ = (char*)alloca((1+(int)(((long long)stack_extend_memory_)&127))*16);*stack_extend_dummy_memory_ = 0;asm volatile("mov %%rsp, %%rbx\nmov %%rax, %%rsp":"=b"(stack_extend_origin_memory_):"a"((char*)stack_extend_memory_+(size)-1024));
// #define END_STACK_EXTEND asm volatile("mov %%rax, %%rsp"::"a"(stack_extend_origin_memory_));free(stack_extend_memory_);

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
#include<bitset>
#include<numeric>
#include<unordered_set>
#include<unordered_map>
#include<complex>
using namespace std;
const long long mod=998244353;
const long long inf=mod*mod;
const long long d2=(mod+1)/2;
const long double EPS=1e-9;
const double INF=1e+10;
const double PI=acos(-1.0);
const int C_SIZE = 3100000;
const int UF_SIZE = 3100000;
namespace{
	long long fact[C_SIZE];
	long long finv[C_SIZE];
	long long inv[C_SIZE];
	long long Comb(int a,int b){
	 	if(a<b||b<0)return 0;
	 	return fact[a]*finv[b]%mod*finv[a-b]%mod;
	}
	void init_C(int n){
		fact[0]=finv[0]=inv[1]=1;
		for(int i=2;i<n;i++){
			inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
		}
		for(int i=1;i<n;i++){
			fact[i]=fact[i-1]*i%mod;
			finv[i]=finv[i-1]*inv[i]%mod;
		}
	}
	long long pw(long long a,long long b){
		if(a<0LL)return 0;
		if(b<0LL)return 0;
		long long ret=1;
		while(b){
			if(b%2)ret=ret*a%mod;
			a=a*a%mod;
			b/=2;
		}
		return ret;
	}
	long long pw_mod(long long a,long long b,long long M){
		if(a<0LL)return 0;
		if(b<0LL)return 0;
		long long ret=1;
		while(b){
			if(b%2)ret=ret*a%M;
			a=a*a%M;
			b/=2;
		}
		return ret;
	}
	int pw_mod_int(int a,int b,int M){
		if(a<0)return 0;
		if(b<0)return 0;
		int ret=1;
		while(b){
			if(b%2)ret=(long long)ret*a%M;
			a=(long long)a*a%M;
			b/=2;
		}
		return ret;
	}
	int ABS(int a){return max(a,-a);}
	long long ABS(long long a){return max(a,-a);}
	double ABS(double a){return max(a,-a);}
	int sig(double r) { return (r < -EPS) ? -1 : (r > +EPS) ? +1 : 0; }
	int UF[UF_SIZE];
	void init_UF(int n){
		for(int i=0;i<n;i++)UF[i]=-1;
	}
	int FIND(int a){
		if(UF[a]<0)return a;
		return UF[a]=FIND(UF[a]);
	}
	void UNION(int a,int b){
		a=FIND(a);b=FIND(b);if(a==b)return;
		if(UF[a]>UF[b])swap(a,b);
		UF[a]+=UF[b];UF[b]=a;
	}
}
// ここから編集しろ
char in[310];
int dp[310];
int n;
vector<pair<int,int> >v;
vector<pair<int,int> >cm;
vector<pair<int,int> > ad(vector<int>a){
	vector<pair<int,int> > ret;
	if(a.size()==1){
		ret.push_back(make_pair(a[0],1));
		ret.push_back(make_pair(a[0],0));
		return ret;
	}
	ret.push_back(make_pair(a[0],1));
	vector<int>b;
	for(int i=1;i<a.size();i++)
		b.push_back(a[i]);
	vector<pair<int,int> >S=ad(b);
	for(int i=0;i<S.size();i++){
		ret.push_back(S[i]);
	}
	ret.push_back(make_pair(a[0],1));
	ret.push_back(make_pair(a[0],0));
	reverse(S.begin(),S.end());
	for(int i=0;i<S.size();i++){
		ret.push_back(S[i]);
	}
	ret.push_back(make_pair(a[0],0));
	
	return ret;
}
void f(int a){
	if(dp[a])return;
	if(a==0)return;
	dp[a]=1;
	bool ok=true;
	for(int i=0;i<n;i++){
		if(!(a&(1<<i)))continue;
		if(in[a-(1<<i)]=='0'){
			ok=false;
			f(a-(1<<i));
			
		}
	}
	if(ok){
		// printf("[%d]\n",a);
		vector<int>q;
		for(int i=0;i<n;i++){
			if(a&(1<<i))q.push_back(i);
		}
		vector<pair<int,int> >ret=ad(q);
		int now=0;
			for(int i=0;i<ret.size();i++){
				if(now<=ret[i].first){
					while(now<ret[i].first){
						now++;
						v.push_back(make_pair(now,0));
					}
					if(ret[i].second){
						v.push_back(make_pair(now,1));
						v.push_back(make_pair(now+1,1));
					}
					v.push_back(make_pair(now+1,0));
					now++;
				}else{
					while(now>1+ret[i].first){
						now--;
						v.push_back(make_pair(now,0));
					}
					if(ret[i].second){
						v.push_back(make_pair(now,1));
						v.push_back(make_pair(now-1,1));
					}
					v.push_back(make_pair(now-1,0));
					now--;
				}
			}
			while(now>0){
				now--;
				v.push_back(make_pair(now,0));
			}
	}
}
int main_(){
	// int a=3;
	// n=a;
	int a;scanf("%d",&a);
	n=a;
	scanf("%s",in);
	v.clear();
	cm.clear();
	for(int i=0;i<310;i++)dp[i]=0;
	for(int i=0;i<(1<<a);i++){
		if(in[i]=='1'){
			for(int j=0;j<a;j++){
				if(i&(1<<j)){
					if(in[i-(1<<j)]=='0'){
						printf("Impossible\n");
						return 0;
					}
				}
			}
		}
	}
	printf("Possible\n");
	if(in[(1<<a)-1]=='1'){
		printf("0\n");
		printf("0 0\n");
		return 0;
	}
	v.push_back(make_pair(0,0));
	f((1<<a)-1);
	// int now=0;	
	// for(int i=0;i<cm.size();i++){
	// 	if(now<=cm[i].first){
	// 		while(now<cm[i].first){
	// 			now++;
	// 			v.push_back(make_pair(now,0));
	// 		}
	// 		if(cm[i].second){
	// 			v.push_back(make_pair(now,1));
	// 			v.push_back(make_pair(now+1,1));
	// 		}
	// 		v.push_back(make_pair(now+1,0));
	// 		now++;
	// 	}else{
	// 		while(now>1+cm[i].first){
	// 			now--;
	// 			v.push_back(make_pair(now,0));
	// 		}
	// 		if(cm[i].second){
	// 			v.push_back(make_pair(now,1));
	// 			v.push_back(make_pair(now-1,1));
	// 		}
	// 		v.push_back(make_pair(now-1,0));
	// 		now--;
	// 	}
	// }
	// while(now>0){
	// 	now--;
	// 	v.push_back(make_pair(now,0));
	// }
	if(v.size()>=250000)while(1);
	printf("%d\n",(int)(v.size())-1);
	for(int i=0;i<v.size();i++){
		printf("%d %d\n",v[i].first,v[i].second);
	}
	for(int i=0;i+1<v.size();i++){
		assert(ABS(v[i].first-v[i+1].first)+ABS(v[i].second-v[i+1].second)==1);
	}
	for(int i=0;i<(1<<a);i++){
		stack<pair<int,int> > S;
		for(int j=0;j+1<v.size();j++){
			if(v[j].first==v[j+1].first)continue;

			int x=min(v[j].first,v[j+1].first);
			int y=v[j].second;
			if(!(i&(1<<x)))continue;
			if(S.size()&&S.top()==make_pair(x,y)){
				S.pop();
			}else S.push(make_pair(x,y));
		}
		if(S.size()==0&&in[i]=='0'){
			printf("NG %d\n",i);
		}else if(S.size()&&in[i]=='1'){
			printf("NG %d\n",i);
		}
	}
	return 0;
}

int main(){
	main_();
	// for(int i=0;i<256;i++){
	// 	if(i%2==0)continue;
	// 	for(int j=0;j<8;j++){
	// 		if(i&(1<<j))in[j]='1';
	// 		else in[j]='0';
	// 	}
	// 	printf("%d:\n",i);
	// 	main_();
	// }
}