This page is still under construction.

Parts of this page are still being built. What you see may change.

Series

Time limit1sMemory limit128 MB

Summary
Write all integers from n to m as one digit string, sort the digits descending, and report the k-th digit, or NAV if the string is shorter.
Level

Medium6 of 10

Topics
Math, Implementation, Binary search, Prefix sum
Solved
No attempts yet

Problem

Write all the natural numbers from nn to mm (inclusive) in a row, without any separators, forming a series of decimal digits.

For example, if n=98n = 98 and m=102m = 102, this series is 9899100101102.

Then sort all the digits in non-increasing order: the greatest digits first, then the next greatest, and so on.

For the example above, the sorted series is 9998211110000.

Given the natural numbers nn, mm, and kk, determine which digit is at the kk-th position of the sorted series.

Input

Three natural numbers nn, mm, and kk, separated by spaces. (0<n<1090 < n < 10^9, 0<m<1090 < m < 10^9, m≥nm \ge n, 0<k<1090 < k < 10^9)

Output

Output the digit at the kk-th position of the sorted series. If the length of the series is less than kk, output the single word NAV.

Examples4

  1. Example 1

    Input
    98 102 4
    
    Expected output
    8
    
  2. Example 2

    Input
    9999 9999 5
    
    Expected output
    NAV
    
  3. Example 3

    Input
    1 9 1
    
    Expected output
    9
    
  4. Example 4

    Input
    1 10 11
    
    Expected output
    0