El rectángulo de Kubrik es una adaptación a dos dimensiones del clásico cubo de Rubik. Se dispone de un rectángulo de 8 casillas, distribuidas en dos filas y cuatro columnas, coloreadas con 8 colores diferentes, que aquí representamos con un número del 1 al 8. Inicialmente, la disposición de los colores en las casillas es la siguiente:

    1    2    3    4
    8    7    6    5

Se pide, a partir de esta disposición inicial, alcanzar una disposición objetivo caracterizada por una configuración diferente del rectángulo. Un ejemplo podría ser la configuración final:

    5    1    8    3
    4    7    6    2

Para ello deberán aplicarse sobre la disposición inicial una serie de transformaciones hasta alcanzar la disposición objetivo. Existen tres tipos de transformaciones, identificadas por las letras A, B y C.

• A: intercambia la fila superior y la fila inferior. El efecto se visualiza en la figura siguiente: de la configuración de la izquierda se pasa a la de la derecha:
  
      1    2    3    4
      8    7    6    5
  
      8    7    6    5
      1    2    3    4
  
  
• B: desplazamiento circular derecho del rectángulo:
  
      1    2    3    4
      8    7    6    5
  
      4    1    2    3
      5    8    7    6
  
  
• C: rotación en sentido horario de los cuatro cuadrados del centro:
  
      1    2    3    4
      8    7    6    5
  
      1    7    2    4
      8    6    3    5
  
  

Concretamente, el programa pide una secuencia mínima de transformaciones que lleve de la configuración inicial a la configuración destino. En caso de haber más de una secuencia mínima, se puede devolver cualquiera de ellas.

Entrada

Residente en el fichero de caracteres "KUBR.DAT": una línea con ocho caracteres entre '1' y '8', sin repetición y separados exactamente por un blanco (no hay ningún otro tipo de caracteres ni al inicio ni al final de la línea), que representan la configuración final, numeradas a partir del vértice superior izquierdo en el sentido del movimiento de las agujas del reloj.

Salida

A guardar en el fichero de caracteres "KUBR.OUT": una línea inicial diciendo la longitud de la secuencia mínima y, a continuación, tantas líneas como transformaciones aplicadas, en el orden de aplicación. No debe aparecer ningún otro tipo de información en la línea. Podéis trabajar con la seguridad de que existe una secuencia de movimientos que llevan de la configuración inicial a la configuración final.

Ejemplo de entrada

5 1 8 3 2 6 7 4

Ejemplo de salida

4
C
A
B
C