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}\).
The only line of input contains two integers \(n\) and \(k\), separated by a single space.
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.
| Subtask # | Score | Constraints |
|---|---|---|
| 1 | 11 | \(n = 1\) |
| 2 | 13 | \(n \leq 10000\) |
| 3 | 15 | \(n \leq 300000\) |
| 4 | 61 | No additional constraints |
| 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
|