$| = 1;

sub binz {
	sprintf "%b", shift;
}

my @matrix = ();

my $antidiagonals = 100;
foreach my $n (1..$antidiagonals) {
	my $k = 0;
	foreach my $m ($n..1_000_000_000) {
		if (index(binz($m), binz($n))>=0) {
			$k++;

			$matrix[$n][$k] = $m;

			if ($k==$antidiagonals+1-$n) {
				last;
			}
		}
	}
}

my $i = 0;
foreach my $d (1..$antidiagonals) {
	foreach my $k (1..$d) {
		my $n = $d+1-$k;
		$i++;
		print "$i $matrix[$n][$k]\n";
	}
}