#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>

int debug = 0;

//
//  Algorithm description:
//
//  1. Compute one step and "normalize" - find the lowest representation
//     of the resulting word.
//
//  2. See if we haven't got the word yet. If we haven't, go to step 1.
//
//  3. So we know after what step the sequence begun to be periodic
//     (let's call that number PP) and the (minimal) periode (let's
//     call it P).
//
//     So we have this sequence
//
//      step #       word after that step
//        1               w(1)
//        2               w(2)
//        .                .
//        .                .
//        .                .
//        PP              w(PP)
//        .                .
//        .                .
//        .                .
//        PP+P-1          w(PP+P-1)
//        PP+P            w(PP)
//        .                .
//        .                .
//        PP+2P-1         w(PP+P-1)
//        PP+2P           w(PP)
//        .                .
//        .                .
//        .                .
//
//
//  The word after step S is thus:
//
//      w(S) = w(S)      if S < PP + P
//      w(S) = w(S-P)    if S >= PP + P    i.e. w(S) = w((S-PP)%P + PP)
//
//
//  "See if haven't got the word yet" is realized as follows.
//  For each possible word we remember the step after which we
//  got that word (if we got it yet). Step 0 is ignored - it is treated
//  as a special case.
//
//  This is done in the array "when" -----> when [x] = y means:
//
//      after y-th step (steps are numbered 1, 2, ...)
//      we got the word "x"
//
//  x should be from 0 to 32767 (15-bit numbers), though
//  the canonical form is from the numbers 0, 1, ... 16383 and 32767.
//  So the array with 16384+1 = 16385 field is sufficient.
//
//  y is from 1 onwards. 0 means we didn't got the word x yet.
//  because we have only 16385 different values for x, y will certainly
//  be less or equal than 16385. So 16-bit integer for the "when"
//  array is OK.
//
//  so when[0..16383] corresponds to x = 0..16383
//  and when[16384] corresponds to x = 32767.
//
//  Note: 16384 is in the case of word length = 15. Generally the
//  word length is "wordLength" and when table has
//
//     whenTableLength = 2^(wordLength-1) + 1
//
//  entries.

typedef unsigned int uint16;		// we use this for "word"

int when [16385];
int whenTableLength;
uint16 maxWord;			// word consisting of all 1's
int wordLength;			// length of the word
uint16 MSB;			// mask of the most significant bit

char aWord [16];		// original word (alphanumeric)
uint16 origWord;		// original word (numeric)
uint16 actWord;			// actual word
char rules [9];			// 8 rules
long dist;
int step;

void InitTable (void)
{
	for (int i = 0; i < whenTableLength; i++)
	  when [i] = 0;
}

void output (FILE *fout, char *s)
{
	fprintf (fout, "%s\n", s);
}


int Get (uint16 w)
{
	if (w == maxWord)
	  return when [whenTableLength-1];
	else
	  return when [w];
}

void Put (uint16 w, int s)
{
	if (w == maxWord)
	  when [whenTableLength-1] = s;
	else
	  when [w] = s;
}

uint16 AToN (char *s)	// first character = most significant bit
{
	uint16 result = 0;
	while (*s)
	  result = result*2 + (*(s++) == 'a' ? 0 : 1);
	return result;
}

char *NToA (uint16 w)
{
	static char buffer [16];
	int index = wordLength;
	buffer [index] = 0;
	while (index > 0)
	{
	  index--;
	  buffer [index] = (w % 2) ? 'b' : 'a';
	  w = w / 2;
	}
	return buffer;
}

uint16 OneStep (uint16 w)
{
	char *oldw, neww [16];
	int i;
	oldw = NToA (w);
	for (i=0; i<wordLength; i++)
	{
	  int index = (oldw [(i+wordLength-2)%wordLength] - 'a') * 4 +
		      (oldw [i] - 'a') * 2 +
		      (oldw [(i+1)%wordLength] - 'a');
	  neww[i] = rules [index];
	}
	neww[i] = 0;
	return AToN (neww);
}

uint16 Normalize (uint16 w)
{
	uint16 min = w;
	int i;
	for (i=0; i<wordLength; i++)
	{
	  w = ((w<<1)&maxWord) + ((w&MSB) >> (wordLength-1));
	  if (w < min)
	    min = w;
	}
	return min;
}

int main ()
{
	FILE *fin = stdin;
	FILE *fout = stdout;
	int i;

	for (;;)
	{
	  if (fscanf (fin, "%d", &wordLength) != 1)
	    break;
	  fscanf (fin, "%s", aWord);
	  if (debug)
	    printf ("%d: %s\n", wordLength, aWord);

	  assert (wordLength > 2 && wordLength < 16);
	  assert (strlen (aWord) == wordLength);

	  // let's scan RULEZ
	  // fscanf (fin, "%s", rules);

	  memset (rules, 0, 8);

	  for (i=0; i<8; i++)
	  {
	    char rul[10];
	    int index;
	    fscanf (fin, "%s", rul);
	    index = (rul[0] - 'a') * 4 + (rul[1] - 'a')*2 + (rul[2]-'a');
	    assert (rules[index] == 0);
	    rules [index] = rul[3];
	  }

	  for (i=0; i<8; i++)
	    assert (rules[i] == 'a' || rules[i] == 'b');

	  // distance (s)
	  fscanf (fin, "%ld", &dist);

	  //wordLength = strlen (aWord);
	  MSB = 1 << (wordLength-1);
	  maxWord = ((unsigned int) 1 << wordLength) - 1;
	  whenTableLength = MSB + 1;

	  InitTable ();

	  origWord = Normalize (AToN (aWord));

	  if (dist == 0)
	  {
	    output (fout, NToA (origWord));
	    continue;
	  }

	  actWord = origWord;
	  step = 0;
	  for (;;)
	  {
	    // do the step
	    step++;
	    actWord = Normalize (OneStep (actWord));

	    // haven't we reached the destination (by chance) ?
	    if (step == dist)
	    {
	      output (fout, NToA (actWord));
	      break;
	    }

	    // look into the table
	    int tmp = Get (actWord);
	    if (tmp == 0)		// we haven't been here yet
	      Put (actWord, step);	// so make a note there
	    else			// oh a CYCLE, cool!
	    {
	      int pp = tmp;	           // pre-period
	      int p = step - pp;	   // period
	      int nd = ((dist-pp)%p)+pp;  // "normalized" distance

	      // let's find the word with that distance from beginning

	      for (i = 0; i < whenTableLength; i++)
		if (when[i] == nd)
		  break;
	      if (i == whenTableLength)
	      {
		printf ("Internal error -- cannot find the word.\n");
		exit (5);
	      }
	      if (i == whenTableLength-1)
		i = maxWord;

	      output (fout, NToA (i));
	      break;
	    }
	  } // inner loop
	} // outer loop

	fclose (fin);
	fclose (fout);
	return 0;
}