Description

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

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

For example, her first 25 seconds went like this:

25 24 23 22 21
10 11 12 13 20
 9  8  7 14 19
 2  3  6 15 18
 1  4  5 16 17

Eight seconds in, she would be at (2, 3), and at 20 seconds, she would be at (5, 4). Your task is to decided where she would be at a given time.

Input

The input consists of several lines, where each line contains a number N where 1 <= N <= 2*10^9, which stands for the time. Here is an sample input:

8
20
25

Output

For each input time, output the column and row number X Y Alice would be at that time. Here is an sample output:

2 3
5 4
1 5

Approach

Compute the nearest square and use that to determine the coordinates of the ant at the specified position. Even squares requiring going up and to the left, while odd squares require going right and down.

Input/Output

• Final input: problem025.input
• Final output: problem025.output

Source Code

• Peter Bui's source code: pbui.cc
• Ian Gavlick's source code: igavlick.cc
• Tommy Walton's source code: twalton1.cpp