Problem J. Jump to number

Author:A. Karabanov, A. Baranov   Time limit:1 sec
Input file:Standard input   Memory limit:256 Mb
Output file:Standard output  

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 ≤ 1018

Sample tests

No. Standard input Standard output
1
10 100 12 1
199999999999
2
2 1 1 2

0.065s 0.009s 13