One day, an ant named Alice 1 came to an M x M chessboard. She wanted to go around all the squares. Moving at a speed of one square per second, she began to walk along the chessboard in the following manner:

At the start, Alice was standing at (1, 1). She began her journey by going up a square then a square to the right, and 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:

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 (3, 2), and at 20 seconds, she would be at (4, 5). Your task is to decided where she would be at a given time.


The input consists of several lines, where each line contains a number N where 1 <= N <= 10,000, which stands for the time.

Example Input



For each input time, output the time, row, and column number Alice would be at that time in the format: time = (row, column).

Example Output

8 = (3, 2)
20 = (4, 5)
25 = (5, 1)

Programming Challanges

This is based on 10161 - Ant on a Chessboard problem on the UVa Online Judge.


To submit your work, follow the same procedure you used for Reading 00:

$ cd path/to/cse-30872-fa18-assignments     # Go to assignments repository
$ git checkout master                       # Make sure we are on master
$ git pull --rebase                         # Pull any changes from GitLab

$ git checkout -b challenge24               # Create and checkout challenge24 branch

$ $EDITOR challenge24/program.cpp           # Edit your code

$ git add challenge24/program.cpp           # Stage your changes
$ git commit -m "challenge24: done"         # Commit your changes

$ git push -u origin challenge24            # Send changes to GitLab

To check your code, you can use the .scripts/ script or curl:

$ .scripts/
Submitting challenge24 assignment ...
Submitting challenge24 code ...
  Result Success
   Score 6.00
    Time 0.06

$ curl -F source=@challenge24/program.cpp
{"score": 6, "result": "Success"}

Once you have commited your work and pushed it to GitLab, member to create a merge request. Refer to the Reading 11 TA List to determine your corresponding TA for the merge request.

  1. It's always Alice. Or Bob.