/*

Twofive (IOI 2001)
Copyright (C) 2002 Paolo Boldi and Sebastiano Vigna

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA


(Come per tutti i problemi del 2001, è utile leggere il libretto distribuito
dagli organizzatori, e disponibile nella sezione "Materiale didattico" della
home page http://ioi.dsi.unimi.it/.)


La soluzione di questo problema è molto intricata. Si basa su una tecnica di
programmazione dinamica che sfrutta delle proprietà combinatoriali (quantomeno
oscure) del problema.

Il problema è fatto in modo che sia pressoché impossibile ottenere risultati
ragionevoli, se non con questa tecnica (il tempo a disposizione era dell'ordine
dei centesimi di secondo).



*/

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

#define NUMEROLETTERE 25
#define MAXSCHEMA	6*6*6*6*6

typedef int schema;
typedef long int lexnum;

lexnum lex[MAXSCHEMA];

/* NOTA. Uno schema si può rappresentare come segue: indichiamo con
   a[4],a[3],...,a[0] il numero di posizioni comprese nello schema
   sulla riga 4,3,2,1,0. Leggiamo a[4]a[3]a[2]a[1]a[0] come un numero
   in base 6. Per esempio, considerate il seguente schema:
   
      XXXX
      XXX
      XXX
      X
     
   Esso corrisponde al numero 01334 in base 6, cioè al numero 346 in
   base 10. Lo schema vuoto è lo 0, lo schema pieno (55555) è 
   il 7775 (cioè MAXSCHEMA-1).
*/

/* Sia s uno schema, e supponiamo che si possa aumentare in h modi
   possibili. Invocando questa funzione con i=0,...,h-1, si ottiene:
   * in r,c la posizione (riga/colonna) dell'i-esimo aumento (in
     ordine crescente di riga)
   * in sn il nuovo schema ottenuto
   * la funzione restituisce 1.
   Invocando la funzione con i>=h, il risultato è 0 (i valori contenuti
   alla fine in r,c,sn non sono attendibili).
*/

int aumenta( schema s, int i, int *r, int *c, schema *sn ) {
	int found = 0;  /* Quanti aumenti sono già stati trovati */
	int incre = 1;  /* Di quanto si deve incrementare lo schema s
		           se si vuole aggiungere una posizione sulla
		           riga corrente */
	int prev = 5;   /* Lunghezza riga precedente */
	int curr;       /* Lunghezza riga corrente */
	int origs = s; 	/* Valore originale di s */
	for ( *r = 0; *r < 5; (*r)++ ) {
		curr = s % 6;
		if ( curr < prev ) {
			if ( found == i ) {
				*c = curr;
				*sn = origs + incre;
				return 1;
			}
			found++;
		}
		prev = curr;
		incre *= 6;
		s /= 6;
	}
	return 0;
}

/* Questi due vettori rappresentano i vincoli correnti.  Se valgono -1, per
quella lettera non ci sono vincoli. */

int riga[NUMEROLETTERE], colonna[NUMEROLETTERE];

/* Lo scopo di questa funzione è riempire l'array lex[]. Ricordiamo che lex[s]
contiene il numero di modi in cui disporre le restanti lettere, posto che le
prime lettere dell'alfabeto siano già state disposte nello schema s rispettando
i vincoli correnti. La funzione prende in ingresso uno schema s e, per
comodità, il numero di lettere k già piazzate (k sarà sempre uguale alla
cardinalità di s; cioè, s è composto da k posizioni).  La funzione restituisce
lex[s]. */


lexnum llex( schema s, int k ) {
	lexnum tot, t;
	int i, r, c;
	schema sn;
	
	if ( lex[s] >= 0 ) return lex[s];
	tot = i = 0;
	while ( aumenta( s, i++, &r, &c, &sn ) )
		if (riga[k] < 0 || riga[k] == r && colonna[k] == c)
			tot += llex( sn, k+1 );

	return lex[s] = tot;
}

/* Restituisce in res (che deve contenere spazio per 25 caratteri + fine
stringa) la parola di indice n. */

void trovaparola( lexnum n, char *res ) {	
	int i, j, k, ultimo;
	lexnum pos = 0;

	for(i=0; i<NUMEROLETTERE; i++) riga[i] = colonna[i] = -1;

	for(i=0; i<NUMEROLETTERE; i++) {
		j = 0;

		/* Proviamo a calcolare quante parole completano il prefisso
		corrente. Ogni volta che otteniamo un numero maggiore di pos torniamo
		indietro di una lettera e proviamo con la successiva. */

		while( pos < n ) {
			if (riga[j] < 0) {
				riga[j] = i / 5;
				colonna[j] = i % 5;
				for(k=0; k<MAXSCHEMA-1; k++) lex[k] = -1;
				pos += (ultimo = llex( 0, 0 ));
				riga[j] = -1;
			}
			j++;
		}
		riga[--j] = i / 5;
		colonna[j] = i % 5;
		res[i] = j+'A';
		pos -= ultimo;
	}

	res[NUMEROLETTERE] = 0;
}

/* Calcola e restituisce l'indice della stringa str. */

lexnum trovaindice( char *str ) {
	int i, j, k;
	lexnum pos = 0;

	for(i=0; i<NUMEROLETTERE; i++) riga[i] = colonna[i] = -1;
	for(i=0; i<NUMEROLETTERE; i++) str[i] -= 'A';

	/* Per ogni possibile posizione i, sommiamo il numero di parole che
	cominciano come la parola data fino alla posizione i-1, e che nella
	posizione i hanno una lettera lessicograficamente minore di str[i]. */

	for(i=0; i<NUMEROLETTERE; i++) {
		for(j=0; j<str[i]; j++) {
			if (riga[j] < 0) {
				riga[j] = i / 5;
				colonna[j] = i % 5;
				for(k=0; k<MAXSCHEMA-1; k++) lex[k] = -1;
				pos += llex( 0, 0 );
				riga[j] = -1;
			}
		}
		riga[str[i]] = i / 5;
		colonna[str[i]] = i % 5;
	}

	return pos;
}

/* Legge da stdin, scrive su stdout */

int main() {
	char res[26];
	lexnum i;
	char c;
	
	lex[MAXSCHEMA-1] = 1;
	
	scanf( "%c ", &c );
	if ( c == 'W' ) {
		fgets( res, 26, stdin );
		printf( "%ld\n", trovaindice( res ) + 1 );
	} else {
		scanf( "%lu", &i );
		trovaparola( i, res );
		printf( "%s\n", res );
	}
	
	return 0;
}