{
Solution of task MAGIC
-------- -- ---- -----

The following algorithm written in pseudocode generates all configurations
that can be obtained by applying a sequence of basic transformations to
the initial configuration.

  Make the set Generated empty;
  Make the set Disp empty;
  Include the configuration Ini in Disp;
  While Disp is not empty Do Begin
    take an element P out of Disp;
    for all basic transformation C Do Begin
      let Q be the configuration obtained by applying C to P;
      If Q is not in the set Generated Then Begin
        include Q in the set Generated;
        include Q in the set Disp;
      End
    End
  End;

We can stop searching if the configuration Q is the target.
Let us first investigate the implementation of the operations on the set
Generated.
The number of all configurations is 8!=40320. It is too large to store the
configurations in an array. We can overcome this problem by using an
bijective function Rank that maps a configuration into a number in the range
0..8!-1. We can obtain such function by defining Rank(Q) as the number of
configurations that precedes Q according to the lexicographic ordering of the
permutations of the numbers 1..8.

Let us observe that each basic transformation C has a unique inverse in the
sense that for any configuration Q if C transforms Q to P then its inverse
transforms P to Q and conversely, if the inverse of C transforms P to Q then
C transforms Q to P. The inverses of the basic transformations are:
  A: A itself,
  B: single left circular shifting,
  C: single anti-clockwise rotation of the middle four squares.

If the configuration Q is obtained in the algorithm by applying the basic
transformation C to P then there is a sequence of basic transformations that
transforms the initial configuration to Q whose last element is C. If we know
Q and C then we can compute P by applying the inverse of C to Q.
Consider the array Last: Array[0..8!-1] Of Char. We use the array Last for
two purposes. Last[Rank(Q)]=' ' iff the configuration Q has not been
generated. If Q is obtained during the generation by applying C to a
configuration P then Last[Rank(Q)] is set to C. Following the link provided
by the inverse transformation we can compose the whole sequence of basic
transformations for the target configuration T.

    S:='';             (* string S is set to empty      *)
    While T <> Ini Do Begin
      X:=Last[Rank(T)];
      S:=X+S;          (* append X to the left end of S *)
      Apply_1(T,X,P);  (* Apply the inverse of X to T   *)
      T:=P;            (* link to backward              *)
    End (* While *);

We implement the dispenser Disp as a queue, i.e. by first-in first-out policy;
items come out in the order of their insertion.
A simple experiment will show that the maximal length of the sequences
produced by the algorithm is 22.

The queue implementation of the dispenser provides optimal solution in the
sense that for each configuration T the algorithm produces the shortest
sequence of basic transformations.
We prove by induction on the length of the optimal solution.
Let us denote by l(T) the length of the sequence generated by the algorithm
for configuration T.

Suppose that during the execution of the algorithm the queue contains the
configurations T1,...,Tk where T1 is the head. Then the
following two conditions hold:
  1) l(T1)<=...<=l(Tk)
  2) l(Tk)<=l(T1)+1
The proof is by induction on the number of queue operations.
Initially the statement holds because only the initial configuration
is in the queue and l(Ini)=0. If the head T1 is dequeued, then the new head is
T2. But then we have l(Tk)<=l(T1)+1<=l(T2)+1, and the remaining inequalities
are unaffected. Consider the case when T1 is dequeued and the new
configuration Q which is obtained by applying C to T1 is enqueued.
Then l(Q)=l(T1)+1, therefore the inequalities
  l(Tk)<=l(T1)+1=l(Q) and l(Q)=l(T1)+1<=l(T2)+1
hold by 1) and 2).

It follows from the previous statement that if the configurations inserted
into the queue over the course of the algorithm in the order T1,...,Tn
then l(T1)<=...<=l(Tn).

Let T(k) denote the set of all configurations Q that the minimal length of the
sequence of basic transformations that transform Ini to Q is k.  The proof of
the optimality of the algorithm follows by induction on k.

The elements of T(1) are those configurations that can be obtained by applying
the basic transformations to Ini. The statement obviously holds for k=1.
Assume that the statement holds for all l<k. Let Q be a configuration in T(k).
Then there is a configuration P in T(k-1) and a basic transformation C such
that Q can be obtained by applying C to P. By the inductive hypotheses,
l(P)=k-1. P was inserted into the queue when it was generated by the algorithm.
Consider the time when the algorithm dequeues P from the queue and checks
whether Q is already generated. If Q is new then the algorithm
generates Q and hence l(Q)=l(P)+1=k. If Q was already generated then
l(Q)<=l(P)=k-1 by the monotonicity property, which is a contradiction.

}

Program Magic;
Const
  Size=8;     { Size of the sheet }
  M   =40320; { =Size! }
Type
  Trans =Array[1..Size] Of 1..Size;
  Config=Array[1..Size] Of 1..Size;
Const
  BT  :Array['A'..'C'] Of Trans=((8,7,6,5,4,3,2,1), { basic transformations }
                                 (4,1,2,3,6,7,8,5),
                                 (1,7,2,4,5,3,6,8));
  BT_1:Array['A'..'C'] Of Trans=((8,7,6,5,4,3,2,1), { inverses of the basic }
                                 (2,3,4,1,8,5,6,7), { transformations       }
                                 (1,3,6,4,5,7,2,8));
  Ini :Config=(1,2,3,4,5,6,7,8);                { the initial configuration }
Var
  T    :Config;                                  { the target configuration }
  Answer:String;           { the solution sequence of basic transformations }
  Fact :Array[0..Size] Of Longint;              { array of factorial values }
  Last :Array[0..M] Of Char;
               { Last[Rank(T)] is the last character of a sequence of basic }
          { transformations that transforms the initial configuration to T. }
                      { If Last[Rank(T)]=' ' then T has not been generated. }

Procedure ReadInput;
{ Global output variable: T }
  Var InFile:Text;
    i:Word;
  Begin
    Assign(InFile,'input.txt'); Reset(Infile);
    For i:=1 To Size Do Read(Infile,T[i]);
    Close(Infile);
  End { ReadInput };

Procedure ComputeFact;
{ Computes the factorial values }
  Var i:Word;
  Begin
    Fact[1]:=1;Fact[0]:=1;
    For i:=2 To Size Do
      Fact[i]:=i*Fact[i-1];
  End;

Function Rank(Const P:Config): Word;
{ Rank(P) is the number of permutations that precedes P }
{ according to the lexicographic ordering.              }
  { Global input variables: Size, Fact }
  Var Res,l,i,j:Word;
  Begin
    Res:=0;
    For i:=1 To Size Do Begin
      l:=0;              { l is the number of elements of P in positions }
                         { 1..i-1 that are less than P[j]                }
      For j:=1 To i-1 Do
        If P[j]<P[i] Then Inc(l);
      { Keeping fixed the first i-1 elements of P there can be (P[i]-1-l) }
      { numbers that are less than P[i] in position i in permutations.   }
      { The number of permutations Q such that the first i-1 elements    }
      { are the same as in P but Q precedes P in the lexicographic       }
      { ordering is (P[i]-1-l)*Fact[Size-i].                             }
      Res:=Res+(P[i]-1-l)*Fact[Size-i];
    End { For };
    Rank:=Res;
  End { Rank };

Procedure Apply(Const T:Config; X:Char; Var R:Config);
{ R is obtained by applying the basic transformation X }
{ to the configuration T                               }
  Var i:Word;
  Begin
    For i:=1 To Size Do R[i]:=T[BT[X][i]];
  End { Apply };

Procedure Apply_1(Const T:Config; X:Char; Var R:Config);
{ R is obtained by applying the inverse of the basic }
{ transformation X to the configuration T            }
  Var i:Word;
  Begin
    For i:=1 To Size Do R[i]:=T[BT_1[X][i]];
  End {Apply_1};

Function Equal(Const R,T:Config): Boolean;
{ Checks equality of the configurations R and T }
  Var i:Word;
  Begin
    i:=1;
    While (i<=Size) And (R[i]=T[i]) Do Inc(i);
    Equal:= i>Size;
  End { Equal };

Procedure Generate(Const T: Config);
{ Generates a sequence of basic transformations that transforms the     }
{ initial configuration to T. Last[Rank(T)] will be the last element of }
{ the sequence.                                                         }

{ Global input-output variable: Last }
  Const
    Qs=7000;  { Queue size }
  Var
    Queue:Array[0..Qs-1] Of Config;
    NotFound:Boolean;
    Head,Tail:Word; { head and tail of the queue }
    R,S: Config;
    X: Char;

  Procedure InitGener;
  Var i:Word;
  Begin
    For i:=0 To M Do Last[i]:=' '; { initialize }
    Last[0]:='.';                  { 0=Rank(Ini), sentinel }
  End;

  Procedure InitQueue;
  { initialize the queue }
  Begin
    Head:=0; Tail:=1;
    Queue[0]:=Ini;                 { put Ini into the queue }
  End { InitQueue} ;

  Procedure Enqueue(Const Q:Config);
  Begin
    Queue[Tail]:=Q;
    Inc(Tail); If Tail=Qs Then Tail:=0;
  End { Enqueue };

  Procedure Dequeue(Var Q:Config);
  Begin
    Q:=Queue[Head];
    Inc(Head); If Head=Qs Then Head:=0;
  End { Dequeue };

  Function NotMember(Const Q:Config; X:Char):Boolean;
  { Checks membership of Q in the set of generated configurations.          }
  { If it is not generated then marks it as generated by setting the value }
  {  of Last[Rank(Q)] to X.                                                }
  { Global input-output variable: Last }
  Var RankQ:Word;
  Begin
    RankQ:=Rank(Q);
    If Last[RankQ]=' ' Then Begin
      NotMember:=True;
      Last[RankQ]:=X;
    End Else
      NotMember:=False;
  End { NotMember };

  Begin { Generate }
    InitGener;
    InitQueue;
    NotFound:=True;
    While NotFound Do Begin
      Dequeue(R);
      For X:='A' To 'C' Do Begin            { apply all basic }
        Apply(R, X, S);                     { transformations to R }
        If NotMember(S,X) Then Begin        { S is a new configuration }
          If Equal(T,S) Then Begin          { T=R*C decomposition found }
            NotFound:= False;
            Break;                          { exit the loop }
          End;
          Enqueue(S);
        End { If new tr. };
      End { For j };
    End { While };
  End { Generate };

Procedure Compose(Const T: Config; Var S:String);
{ Composes the sequence of basic transformations from the array Last }
{ following the link provided by the inverse transformation.         }
  { Global input variable: Last }
  Var
    RankQ:Word; X:Char;
    P,Q  : Config;
  Begin
    Q:=T;
    RankQ:=Rank(Q);
    S:='';
    While RankQ <> 0 Do Begin { while Q<>Ini                  }
      X:=Last[RankQ];
      S:=X+S;                 { append X to the left end of S }
      Apply_1(Q,X,P);         { Apply the inverse of X to Q   }
      Q:=P;                   { link to backward              }
      RankQ:=Rank(Q);
    End { While };
  End { Compose };

Procedure WriteOut;
 { Global input variable: Answer }
  Var OutFile:Text;
    L,i:Word;
  Begin
    Assign(OutFile,'output.txt'); Rewrite(OutFile);
    L:=Length(Answer);
    WriteLn(OutFile,L);
    For i:=1 To L Do  WriteLn(OutFile,Answer[i]);
    Close(OutFile);
  End { WriteOut };

Begin { Program }
  ReadInput;
  ComputeFact;
  Generate(T);
  Compose(T, Answer);
  WriteOut;
End.

{ Scientific Committee IOI'96 }