依据：
1. n位长度的串表达2^n种值
    e.g. 2位np 能表达 0, 1, -2, -1这4个值
2.这2^n个值是连续变化的
    e.g. 2位np 能表达的值（0, 1, -2, -1）一定在[-2, 1]中， 且填满这个区间
3.基于上述两点，在表达范围内的值一定有唯一表达，不再范围内的值一定无法表达。

#include <cstdio>
#include <cstring>
#define MAXN (65)
#define min(a,b) (((a)<(b))?(a):(b))
#define max(a,b) (((a)>(b))?(a):(b))
#define abs(x) (((x)>0)?(x):(-(x)))

using namespace std;

int n;
long long v;
struct Digit{
    unsigned long long v, mx, mi; //v记录该位的值，mx为从0位开始到该位能表达的上限，mi为下限
    //都用unsigned记录，因为v的符号由s决定，mx只能是非负数，mi只能是非正数
    char s; //记录该位的符号
}ds[MAXN];
int res[MAXN];


int main(){
    char str[MAXN];
    int tot;
    scanf("%d", &tot);
    while(tot--){
        scanf("%d%s%lld", &n, str, &v);
        memset(ds, 0, sizeof(ds));
        for(int i = 0; i < n; i++){//按定义获得每一位的v， mx, mi
            ds[i].s = str[n - i - 1];
            ds[i].v = 1LL<<i;
            if(i == 0){
                if(ds[i].s == 'p') ds[i].mx = ds[i].v;
                else ds[i].mi = ds[i].v;
                continue;
            }
            ds[i].mx = ds[i - 1].mx;
            ds[i].mi = ds[i - 1].mi;
            if(ds[i].s == 'p') ds[i].mx += ds[i].v;
            else ds[i].mi += ds[i].v;
        }
        //如何要表达的值不在表示范围内，则一定无法表达
        if((v > 0 && ds[n - 1].mx < v) || (v < 0 && ds[n - 1].mi < abs(v))){
            printf("Impossible\n");
            continue;
        }

        //在范围内，一定有唯一表达
        //从最高位开始，当第i位无法表达单前值时，i + 1位一定被设置为1，因此选中i+1,并更新当前值
        memset(res, 0, sizeof(res));
        int idx = n - 1;
        while(v){
            if(v > 0) for(; idx >= 0; idx--) if(ds[idx].mx < v) break;
            else for(; idx >= 0; idx--) if(ds[idx].mi < abs(v)) break;
            idx++;
            res[idx] = 1;
            if(ds[idx].s == 'p') v -= ds[idx].v;
            else v += ds[idx].v;
        }
        for(int i = n - 1; i >= 0; i--) printf("%d", res[i]);
        printf("\n");
    }
    return 0;
}