Snail Top

Time limit1sMemory limit512 MB

Summary

For a half-disc of radius R (x^2+y^2 <= R^2, x >= 0), find the integer point strictly inside it that maximizes the area swept when the half-disc rotates one full turn about that axis.

Level: Medium6 of 10
Topics: Geometry, Math, Binary search, Brute force
Solved: No attempts yet

Problem

As an adventurer of Victoria Island, you are famous for hunting snails and nothing else. One day, you hear a rumor that a huge and powerful long-lived snail named Mano appears somewhere in Lith Harbor. Wanting a bigger and stronger snail, you start searching every corner of Lith Harbor for Mano, and after wandering for a long while, you finally find Mano. You are briefly overwhelmed by Mano's stature, which matches its reputation, but since you have the skill "Snail's Weak Point," you quickly succeed in hunting Mano. Mano then leaves behind a few incomprehensible words and a rainbow-colored snail shell and vanishes.

As if possessed, you use the rainbow-colored snail shell, and at that moment you turn into a snail! Fortunately, you return shortly after, but you realize that the wish you had unconsciously held was to become a snail. Sadly, the one-of-a-kind rainbow-colored snail shell can no longer be obtained, and that means you can never become a snail again. Instead of becoming a snail, you decide to use the snail shells you have collected in a meaningful way to honor the snails you have hunted.

While thinking about how to use the snail shells, you come up with a tremendous idea! It is to make toy tops out of snail shells. You name it "Snail Top" and begin making them. A Snail Top is assembled from a disc and an axis, and the disc of a Snail Top is represented as in the following figure.

That is, it is the region in the coordinate plane where $x^2+y^2 ≤ R^2$ and $0 ≤ x$ . Each Snail Top has a measure called combat power, defined as the area of the trace produced when the disc is rotated one full turn around the axis. Combat power depends on the position of the axis, and tops with higher combat power sell better, so you want to find the axis position that maximizes it. The axis must lie strictly inside the disc, not on its boundary, and for convenience in the manufacturing process, both coordinates $(x, y)$ of the axis must be integers. Given the radius $R$ of the disc, find the axis position that maximizes combat power.

Input

The first line contains an integer $R$ , the radius of the disc.

Output

Output the coordinates of the axis that maximizes combat power. If there are multiple valid answers, output the one with the largest $x$ -coordinate, and if there are still multiple with the same $x$ -coordinate, output the one with the largest $y$ -coordinate.

Constraints

$2 ≤ R ≤ 10^9$

Examples1

Example 1
Input
```
2
```
Expected output
```
1 1
```