Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

F. Igor and Interesting Numbers

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputIgor likes hexadecimal notation and considers positive integer in the hexadecimal notation interesting if each digit and each letter in it appears no more than *t* times. For example, if *t* = 3, then integers 13a13322, aaa, abcdef0123456789 are interesting, but numbers aaaa, abababab and 1000000 are not interesting.

Your task is to find the *k*-th smallest interesting for Igor integer in the hexadecimal notation. The integer should not contain leading zeros.

Input

The first line contains the two integers *k* and *t* (1 ≤ *k* ≤ 2·10^{9}, 1 ≤ *t* ≤ 10) — the number of the required integer and the maximum number of times some integer or letter can appear in interesting integer.

It can be shown that the answer always exists for such constraints.

Output

Print in the hexadecimal notation the only integer that is the *k*-th smallest interesting integer for Igor.

Examples

Input

17 1

Output

12

Input

1000000 2

Output

fca2c

Note

The first 20 interesting integers if *t* = 1: 1, 2, 3, 4, 5, 6, 7, 8, 9, a, b, c, d, e, f, 10, 12, 13, 14, 15. So the answer for the first example equals 12.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/16/2018 21:36:00 (d1).

Desktop version, switch to mobile version.

User lists

Name |
---|