{$I+,Q+,R+,S+}
{$M 65520,0,655360}
program buratinas;

  const PR = 'BURAT.DAT';
        RZ = 'BURAT.REZ';
        MAX_E = 1000; { maksimalus ‚jim— skai‡ius }
        MAX_EIL = 4000; { maksimalus eil‚s dydis }
        MAX_N = 16; { maksimalus lentos dydis }
        DX:  array [1..4] of integer = (1, 0, -1, 0);
        DY:  array [1..4] of integer = (0, -1, 0, 1);
  type langelis = record
                    eil, stu: integer;
                  end;
       ejimai = array [1..MAX_E] of char;
       lenta = array [1..MAX_N, 1..MAX_N] of integer;
       eile = array [1..MAX_EIL] of record
                                      b, k1, k2: langelis;
                                      is: integer;
                                    end;

  { ‘emiau apražyti globalieji kintamieji }
  var n: integer;       { lentos dydis }
      r,                { raktelio koordinat‚s }
      p1, p2: langelis; { abiej— pl‚žik— koordinat‚s }
      ej: ejimai;       { buratino ‚jimai }
      sk: integer;      { j— skai‡ius }
      Q: eile;          { eil‚ }

  {---------------------pagalbin‚s funkcijos-----------------}
  function lygu (lan1, lan2: langelis): boolean;
    { patikrina, ar du langeliai sutampa }
  begin
    lygu := (lan1.eil = lan2.eil) and (lan1.stu = lan2.stu);
  end; { lygu }

  function lentoje (lan: langelis): boolean;
  begin
    lentoje := (lan.eil >= 1) and (lan.eil <= n) and
               (lan.stu >= 1) and (lan.stu <= n);
  end; { lentoje }

  function laisva (lan, k1, k2: langelis): boolean;
  begin
    laisva := not lygu(lan, k1) and not lygu (lan, k2);
  end; { laisva }

  function puolamas (lan, k1, k2: langelis): boolean;
    { patikrina, ar langelis yra puolamas }
    var puola1, puola2, gina_k1_p1, gina_k1_p2, gina_k2_p1,
        gina_k2_p2: boolean;
  begin
    puola1 := lan.eil = p1.eil; puola2 := lan.eil = p2.eil;
    gina_k1_p1 := (k1.eil = lan.eil) and
                  ((p1.stu < k1.stu) and (k1.stu < lan.stu) or
                  (p1.stu > k1.stu) and (k1.stu > lan.stu));
    gina_k1_p2 := (k1.eil = lan.eil) and
                  ((p2.stu < k1.stu) and (k1.stu < lan.stu) or
                  (p2.stu > k1.stu) and (k1.stu > lan.stu));
    gina_k2_p1 := (k2.eil = lan.eil) and
                  ((p1.stu < k2.stu) and (k2.stu < lan.stu) or
                  (p1.stu > k2.stu) and (k2.stu > lan.stu));
    gina_k2_p2 := (k2.eil = lan.eil) and
                  ((p2.stu < k2.stu) and (k2.stu < lan.stu) or
                  (p2.stu > k2.stu) and (k2.stu > lan.stu));
    puolamas := puola1 and not (gina_k1_p1 or gina_k2_p1) or
                puola2 and not (gina_k1_p2 or gina_k2_p2);
  end; { puolamas }

  {-------------------bangos metodas----------------------}
  procedure banga (lan1, lan2, k1, k2: langelis;
                   var len: lenta;
                   var pasiekta: boolean);
    { bangos metodu iž langelio lan1 pasiekia lan2; konteineri— nestumdome }
    var i, j, k: integer;
        rastas_naujas: boolean;
        nau: langelis;
  begin
    { gal b–t tie langeliai sutampa }
    pasiekta := lygu (lan1, lan2);
    if pasiekta then exit;
    for i := 1 to n do
      for j := 1 to n do
        len[i, j] := -1; { langeliai nepasiekti }
    len[lan1.eil, lan1.stu] := 0;
    rastas_naujas := true;
    repeat { kol pasiekiame naujus langelius ir nepasiek‚me iežkomojo }
      rastas_naujas := false;
      for i := 1 to n do
        for j := 1 to n do
          if (len[i, j] <> -1)
           then for k := 1 to 4 do
                  begin
                    nau.eil := i + dx[k]; nau.stu := j + dy[k];
                    if lentoje (nau) and not puolamas(nau, k1, k2) and
                       laisva (nau, k1, k2) and (len[nau.eil, nau.stu] = -1)
                       and not pasiekta
                       then begin
                              len[nau.eil, nau.stu] := len[i, j] + 1;
                              rastas_naujas := true;
                              pasiekta := lygu (nau, lan2);
                              if pasiekta then exit;
                            end;
                  end;
    until not rastas_naujas or pasiekta;
  end; { banga }

  {-----------------proced–ros darbui su eile ----------------}
  procedure itraukti_i_eile (b, k1, k2: langelis; is: integer;
                             var uodega: integer);
    var i: integer;
        rasta: boolean;
        len: lenta;
  begin
    { patikrinsime, ar n‚ra analogižko elemento eil‚je }
    i := 1; rasta := false;
    while not rasta and (i < uodega) do
      begin
        if (lygu(Q[i].k1, k1) and lygu(Q[i].k2, k2) or
                 lygu(Q[i].k2, k1) and lygu(Q[i].k1, k2))
           then banga (Q[i].b, b, k1, k2, len, rasta);
       i := i + 1;
     end;
    if not rasta
       then begin
              uodega := uodega + 1;
              Q[uodega].b := b;
              Q[uodega].k1 := k1;
              Q[uodega].k2 := k2;
              Q[uodega].is := is;
            end;
  end; { Ťtraukti_Ť_eilŠ }

  procedure paimti_is_eiles (galva: integer; var is: integer;
                             var b, k1, k2: langelis);
  begin
    is := Q[galva].is;
    k1 := Q[galva].k1; k2 := Q[galva].k2; b := Q[galva].b;
  end; { paimti_iž_eil‚s }

  {---------------------pagrindin‚ proced–ra ----------------------}
  procedure raktelio_paieska (b, k1, k2: langelis; var uodega: integer);
    var galva, is, i, kont_num: integer;
        len: lenta;
        pasiekta, gali: boolean;
        juda, nejud, lan, bur, buv_lan, buv_juda: langelis;
  begin
    galva := 0; uodega := 0;
    itraukti_i_eile (b,  k1, k2, 0, uodega);
    { gal Buratinas pasieks raktelŤ nestumdydamas konteineri— }
    banga (b, r, k1, k2, len, pasiekta);
    while not pasiekta do
      begin
        galva := galva + 1;
        paimti_is_eiles (galva, is, b, k1, k2);
        for i := 1 to 4 do { abu konteinerius stumiame visomis kryptimis }
          for kont_num := 1 to 2 do
           if not pasiekta then
              begin
                { stumiamas konteineris yra langelyje juda }
                if kont_num = 1 then begin juda := k1; nejud := k2; end
                                else begin juda := k2; nejud := k1; end;
                { konteineris bus perstumtas Ť žŤ langelŤ }
                lan.eil := juda.eil + dx[i];
                lan.stu := juda.stu + dy[i];
                { Buratinas jŤ stums iž žio langelio }
                bur.stu := juda.stu - dy[i];
                bur.eil := juda.eil - dx[i];
                { ar Buratinas gali pasiekti langelŤ iž kurio stums }
                banga (b, bur, k1, k2, len, gali);
                if gali and lentoje (lan) and not puolamas (juda, lan, nejud)
                   and laisva (lan, k1, k2) then
                   begin { stumiama kol sutinkama kli–tis }
                     while lentoje (lan) and not puolamas (juda, lan, nejud)
                           and laisva (lan, k1, k2) do
                       begin
                         buv_lan := lan;
                         buv_juda := juda;
                         juda := lan;
                         lan.eil := juda.eil + dx[i];
                         lan.stu := juda.stu + dy[i];
                       end;
                     lan := buv_lan;
                     juda := buv_juda;
                if kont_num = 1
                   then itraukti_i_eile (juda, lan, k2, galva, uodega)
                   else itraukti_i_eile (juda, k1, lan, galva, uodega);
                { gal iž naujos pad‚ties galima pasiekti raktelŤ }
                if kont_num = 1
                   then banga (juda, r, lan, k2, len, pasiekta)
                   else banga (juda, r, k1, lan, len, pasiekta)
              end;
            end;
      end;
  end; { raktelio_paiežka }

  {----------------Rezultat— gavimas--------------------------}
  procedure rasti_ejimus (lan1, lan2: langelis; len: lenta;
                          var sk: integer; var ej: ejimai);
    { Lentoje bangos metodu suražyti ‚jimai, padedantys iž pirmojo
      langelio pasiekti antr…jŤ; ži proced–ra tuos ‚jimus atbula tvarka
      suražo Ť masyv… sk }
      var i, num: integer;
          rasta: boolean;
          nau: langelis;
  begin
    while not lygu (lan2, lan1) do
      begin
        i := 0;  rasta := false;
        while (i < 4) and not rasta do
          begin
            i := i + 1;
            num := len[lan2.eil, lan2.stu];
            nau.eil := lan2.eil + dx[i]; nau.stu := lan2.stu + dy[i];
            rasta := lentoje(nau) and (len[nau.eil, nau.stu] + 1 = num);
          end;
        sk := sk + 1;
        case i of
         1: ej[sk] := 'A';
         2: ej[sk] := 'D';
         3: ej[sk] := 'V';
         4: ej[sk] := 'K';
        end;
        lan2 := nau;
      end;
  end; { rasti_‚jimus }

  procedure rezultatai (uodega: integer; const Q: eile;
                        var sk: integer; var ej: ejimai);
    { pagal eilŠ suformuojami rezultatai }
    var kiek, i, is, is_n: integer;
        sena, nauja, bur, b, k1, k2, b_n, k1_n, k2_n: langelis;
        len: lenta;
        pasiekta: boolean;
  begin
    sk := 0; { ‚jim— skai‡ius }
    paimti_is_eiles (uodega, is, b, k1, k2);
    banga (b, r, k1, k2, len, pasiekta);
    rasti_ejimus (b, r, len, sk, ej);
    while is <> 0 do
      begin
        paimti_is_eiles (is, is_n, b_n, k1_n, k2_n);
        { pastumiamas konteineris }
        if lygu (k1, k1_n)
           then begin sena := k2; nauja := k2_n; end
           else begin sena := k1; nauja := k1_n; end;
        kiek := abs (sena.eil-nauja.eil) + abs(sena.stu - nauja.stu);
        for i := 1 to kiek do
          begin
            sk := sk + 1;
            if sena.eil < nauja.eil then ej[sk] := 'A'
            else if sena.eil > nauja.eil then ej[sk] := 'V'
            else if sena.stu < nauja.stu then ej[sk] := 'K'
            else ej[sk] := 'D';
         end;
         bur := nauja;
           if sena.eil < nauja.eil
              then bur.eil := bur.eil + 1
           else if sena.eil > nauja.eil then bur.eil := bur.eil - 1
           else if sena.stu < nauja.stu then bur.stu := bur.stu + 1
           else bur.stu := bur.stu - 1;
        { Buratinas paeina Ť reikiam… langelŤ }
        banga (b_n, bur, k1_n, k2_n, len, pasiekta);
        rasti_ejimus (b_n, bur, len, sk, ej);
        is := is_n; b := b_n; k1 := k1_n; k2 := k2_n;
      end;
  end; { rezultatai }

  {--------------duomen— skaitymas bei ražymas--------------}
  procedure skaityti (var n: integer;
                      var b, r, k1, k2, p1, p2: langelis);
    var f: text;
  begin
    assign (f, PR);
    reset (f);
    readln (f, n);
    readln (f, b.eil, b.stu);
    readln (f, r.eil, r.stu);
    readln (f, k1.eil, k1.stu);
    readln (f, k2.eil, k2.stu);
    readln (f, p1.eil, p1.stu);
    readln (f, p2.eil, p2.stu);
    close (f);
  end; { skaityti }

  procedure spausdinti (sk: integer; const ej: ejimai);
    var f: text;
        i: integer;
  begin
    assign (f, RZ);
    rewrite (f);
    writeln (f, sk);
    for i := sk downto 1 do
      write (f, ej[i]);
    close (f);
  end; { spausdinti }

  var b, k1, k2: langelis;
      uodega: integer;
begin
  skaityti (n, b, r, k1, k2, p1, p2);
  raktelio_paieska (b, k1, k2, uodega);
  rezultatai (uodega, Q, sk, ej);
  spausdinti (sk, ej);
end.