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 signed long long ll;

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N,L;
string A;
int ismin[256];


vector<pair<int,int>> construct(int mask) {
	vector<pair<int,int>> V;
	
	int i;
	FOR(i,N) if(mask&(1<<i)) {
		if(__builtin_popcount(mask)==1) {
			V.push_back({i,1});
			V.push_back({i+1,1});
			V.push_back({i+1,0});
			V.push_back({i,0});
		}
		else {
			vector<pair<int,int>> W=construct(mask^(1<<i));
			V.push_back({i,1});
			while(V.back().first+1<W[0].first) {
				V.push_back(V.back());
				V.back().first++;
			}
			FORR(w,W) V.push_back(w);
			V.push_back(W.back());
			V.back().second=1;
			while(V.back().first>i) {
				V.push_back(V.back());
				V.back().first--;
			}
			V.push_back({i,0});
			V.push_back({i+1,0});
			V.push_back({i+1,1});
			reverse(ALL(W));
			while(V.back().first<W[0].first) {
				V.push_back(V.back());
				V.back().first++;
			}
			
			FORR(w,W) V.push_back(w);
			while(V.back().first>i+1) {
				V.push_back(V.back());
				V.back().first--;
			}
			V.push_back({i+1,0});
			V.push_back({i,0});
		}
		break;
	}
	return V;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>A;
	L=1<<N;
	FORR(c,A) c-='0';
	FOR(x,L) FOR(y,L) if((x&y)==y && A[x] && A[y]==0) return _P("Impossible\n");
	FOR(x,L) ismin[x]=A[x]==0;
	FOR(x,L) if(A[x]==0) FOR(y,L) if((x&y)==y && y<x && A[y]==0) ismin[y]=0;
	
	vector<pair<int,int>> W;
	W.push_back({0,0});
	FOR(x,L) if(A[x]==0) {
		vector<pair<int,int>> V=construct(x);
		FOR(i,V[0].first) W.push_back({i,1});
		FORR(v,V) W.push_back(v);
		for(i=V[0].first;i>=0;i--) W.push_back({i,1});
		W.push_back({0,0});
	}
	cout<<"Possible"<<endl;
	cout<<W.size()-1<<endl;
	FORR(w,W) cout<<w.first<<" "<<w.second<<endl;
	/*
	FOR(i,W.size()-1) {
		cout<<i<<" "<<W[i].first<<" "<<W[i].second<<" "<<W[i+1].first<<" "<<W[i+1].second<<endl;
		assert(abs(W[i].first-W[i+1].first)+abs(W[i].second-W[i+1].second)==1);
	}
	*/
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}