$| = 1;

use bigint;

my $max = 100_000;

my $base = 10;
my @dx = (+1,  0, -1,  0);
my @dy = ( 0, -1,  0, +1);
my $direction = 0;
my $directions = scalar(@dx);
my %seen = ();
my %lattice = ();
my %direction = ();
my $x = 0;
my $y = 0;
my $minx = 0;
my $maxx = 0;
my $miny = 0;
my $maxy = 0;

sub getKey {
	my $pos = shift;
	my $xx = $x + $pos * $dx[$direction];
	my $yy = $y + $pos * $dy[$direction];
	return "$xx,$yy";
}

sub hasDigit {
	my $pos = shift;
	my $key = getKey($pos);
	return exists $lattice{$key};
}

sub getDigit {
	my $pos = shift;
	my $key = getKey($pos);
	return $lattice{$key};
}

sub setDigit {
	my $pos = shift;
	my $digit = shift;
	my $key = getKey($pos);
	if (exists $lattice{$key}) {
		die if $lattice{$key} != $digit;
	} else {
		$lattice{$key} = $digit;
		$direction{$key} = $direction;
	}
}

sub walk {
	my $pos = shift;

	$x += $pos * $dx[$direction];
	$y += $pos * $dy[$direction];

	if ($minx > $x) {
		$minx = $x;
	}
	if ($maxx < $x) {
		$maxx = $x;
	}
	if ($miny > $y) {
		$miny = $y;
	}
	if ($maxy < $y) {
		$maxy = $y;
	}
}

sub turn {
	$direction = ($direction + 1) % $directions;
}

sub other {
	my @digits = ();
	my @occupied = ();
	my $pow = 0;

	while (1) {
		my $pos = scalar(@digits);

		if (hasDigit($pos)) {
			push @digits => getDigit($pos);
			push @occupied => 1;
		} else {
			push @digits => 0;
			push @occupied => 0;
			$pow++;
		}

		if ($occupied[$pos] && $digits[$pos]==0) {
			# leading zero
		} else {
			my $min = $occupied[$pos] ? 0 : ($base ** ($pow-1));
			my $max = ($base ** $pow) - 1;

			foreach my $can ($min..$max) {
				my $rem = $can;
				my $a = 0;
				foreach (0..$pos) {
					if (not $occupied[$_]) {
						$digits[$_] = $rem % $base;
						$rem = ($rem - $digits[$_]) / $base;
					}
					$a = $a + $digits[$_] * ($base**$_);
				}

				if (not exists $seen{$a}) {
					$seen{$a} = 1;
					foreach (0..$pos) {
						setDigit($_, $digits[$_]);
					}
					walk($pos+1);
					turn();
					return $a;
				}
			}
		}
	}
}

foreach my $n (1..$max) {
	my $a = other();
	print "$n $a\n";
}