代码实现

//poj 1023
//sep9
#include <iostream>
#include <stack>
using namespace std;
int k;
char s[80];
long long n;
 
int main()
{
	int cases;
	scanf("%d",&cases);
	while(cases--){
		scanf("%d%s%lld",&k,s,&n);
		stack<int> ans;	
		int i;
		if(n==0){
			puts("0");
			continue;
		}
		for(i=k-1;i>=0;--i){
			if(n%2==0){
				ans.push(0);
				n/=2;
				continue;
			}
			if(n%2==1){
				ans.push(1);
				if(s[i]=='p'){
					n=n/2;
				}else{
					n=n/2+1;
				}
				continue;
			}
			if(n%2==-1){
				ans.push(1);
				if(s[i]=='p'){
					n=n/2-1;
				}else{
					n=(n+1)/2;
				}		
			} 
		}
		if(!(i==-1&&n==0))
			puts("Impossible");
		else{
			while(!ans.empty()){
				printf("%d",ans.top());
				ans.pop();
			}
			printf("\n");
		}
	}
	return 0;	
}