Word

Dr. R. E. Wright’s class was studying modified L-Systems. Let us explain necessary details. As a model let us have words of length n over a two letter alphabet {a,b} The words are cyclic, this means we can write one word in any of n forms we receive by cyclic shift, whereby the first and the last letters in the word are considered to be neighbours.

Rewriting rules rewrite a letter at a position i, depending on letters at the positions i – 2, i, i+1. We rewrite all letters of the word in one step. When we have a given starting word and a set of rewriting rules a natural question is: how does the word look after s rewriting steps?

Help Dr. R. E. Wright and write a program which solves this task.

Input 

There are several blocks in the input file, each describing one system. There is an integer number n, 2 < n < 16 the length of the input word in the first line. There is a word in the next line. The word contains only lowercase letters a and b. There are four characters c₁c₂c₃c₄ in the next eight lines. Each quadruple represents one rewriting rule with the following meaning: when the letter at the position i – 2 is c₁ and the letter at the position i is c₂ and the letter at the position i + 1 is c₃ then the letter at the position i after rewriting will be c₄. Rewriting rules are correct and complete. There is an integer number s, 0

Output 

There is one line corresponding to each block of the input file. The line contains a word which we receive after s rewriting steps from the corresponding starting word using given rewriting rules. As we mentioned above, the word can be written in any of n cyclic shifted forms. The output file contains the lexicographically smallest word, assuming that a < b.

Sample Input 

5
aaaaa
aaab
aabb
abab
abbb
baab
babb
bbab
bbbb
1

Sample Output 

bbbbb

C Code

#include<iostream.h>
#include<vector>
#include<vector>
#include<algorithm>
#include<map>

using namespace std;

int Trans[100];

vector<string>V;
vector<string>R;

map<string,int>M;
string ini, rules;
int N, Ind;

int Gen() {
	string temp = "";
	int i, a, b, c, d, ind, v;
	Ind = 0;
	V.push_back("");
	while(1) {
		temp = "";
		for(i = 0; i<N; i++) {
			ind = (i - 2 + N) % N;
			a = ini[ind] - 'a';
			b = ini[i] - 'a';
			c = ini[(i+1) % N] - 'a';
			v = a*4 + b*2 + c;
			temp += Trans[v] + 'a';
		}
		if(M[temp]) {
			return M[temp];
			break;
		}
		M[temp] = ++Ind;
		ini = temp;
		V.push_back(temp);
	}
}


void Cal(int n) {
	int s, i, d, id, k;
	string a, b;
	k = Gen();
	if(n < k) {
		a = V[n];
	}
	else {
		s = V.size() - 1;
		d = s - k + 1;
		n -= k;
		n %= d;
		a = V[k + n];
	}
	for(i = 0; i<N; i++) {
		id = i;
		b = "";
		s = 0;
		while(s++ <N) {
			b += a[id];
			id++;
			id %= N;
		}
		R.push_back(b);
	}
	sort(R.begin(),R.end());
	cout<<R[0]<<endl;
}

void Free() {
	M.clear();
	V.clear();
	R.clear();
}

void main() {
	int n, a, b, c, d, v;
	//freopen("c:\\h.txt","r",stdin);
	//freopen("c:\\out.txt","w",stdout);
	while(cin>>N) {
		cin>>ini;
		n = 8;
		while(n--) {
			cin>>rules;
			a = rules[0] - 'a';
			b = rules[1] - 'a';
			c = rules[2] - 'a';
			d = rules[3] - 'a';
			v = a*4 + b*2 + c;
			Trans[v] = d;
		}
		cin>>n;
		if(n == 0) {
			cout<<ini<<endl;
			continue;
		}
		Cal(n);
		Free();
	}
}