eolymp
bolt
Try our new interface for solving problems
Problems

Graded lexicographic order

Graded lexicographic order

Time limit 3 seconds
Memory limit 32 MiB

Consider the integers from 1 to n. Called the weight of its sum of digits, and let the weight of x for w(x).

Then we'll arrange the numbers in the so-called graded lexicographic order. Let two numbers a and b. If w(a) < w(b), then the number a is the graded lexicographic order to the number b. If w(a) = w(b), if a number is in the graded lexicographic order to the number of b if and only if the decimal representation of a lexicographically less than the decimal representation of b.

For example, in this order:

  • number of 120 goes to number 4;

  • number of 555 goes to number 78;

  • number of 20 goes to number 200.

For given n and k, find the number k and the number, located on the k-th position in the graded lexicographic ordering of natural numbers from 1 to n.

Input data

In the input file contains n and k (1kn10^18).

Output data

The first line of the output file output the number of k.

The second row output digits in the k-th place.

Examples

Input example #1
20
10
Output example #1
2
14