$| = 1;

use bigint;

my $base = 10;

sub firstWithDs {
	my $ds = shift;
	my $head = ($ds % ($base-1))+1;
	my $pow = int($ds / ($base-1));
	return $head * $base**$pow - 1;
}

sub nextWithSameDs {
	my $n = shift;
	my $r = 0;
	my $p = 0;
	while (1) {
		my $d = $n % $base;
		if ($d < ($base-1) && $r>0) {
			return ($n+1)*$base**$p + firstWithDs($r-1);
		}
		$n = ($n-$d)/$base;
		$p = $p+1;
		$r = $r + $d;
	}
}

sub ds {
	my $n = shift;
	my $ds = 0;

	while ($n) {
		my $d = $n % $base;
		$ds += $d;
		$n -= $d;
		$n /= $base;
	}

	return $ds;
}

my @countByDs = ();
my @matrix    = (); # ds x n

sub search {
	my $ds = shift;
	my $n = shift;

	if ($matrix[$ds][$n]==0) {
		if ($n==1) {
			$matrix[$ds][$n] = firstWithDs($ds);
		} else {
			$matrix[$ds][$n] = nextWithSameDs(search($ds, $n-1));
		}
	}

	return $matrix[$ds][$n];
}

foreach my $n (1..10_000) {
	my $ds = ds($n);
	my $i = ++$countByDs[$ds];
	print $n, " ", search($i, $ds), "\n";
}