K-th Number in a Times Table

A times table with m rows and n columns holds the number r * c in row r and column c, counting both from 1. For example, the table with 3 rows and 4 columns is:

1  2  3  4
2  4  6  8
3  6  9  12

Imagine writing all m * n entries in one list, sorted from smallest to largest and keeping repeats. Write kth_in_table(m, n, k) that returns the k-th number of that list, counting from 1.

Examples

kth_in_table(3, 4, 5)    # returns 3
kth_in_table(3, 4, 12)   # returns 12
kth_in_table(2, 2, 3)    # returns 2

The sorted entries of the 3 by 4 table are 1, 2, 2, 3, 3, 4, 4, 6, 6, 8, 9, 12, so the 5th one is 3.

Constraints

• 1 <= m, n <= 30,000
• 1 <= k <= m * n

Note

The largest tables have 900 million entries, far too many to list or sort.