MCLONUM - Closest Number

no tags 

Consider two n-digit positive decimal integers A and B with no leading zeroes. We need to find the two closest to A n-digit numbers (the first one – greater or equal to A, the other – strictly less than A), with decimal writings containing all the digits of B in some order. For example if A=3022 and B=1232, using B’s digits we can obtain the following 4-digit numbers: 1223, 1232, 1322, 2123, 2132, 2213, 2231, 2312, 2321, 3122, 3212 and 3221. The least number greater or equal to A obtained by B’s digits is 3122, and the biggest one, strictly less then A is 2321. If A=1232 and B=3022, the possible numbers are 2023, 2032, 2203, 2230, 2302, 2320, 3022, 3202 and 3220. The least number greater or equal to A obtained by B’s digits is 2023, and there is no number less than A. Write a program closest to find these “closest to A” numbers for given A and B, or to determine that one of them does not exist.

Input

Two lines are read from the standard input, each of them containing an n-digit positive integer with no leading zeroes, with A read from the first, and B read from the second line (1 ≤ n ≤ 60).

Output

Write to the standard output:

  • Line 1: the least n-digit number with no leading zeroes, not less than A, containing all the digits of B in some order. If such number does not exist, the output should be 0.
  • Line 2: the biggest n-digit number with no leading zeroes, less than A, containing all the digits of B in some order. If such number does not exist, the output should be 0.

Sample

Input:
3075
6604
3000203
4562454

Output:
4066
0
4244556
2655444
Problem for kid - Please, think like kid.


Added by:psetter
Date:2009-02-18
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:BOI For Kid 08