program hanoi;

{
 author: tobias thierer - ceoi@tobias-thierer.de

 towers of hanoi

 Linear-time solution with hard-wired modulo. No need for bigints, thus
 none used.

 NOTE: piles and disks are counted beginning with 1 in this program
}

const MAX_N    = 100000; { 10^5 }
      IN_NAME  = 'hanoi.in';
      OUT_NAME = 'hanoi.out';
      MODULO   = 1000000;
      DEBUG    = false;

var n, numMoves : Longint;
    powersOfTwo : array[0..MAX_N] of Longint;
    pileOfDisk  : array[1..MAX_N] of Longint;
    numCalls    : Longint;
    outf        : Text;

{------------------------------------------------------------------------}

procedure readInput;
var inf: Text;
    pileSize   : array[1..3] of Longint;
    pile, disk :  Longint;
    pot, i     : Longint;
begin
    assign(inf, IN_NAME);
    reset(inf);
    readln(inf, n);
    if debug then writeln(n);
    pot := 1;
    for i:=0 to n do begin
        powersOfTwo[i] := pot;
        pot := (2*pot) mod MODULO;
    end;
    for pile := 1 to 3 do read(inf, pileSize[pile]);
    readln(inf);
    for pile := 1 to 3 do begin
        for i:=1 to pileSize[pile] do begin
            read(inf, disk);
            pileOfDisk[disk] := pile;
        end;
        readln(inf);
    end;
    close(inf);
    numMoves := 0;
    numCalls := 0;
end; { procedure readInput }

{ move disks 0..maxDisk to dstPile }
procedure moveDisks(maxDisk: Longint; dstPile: Longint);
var srcPile, auxPile : Longint;
begin
    inc(numCalls);
    if (maxDisk > 0) then begin
        srcPile := pileOfDisk[maxDisk];
        auxPile := 1+2+3 - srcPile - dstPile;
        if DEBUG then writeln('moveDisks(', maxDisk, ',', dstPile, ');');
        if (srcPile = dstPile)
         then begin
            moveDisks(maxDisk-1, dstPile);
         end
         else begin
            moveDisks(maxDisk-1, auxPile); { now we can directly move
                 $maxDisk (1 move) and then move the  smaller disks
                 (2^(maxDisk-1) - 1) moves --> 2^(maxDisk-1) moves total }
            { for disk := 1 to maxDisk do pileOfDisk[disk]:=dstPile }
            numMoves := (numMoves + powersOfTwo[maxDisk-1]) mod MODULO;
         end;
    end;
end; { procedure moveDisks }

begin { main }
    readInput;
    moveDisks(n-1, pileOfDisk[n]);
    if DEBUG
     then writeln(numCalls, ' calls, ', numMoves, ' moves');
    assign(outf, OUT_NAME);
    rewrite(outf);
    writeln(outf, pileOfDisk[n]);
    writeln(outf, numMoves);
    close(outf);
end. { main }