Secret Commands "Retreat"

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 k-th beautiful number within the range from l to r (counting starts from one).

A number x is considered beautiful if the sum of its digits is divisible by n. You have only two seconds to provide the correct answer, or you risk being discovered and expelled from the team.

Input

The input consists of a single line containing four numbers: l, r, n, and k (1 ≤ l ≤ r ≤ 10^18, 1 ≤ n ≤ 1000, 1 ≤ k ≤ 10^18).

Output

Output the k-th beautiful number in the range from l to r. If no such number exists, print -1.

Examples