Ant on a Chessboard

One day, an ant called Alice came to an M×M chessboard. She wanted to go around all the squares. So she began to walk along the chessboard according to this way (you can assume that her speed is one square per second):

At the first second, Alice was standing at (1,1). Firstly, she went up a square, then a square to the right, then a square downward. After that, she went a square to the right, then two squares upward, and then two squares to the left… In a word, the path was like a snake.

For example, her first 25 seconds went like this (the number in each square stands for the time when she went into that square):

At the 8^th second, she was at (2,3), and at the 20^th second, she was at (5,4).

Your task is to decide where she was at a given time (you can assume that M is large enough).

Input Specification

The input will contain several lines, and each line contains a number N (1 ≤ N ≤ 2⋅10⁹) which stands for the time. The input will be terminated with a line that contains a number 0.

Output Specification

For each input situation, you should print a line with two numbers (x, y), the column and the row number, with exactly one space between them.

Sample Input

1. 8
2. 20
3. 25
4. 0

download as text file

Output for Sample Input

1. 2 3
2. 5 4
3. 1 5

download as text file