Dictionary

Interview

Time limit2sMemory limit128 MB

Summary

Construct the K-th lexicographically smallest string made of N 'a's and M 'z's using combinatorial counting, or report -1 if K exceeds the total count.

Level: Medium5 of 10
Topics: Combinatorics, Greedy, Math
Solved: No attempts yet

Problem

A dictionary contains every string made of exactly N letters a and M letters z, sorted in lexicographic order. Equal letters are indistinguishable, and no other letters appear.

Given N, M, and K, find the K-th string in this dictionary.

Input

The first line contains three integers N, M, and K in that order.

Output

Print the K-th string in the dictionary on the first line. If the dictionary contains fewer than K strings, print -1.

Constraints

1 <= N, M <= 100
1 <= K <= 1,000,000,000

Examples4

Example 1
Input
```
2 2 2
```
Expected output
```
azaz
```
Example 2
Input
```
2 2 6
```
Expected output
```
zzaa
```
Example 3
Input
```
10 10 1000000000
```
Expected output
```
-1
```
Example 4
Input
```
7 4 47
```
Expected output
```
aaazazaazaz
```