### Problem Statement

Consider a square n x n matrix A. The cell Ai,j is equal to the product i * j (i, j are 1-based). Let's create a one-dimensional array which contains all the elements of the matrix A. The length of this array will be equal to n2. Sort this array and return the element which will be in the k-th position (k is a 1-based index).

### Definition

 Class: ProductsMatrix Method: nthElement Parameters: int, int Returns: long Method signature: long nthElement(int n, int k) (be sure your method is public)

### Constraints

-n will be between 1 and 10^5, inclusive.
-k will be between 1 and min(10^9, n^2), inclusive.

### Examples

0)

 `3` `7`
`Returns: 6`
 The matrix will be: ```1 2 3 2 4 6 3 6 9 ``` The array after sorting will be: {1, 2, 2, 3, 3, 4, 6, 6, 9}.
1)

 `2` `4`
`Returns: 4`
 k is 1-based.
2)

 `3` `8`
`Returns: 6`
3)

 `1` `1`
`Returns: 1`
4)

 `4` `4`
`Returns: 3`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=6197

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10061&pm=6197

Mike Mirzayanov

#### Testers:

PabloGilberto , brett1479 , Olexiy

Search