eolymp
Competitions

2022 Azerbaijan - semifinals

Strange Sequence

From the given number n, the following sequence S is obtained:

S0 = n,

Si = f(Si-1), i1

Here f(x) is equal to the difference between the numbers obtained by rearranging the digits of the number x in descending and ascending order. For example:

f(2214) = 42211224 = 2997

Note that leading zeros are not counted. Find the value of Sk.

Input

Two integers n (0n109) and k (0k105).

Output

Print the value of Sk.

Example

Let n = 2214, k = 2. Then:

A0 = 2214,

A1 = f(2214) = 42211224 = 2997

A2 = f(2997) = 99722799 = 7173

Time limit 1 second
Memory limit 128 MiB
Input example #1
757 334
Output example #1
495
Source 2022 Azerbaijan Republic Olympiad, Semifinals, March 8