Secret Commands "Retreat"#4265
You have stumbled upon the secret forum of the "Retreat" team leaders. To gain access, you must correctly answer the key question. The answer is the -th beautiful number within the range from to (counting starts from one).
A number is considered beautiful if the sum of its digits is divisible by . You have only two seconds to provide the correct answer, or you risk being discovered and expelled from the team.
The input consists of a single line containing four numbers: , , , and (1 \leq l \leq r \leq 10^{18}, 1 \leq n \leq 1000, 1 \leq k \leq 10^{18}).
Output the -th beautiful number in the range from to . If no such number exists, print .
Example 1