Problem: A wavy number is such positive integer that for any digit of its decimal representation except for the first one and the last one following condition holds: the digit is either strictly larger than both its adjacent digits or strictly less than both its adjacent digits. For example, numbers 35270, 102, 747, 20 and 3 are wavy and numbers 123, 1000 and 2212 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 1014.

Input

The only line of input contains two integers n and k, separated by a single space (1 ≤ n, k ≤ 1014). 

Output

Your task is to output the only integer r — the answer to the given problem. If such number does not exist or it is larger than 1014, then print "-1" (minus one without the quotes) instead.

Examples

Input

123 4


Output

1845


Input

100 1


Output

-1


Input

97461 457


Output

1805270103

Note

The values of the first four wavy numbers that are divisible by n for the first sample are: 492, 615, 738 and 1845.

Solution (in JAVA):

Solution:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;
import java.util.ArrayList;

public class E {
    BufferedReader br;
    StringTokenizer in;
    PrintWriter out;
    long n,k;
    int pos = 0;
    int pindex = 0;
    int [] numbers = new int[830169];
    ArrayList<Integer> powerSevenIncreasing = new ArrayList<Integer>();
    ArrayList<Integer> powerSevenDecreasing = new ArrayList<Integer>();
    ArrayList<Integer> powerSix = new ArrayList<Integer>(); 
    int[] powerEight = new int[4195557];
    
    public String nextToken() throws IOException {
        while (in == null || !in.hasMoreTokens()) {
            in = new StringTokenizer(br.readLine());
        }

        return in.nextToken();
    }

    public int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    public long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }

    public double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }
    
    public void solve() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(System.out);
        
        n = nextLong();
        k = nextLong(); 

        if(n >= 10000000) {
            long x = n;
            while(n < 100000000000000L) {
                boolean wavy = wavy(n);
                if(wavy && k == 1) {
                    out.println(n);
                    out.close();
                    return;
                }
                else
                    if(wavy)
                        k--;
                
                n += x;
            }
            out.println(-1);
            out.close();
            return;
        }
        
        int num = (int)n;
        
        for(int i = 1 ; i <= 9 ; i++)
            numbers[pos++] = i;
        
        for(int length = 2 ; length <= 8 ; length++) {
            for(int i = 1 ; i <= 9 ; i++) {
                generateWavy(i,i,true,1,length,true);
                generateWavy(i,i,false,1,length,false);
            }
        }
        
       modComparator m = new modComparator(num);
       
       Collections.sort(powerSevenIncreasing,m);
       Collections.sort(powerSevenDecreasing,m);
       Collections.sort(powerSix,m);
       
       Arrays.sort(numbers);
       Arrays.sort(powerEight);
       
       
       int [] valsIncreasing = new int[powerSevenIncreasing.size()];
       
       for(int i = 0 ; i < valsIncreasing.length ; i++)
           valsIncreasing[i] = powerSevenIncreasing.get(i);
       
       int [] modsIncreasing = new int[powerSevenIncreasing.size()];
       
       for(int i = 0 ; i < powerSevenIncreasing.size() ; i++) {
           modsIncreasing[i] = powerSevenIncreasing.get(i) % num; 
       }
       
       int [] valsDecreasing = new int[powerSevenDecreasing.size()];
       
       for(int i = 0 ; i < valsDecreasing.length ; i++)
           valsDecreasing[i] = powerSevenDecreasing.get(i);
       
       int [] modsDecreasing = new int[powerSevenDecreasing.size()];
       
       for(int i = 0 ; i < powerSevenDecreasing.size() ; i++) {
           modsDecreasing[i] = powerSevenDecreasing.get(i) % num; 
       }
       
       int [] valsSix = new int[powerSix.size()];
       
       for(int i = 0 ; i < valsSix.length ; i++)
           valsSix[i] = powerSix.get(i);
       
       int [] modsSix = new int[powerSix.size()];
       
       for(int i = 0 ; i < powerSix.size() ; i++) {
           modsSix[i] = powerSix.get(i) % num; 
       }
       
       for(int i = 0 ; i < numbers.length ; i++) {
           if(numbers[i] % num == 0) {
               if(k == 1) {
                   out.println(numbers[i]);
                   out.close();
                   return;
                    }
                   k--;
               }
           }
       for(int i = 0 ; i < powerEight.length; i++) {
           if(powerEight[i] % num == 0) {
               if(k == 1) {
                   out.println(powerEight[i]);
                   out.close();
                   return;
                }
                   k--;
               }
           }
       for(int i = 0 ; i < numbers.length ; i++) {
           if(numbers[i] < 10)
               continue;
           
           long currentNumber = numbers[i] * 10000000L;
           long v = currentNumber;
           currentNumber = currentNumber % num;
           currentNumber *= -1;
           while(currentNumber < 0)
               currentNumber += num;
           int toSearch = (int)currentNumber;
                   
           int secondIndex = numbers[i] % 10;
           int firstIndex = (numbers[i] / 10) % 10;
               
           if(secondIndex == 0) {
               // power seven decreasing
               int lowerIndex = binarySearchLower(modsDecreasing, toSearch);
               int upperIndex = binarySearchUpper(modsDecreasing, toSearch);
               
               if(lowerIndex == -1 || upperIndex == -1)
               {
                   continue;
               }
               
               int lengthSeven = 1000000;
               int fromIndex = Arrays.binarySearch(valsDecreasing, lowerIndex, upperIndex+1, lengthSeven);
               fromIndex += 1;
               fromIndex *= -1;
               
               int rangeLength = upperIndex - fromIndex + 1;
               
               if(rangeLength >= k) {
                   out.println(valsDecreasing[fromIndex+(int)k-1]+v);
                   out.close();
                   return;
               } else {
                   k -= rangeLength;
               }
               
           } else {
               // power six
               int lowerIndex = binarySearchLower(modsSix, toSearch);
               int upperIndex = binarySearchUpper(modsSix, toSearch);
               
                   if(lowerIndex != -1 && upperIndex != -1 && secondIndex > firstIndex)
                   {
                       int rangeLength = upperIndex - lowerIndex + 1;
                       
                       if(rangeLength >= k) {
                           out.println(valsSix[lowerIndex+(int)k-1]+v);
                           out.close();
                           return;
                       } else {
                           k -= rangeLength;
                       }
                   }
               
               if(firstIndex > secondIndex) {
                   lowerIndex = binarySearchLower(modsDecreasing, toSearch);
                   upperIndex = binarySearchUpper(modsDecreasing, toSearch);
                   
                   if(lowerIndex == -1 || upperIndex == -1)
                   {
                       continue;
                   }
                   
                   int digit = secondIndex + 1;
                   digit *= 1000000;
                   
                   int fromIndex = Arrays.binarySearch(valsDecreasing, lowerIndex, upperIndex+1, digit);
                   fromIndex +=  1;
                   fromIndex *= -1;
                   
                   int rangeLength2 = upperIndex - fromIndex + 1;
                   if(rangeLength2 >= k) {
                       out.println(valsDecreasing[fromIndex+(int)k -1]+v);
                       out.close();
                       return;
                   } else {
                       k -= rangeLength2;
                   }
                   
               } else {
                   lowerIndex = binarySearchLower(modsIncreasing, toSearch);
                   upperIndex = binarySearchUpper(modsIncreasing, toSearch);
                   
                   if(lowerIndex == -1 || upperIndex == -1)
                   {
                       continue;
                   }

                   int digit = secondIndex;
                   digit *= 1000000;

                   int to = Arrays.binarySearch(valsIncreasing, lowerIndex, upperIndex+1, digit);
                   to +=  1;
                   to *= -1;
                   to -= 1;
                   
                   int rangeLength2 = to - lowerIndex + 1;
                   if(rangeLength2 >= k) {
                       out.println(valsIncreasing[lowerIndex+(int)k -1]+v);
                       out.close();
                       return;
                   } else {
                       k -= rangeLength2;
                   }
               }
           }
      }
       out.println(-1);
       out.close();
    }
    public boolean wavy(long val){
        int digits = 0;
        long copy = val;
        while(copy > 0) {
            copy/=10;
            digits++;
        }
        int [] d = new int[digits];
        for(int i = d.length-1 ; i>=0 ; i--)
        {
            d[i] = (int)(val % 10);
            val/=10;
        }
        
        for(int i = 1 ; i < d.length - 1; i++){
            if(!((d[i] > d[i-1] && d[i] > d[i+1])||(d[i] < d[i-1] && d[i] < d[i+1])))
                return false;
        }
        return true;
    }
    
    public void generateWavy(int num, int lastDigit, boolean isHigher,int index, int maxLength, boolean increase) {
        if(index == maxLength) {
            if(maxLength < 8) {
                numbers[pos] = num;
                pos++;
            }
            else {
                powerEight[pindex++] = num;
            }
            if(maxLength == 7) {
                if(increase) {
                    powerSevenIncreasing.add(num);
                } else {
                    powerSevenDecreasing.add(num);
                }
            }
            else if(maxLength == 6 && !increase) {
                powerSix.add(num);
            }
        }
        else
        if(isHigher) {
            for(int i = lastDigit + 1 ; i <= 9 ; i++)
                generateWavy(num*10 + i, i, false, index+1, maxLength, increase);
        } else {
            for(int i = lastDigit - 1 ; i >= 0 ; i--)
                generateWavy(num*10 + i, i, true, index+1, maxLength,increase);
        }
    }
    public static void main (String [] args) throws IOException {
        new E().solve();
    }
    
    public int binarySearchLower(int [] values, int key) {
        int low = 0;
        int high = values.length - 1;
        
        if(values[low] == key)
            return low;
        
        while(true) {
            int mid = (low + high) >> 1;
            
            if(low > high)
                return -1;
            
            if(values[mid] == key) {
                if(values[mid-1] != key)
                    return mid;
                
                high = mid-1;
            }
            else
                if(values[mid] > key)
                    high = mid-1;
                    else 
                        if(values[mid] < key)
                            low = mid+1;
        }
    }
    
    public int binarySearchUpper(int [] values, int key) {
        int low = 0;
        int high = values.length - 1;
        
        if(values[high] == key)
            return high;
        
        while(true) {
            int mid = (low + high) >> 1;
            
            if(low > high)
                return -1;
            
            if(values[mid] == key) {
                if(values[mid+1] != key)
                    return mid;
                
                low = mid+1;
            }
            else
                if(values[mid] > key)
                    high = mid-1;
                    else 
                        if(values[mid] < key)
                            low = mid+1;
        }
    }
    
}
class modComparator implements Comparator<Integer>{
    int n;
    public modComparator(int n) {
        this.n = n;
    }
    
    @Override
    public int compare(Integer o1, Integer o2) {
        int mod1 = o1 % n;
        int mod2 = o2 % n;
        
        if(mod1 < mod2)
            return -1;
        if(mod1 > mod2)
            return 1;
        
        if(o1 < o2)
            return -1;
        return 1;
    }
}