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>
using namespace std;

typedef long long ll;
typedef pair<int,int> P;

#define fr first
#define sc second
#define chmax(a,b) a=max(a,b)
#define chmin(a,b) a=min(a,b)

vector<P> ret;

void pos(int i){
	for(int j=0;j<i;j++){
		ret.push_back(P(j+1,0));
	}
	ret.push_back(P(i,1));
	ret.push_back(P(i+1,1));
	ret.push_back(P(i+1,0));
	ret.push_back(P(i,0));
	for(int j=i-1;j>=0;j--){
		ret.push_back(P(j,0));
	}
}
void neg(int i){
	for(int j=0;j<i;j++){
		ret.push_back(P(j+1,0));
	}
	ret.push_back(P(i+1,0));
	ret.push_back(P(i+1,1));
	ret.push_back(P(i,1));
	ret.push_back(P(i,0));
	for(int j=i-1;j>=0;j--){
		ret.push_back(P(j,0));
	}
}

vector<P> f(vector<P> vec,int t){
	int cnt[300]={};
	for(int i=0;i<vec.size();i++){
		cnt[vec[i].sc]++;
	}
	int MIN=100;
	int id=-1;
	for(int i=0;i<300;i++){
		if(cnt[i]==0)continue;
		if(MIN>cnt[i]){
			MIN=cnt[i];
			id=i;
		}
	}
	//cerr<<"id="<<id<<endl;
	vector<P> ret;
	for(int i=0;i<vec.size();i++){
		if(vec[i].sc!=id)ret.push_back(vec[i]);
		else {
			if(vec[i].fr==1){
				ret.push_back(P(1,id));
				ret.push_back(P(1,t));
				ret.push_back(P(-1,id));
				ret.push_back(P(-1,t));
			}
			else {
				ret.push_back(P(1,t));
				ret.push_back(P(1,id));
				ret.push_back(P(-1,t));
				ret.push_back(P(-1,id));
			}
		}
	}
	return ret;
}

bool zero(vector<P> vec, int x){
	stack<P> st;
	for(P p: vec){
		if((x>>p.sc)&1){
			if(st.size()==0){
				st.push(p);
				continue;
			}
			P q=st.top();
			if(q.sc==p.sc&&p.fr+q.fr==0)st.pop();
			else st.push(p);
		}
	}
	return st.size()==0;
}

int main(){
	int n;
	string s;
	cin>>n>>s;
	
	int a[300];
	for(int i=0;i<(1<<n);i++)a[i]=s[i]-'0';
	
	bool used[300];
	memset(used,0,sizeof used);
	
	int b[300];
	for(int i=0;i<300;i++)b[i]=1;
	
	for(int x=1;x<(1<<n);x++){
		used[x]=true;
		for(int y=0;y<x;y++){
			if((x&y)==y)if(used[y])used[x]=false;
		}
		for(int y=0;y<(1<<n);y++){
			if((x&y)==x)if(a[y]==1)used[x]=false;
		}
		if(used[x]){
			for(int y=0;y<(1<<n);y++){
				if((x&y)==x)b[y]=0;
			}
		}
	}
	
	bool ok=true;
	for(int i=0;i<(1<<n);i++)ok&=a[i]==b[i];
	if(!ok){
		puts("Impossible");
		return 0;
	}
	vector<P> vv;
	/*for(int x=0;x<(1<<n);x++){
		if(!used[x])continue;
		if(vv.size()==0){
			vv.push_back(P(1,x));
		}
		else{
			vv=f(vv,x);
		}
	}*/
	vector<P> vec[300];
	ret.push_back(P(0,0));
	for(int x=0;x<(1<<n);x++){
		if(!used[x])continue;
		if(zero(vv,x)){
			int cnt=0;
			int c[10];
			for(int i=0;i<n;i++){
				if((x>>i)&1)c[cnt++]=i;
			}
			vec[x].push_back(P(1,c[0]));
			for(int i=1;i<cnt;i++)vec[x]=f(vec[x],c[i]);
			vv.insert(vv.end(),vec[x].begin(),vec[x].end());
		}
	}
	for(P p: vv){
		if(p.fr==1)pos(p.sc);
		else neg(p.sc);
	}
	
	/*vector<P> ret2;
	for(P p: ret){
		if(ret2.size()>=2&&ret2[ret2.size()-2]==p)ret2.pop_back();
		else ret2.push_back(p);
	}
	ret=ret2;*/
	
	assert(ret.size()<=250000);
	
	puts("Possible");
	printf("%d\n",(int)(ret.size())-1);
	for(int i=0;i<ret.size();i++){
		printf("%d %d\n",ret[i].fr,ret[i].sc);
	}
}