wavynumbers
Wavy Numbers
A wavy number is a positive integer that for any digit of its decimal representation, the following condition holds: The digit is either strictly larger than all adjacent digits or strictly smaller than all adjacent digits. For example, numbers \(35270\), \(102\), \(747\), \(20\) and \(3\) are wavy but numbers \(123\), \(1000\), \(2212\), and \(55\) are not.
The task is to find the \(k^{th}\) smallest wavy number \(r\) that is divisible by \(n\), for the given integer values \(n\) and \(k\).
You are to write a program that will find the value of \(r\) if it doesn't exceed \(10^{14}\).
Input format
The only line of input contains two integers \(n\) and \(k\), separated by a single space.
Output format
Output a single integer \(r\) — the answer to the given problem. If such a number does not exist or it is larger than \(10^{14}\), then print "1" (negative one without the quotes) instead.
Limits
\(1 \leq n, k \leq 10^{14}\).
Subtask #

Score

Constraints

1 
11 
\(n = 1\) 
2 
13 
\(n \leq 10000\) 
3 
15 
\(n \leq 300000\) 
4 
61 
No additional constraints 
Samples
Sample Input 1

Sample Output 1

123 4

1845

The values of the first four wavy numbers that are divisible by \(123\) are: \(492\), \(615\), \(738\) and \(1845\).
Sample Input 2

Sample Output 2

100 1

1

Sample Input 3

Sample Output 3

97461 457

1805270103
