#!/usr/bin/perl -w

use strict;

sub r2g {
    my $lower  = shift;
    my $upper  = shift;
    my $maxlen = length($upper);
    $maxlen = length($lower) if ( length($lower) > $maxlen );
    my @globs;
    my $format = "%0${maxlen}d";
    my $maxn   = $lower;

    # Take care of two fringe cases
    return [ sprintf( $format, $maxn ) ] if ( $maxn == $upper );
    return [ '?' x $maxlen ]
      if ( ( $maxn == 0 ) && ( $upper == '9' x $maxlen ) );
  PATTERN:

    # $maxn is the least number in the range $lower through $upper
    # that isn't already matched by some glob pattern.
    # We can only put a (non-trivial) glob pattern in a position
    # if all the positions to the right are already globbed with '?'.
    # The largest number matched by such a glob ends with 1 or more 9's.
    while ( $maxn <= $upper ) {
        for ( my $i = $maxlen - 1 ; $i >= 0 ; --$i ) {
            my $pattern = $maxn = sprintf( $format, $maxn );
            for ( my $j = $i + 1 ; $j < $maxlen ; ++$j ) {
                substr( $pattern, $j, 1 ) = '?';
            }
            my $c = substr( $maxn, $i, 1 );
            if ( $c ne '0' ) {

                # We cannot glob further left
                # See if we can glob starting here
                foreach my $d ( reverse( $c .. '9' ) ) {
                    substr( $maxn, $i, 1 ) = $d;
                    if ( $maxn <= $upper ) {
                        substr( $pattern, $i, 1 ) =
                          ( $d eq $c ) ? $d : "[$c-$d]";
                        substr( $maxn, $i, 1 ) = $d;
                        push( @globs, $pattern );
                        ++$maxn;
                        next PATTERN;
                    }
                }
            }
            else {

                # We can glob with a ? here if replacing the digit
                # with a 9 still remains less than or equal to $upper
                foreach my $d ( reverse( '0' .. '9' ) ) {
                    substr( $maxn, $i, 1 ) = $d;
                    if ( $maxn <= $upper ) {
                        if ( $d ne '9' ) {

                            # Couldn't do a ? match.
                            # Glob what we can, increment $maxn
                            # and look for a new pattern
                            substr( $pattern, $i, 1 ) =
                              ( $d eq '0' ) ? '0' : "[0-$d]";
                            push( @globs, $pattern );
                            ++$maxn;
                            next PATTERN;
                        }
                        last PATTERN if ( $i == 0 );
                        last;
                    }
                }
            }
        }
    }
    return \@globs;
}

# my $g = r2g("0123", "1243");
# print("@$g\n");
# $g = r2g("0000", "1243");
# print("@$g\n");
# $g = r2g("0001", "9999");
# print("@$g\n");
# $g = r2g("0000", "9999");
# print("@$g\n");
# $g = r2g("0000", "0999");
# print("@$g\n");
# $g = r2g("9000", "9999");
# print("@$g\n");

while ( my $line = <> ) {
    if ( $line =~ /([0-9]+)[^0-9]+([0-9]+)/ ) {
        my $g = r2g( $1, $2 );
        print("$1-$2: @$g\n");
    }
}