看着没有几个0ms的，难道都是开了map之类的？说了n<16,整形完全存的下，用位操作会快很多
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;

int firstPos[65537];
int nthNum[65537];
int rule[8];
int n, p2, mask, s, m;

int nzy(int q){
	int ans = (q<<1) & mask;
	if(q&m) ans+=1;
	return ans;
}

int nyy(int q){
	int ans = q>>1;
	if(q&1) ans+=m;
	return ans;
}

int getBit(int nn, int k){
	return (nn>>k)%2;
}

int getMin(int q){
	int mn = q;
	for(int i = 0; i < n-1; i++){
		q = nzy(q);
		if(q<mn) mn = q;
	}
	return mn;
}

bool init(){
	if(scanf("%d", &n) != 1) return 0;
	p2 = 1<<n;
	mask = p2-1;
	m = p2>>1;
	for(int i = 0; i <= p2; i++) firstPos[i] = -1;
	char str[19];
	scanf("%s", str);
	int len = strlen(str);
	int sum = 0;
	for(int i = 0; i < len; i++){
		sum <<= 1;
		sum += str[i]-'a';
	}
	//cout << sum << endl;
	int mn = getMin(sum);
	//cout << mn << endl;
	firstPos[mn]=0;
	nthNum[0]=mn;
	for(int i = 0; i < 8; i++){
		scanf("%s", str);
		int idx = ((str[0]-'a')<<2) + ((str[1]-'a')<<1) + (str[2]-'a');
		rule[idx]=str[3]-'a';
	}
	//for(int i = 0; i < 8; i++) cout << rule[i] << " "; cout << endl;
	scanf("%d",&s);
	return 1;
}

int getAns(){
	if(s==0) return nthNum[0];
	int firstRep = -1, lastRep = -1;
	for(int i = 1; i <= s; i++){
		int syc = nthNum[i-1];
		int j1 = nzy(syc), g2 = nyy(nyy(syc));
		int toGet = 0;
		for(int k = n-1; k >= 0; k--){
			int idx = (getBit(g2,k)<<2) + (getBit(syc,k)<<1) + getBit(j1,k);
			toGet <<=1;
			toGet += rule[idx];
		}
		toGet = getMin(toGet);
		if(!(~firstPos[toGet])){
			firstPos[toGet]=i;
			nthNum[i]=toGet;
			if(i==s) return toGet;
		}
		else{
			firstRep = i, lastRep = firstPos[toGet];
			break;
		}
	}
	return nthNum[lastRep+(s-firstRep)%(firstRep-lastRep)];
}

int main() {
	while(init()){
		int ans = getAns();
		for(int k = n-1; k >= 0; k--){
			printf("%c", getBit(ans, k)+'a');
		}
		printf("\n");
	}
	return 0;
}