The N-th Positive Rational Number

Interview

Time limit1sMemory limit256 MB

Summary

Given N, return the N-th term of the diagonal enumeration of positive rationals where each group of constant numerator plus denominator is listed with decreasing numerator.

Level: Easy3 of 10
Topics: Math, Implementation, Brute force
Solved: No attempts yet

Problem

Minho takes a discrete mathematics course. One day the professor proved that the positive rational numbers are countable and then assigned homework.

The positive rationals are listed by the following rule. Collect the fractions whose numerator and denominator have the same sum into one group, and number the groups starting from the smallest sum. The group with sum $s$ holds $s-1$ fractions, and inside the group they are written from the largest numerator down: $\frac{s-1}{1}, \frac{s-2}{2}, \dots, \frac{1}{s-1}$ .

The listing therefore runs $\frac{1}{1}, \frac{2}{1}, \frac{1}{2}, \frac{3}{1}, \frac{2}{2}, \frac{1}{3}, \frac{4}{1}, \dots$ . The first rational is $\frac{1}{1}$ , the second is $\frac{2}{1}$ , the third is $\frac{1}{2}$ , the fourth is $\frac{3}{1}$ , and the fifth is $\frac{2}{2}$ .

Fractions of equal value such as $\frac{1}{1}, \frac{2}{2}, \frac{3}{3}$ count as separate terms. Nothing is reduced.

Minho does not want to do the homework by hand, so he writes a program instead. Find the $N$ -th rational number.

Input

The first line contains a positive integer $N$ . ( $1 \le N \le 1000$ )

Output

If the $N$ -th rational number is $\frac{a}{b}$ , print the numerator $a$ and the denominator $b$ on one line, separated by a space. Do not reduce the fraction.

Hint

Minho solved the homework with a program rather than by hand and derived a formula from it.

Examples3

Example 1
Input
```
1
```
Expected output
```
1 1
```
Example 2
Input
```
2
```
Expected output
```
2 1
```
Example 3
Input
```
5
```
Expected output
```
2 2
```