Problem J. Jump to number ≡

Statement

The task at hand involves finding the k-th sequentially ordered q-ary number (starting from the 1st),
where the sum of its digits equals n, and its length does not exceed l.

Input format

Four integers are provided in the input data: q, n, l and k.

Output format

The output data should contain the resulting number.

If such a number does not exist or if it exceeds the permissible range,
the output data should remain empty.

Constraints

2 ≤ q ≤ 10, 1 ≤ (n, l) ≤ 4000, 1 ≤ k ≤ 10¹⁸

Sample tests

10 100 12 1

199999999999

2 1 1 2