Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

Google Inc Está desarrollando una nueva tecnología para recorrer un mapa en diferentes niveles de zoom. Su tecnología asume que la región m se mapea a una región rectangular plana y se divide en sub-regiones rectangulares que representan los niveles de zoom. La tecnología de Google Inc. representa  mapas utilizando la estructura conocida como quad-tree . En un quad-tree , una región rectangular llamada x puede ser dividida a la mitad, tanto horizontalmente como verticalmente resultando en cuatro sub regiones del mismo tamaño. Estas sub regiones se denominan regiones hijo de x , y se llaman xp para la superior izquierda, xq para la superior derecha, xr de abajo y a la derecha y xs para las de abajo a la izquierda, xc representa la concatenación de la cadena x y carácter c = 'p', 'q', 'r' o 's'. Por ejemplo si la región base mapeada se denomina m , las regiones hijas de m son en el sentido del reloj: mp , mq , mr y ms , como se ilustra.

Cada sub región puede ser subdividida. Por ejemplo la región denominada ms puede ser sub dividida en más sub regiones msp , msq , msr y mss, como se ilustra.

La figura muestra el resultado de dividir las sub regiones hijas de msr.

Los nombres de la sub regiones tienen la misma longitud de del nivel de zoom, dado que representan regiones del mismo tamaño. Las sub regiones en el mismo nivel de zoom que comparten un lado común se dicen vecinos.  Todo lo que esta fuera de la región base m no se mapea para cada nivel de zoom todas las sub regiones de m son mapeadas.

La tecnología de mapas Google's le provee al usuario una forma de navegar de una sub región a una sub región vecina en las direcciones arriba, abajo, izquierda y derecha. Su misión es la de ayudar a Google Inc. a encontrar la sub región vecina de una sub región dada. Esto es que dado el nombre de una sub región rectangular usted debe determinar los nombres de sus cuatro vecinos.

Input

La primera línea contiene un entero N( 1 )

Output

Para cada caso de prueba se imprime una línea  que contiene los nombres de las cuatro regiones de una región dada, en el orden:  arriba abajo izquierda y derecha separadas por un espacio. Para vecinos que no están en el mapa se debe escribir .

Sample test(s)