#!/usr/bin/perl -w

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

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

use strict;
use vars qw($n @pileOfDisk $numMoves $numCalls @powersOfTwo);
use constant INNAME  => "hanoi.in";
use constant OUTNAME => "hanoi.out";
use constant MAX_N   => 10 ** 5;
use constant DEBUG   => 0;
sub println { print @_; print "\n"; }
my $MODULO = 1000000;
$|=1;

sub readInput {
	open(INF, "<", INNAME) or die "Can't open " . INNAME . " for reading";
 	$n = <INF>;
 	chomp $n;
 	$n > MAX_N and die "n too big n=$n, exceeds limit of MAX_N=" . MAX_N;
 	my $pot = 1;
 	for (0..$n) {
		$powersOfTwo[$_] = $pot;
		$pot = (2*$pot) % $MODULO;
	}
 	my @sizes = split(/\s+/, scalar <INF>); # ignored
	foreach my $actPile (0..2) {	
		chomp ($_=<INF>);
		my @pile = map { $_-1 } (split);
		foreach my $disk(@pile) { $pileOfDisk[$disk] = $actPile; }
	}
	close INF;
	$numMoves = 0;
}

# moves disks 0..$maxDisk to $dstPile
sub moveDisks {
	no warnings;
	my ($maxDisk, $dstPile) = @_;
	$numCalls++;
	return if $maxDisk < 0;
	my $srcPile = $pileOfDisk[$maxDisk];
	my $auxPile = 0+1+2 - $srcPile - $dstPile;
	DEBUG and println "moveDisks(", $maxDisk+1,", $dstPile);";
	if ($srcPile == $dstPile) {
		moveDisks($maxDisk-1, $dstPile);	
	} else {
		moveDisks($maxDisk-1, $auxPile); # out of the way
		# now we can directly move $maxDisk (1 move) and then move the 
		# smaller disks (2**$maxDisk - 1) moves --> 2**$maxDisk moves total
		#for (0..$maxDisk) { $pileOfDisk[$_] = $dstPile; }
		#$numMoves += 2** $maxDisk;
		$numMoves = ($numMoves + $powersOfTwo[$maxDisk]) % $MODULO;
	}
}

print scalar localtime, ": reading input\n";
readInput;
println "n = $n";
print scalar localtime, ": done, solving\n";
moveDisks($n-2, $pileOfDisk[$n-1]);
print scalar localtime, ": done\n";
println "$numCalls calls, $numMoves moves";

open(OUTF, ">", OUTNAME) or die "Can't open " . OUTNAME . " for writing";
print(OUTF $pileOfDisk[$n-1]+1, "\n$numMoves\n");
close OUTF;