DWITE, November 2011, Problem 1

Once upon a time, Little Billy romped about, passing by candy stores. However, that candy store has since shut down, and he has been deprived of the very essence of his life. In light of this existential crisis, his walks have never been quite the same. Today, he is aimlessly walking from his home $(0,0)$ to infinity, in search of his lost soul.

Billy's concerned parents would like to know where Billy is after $N$ steps. They know that he can take two types of steps: one unit down or one unit to the right. He follows a predictable pattern: $1$ step right, $2$ steps down, $3$ steps right, $4$ steps down, and so on. That is, the sequence of steps begins as follows: R D D R R R D D D D.

The input will contain 5 test cases, each consisting of one line, containing the number of steps $0\le N\le 100000$.

Your output should contain 5 lines with two space-separated integers each, representing Billy's coordinates after $N$ steps in the corresponding test case.

Sample Input

0
1
2
3
4

Sample Output

0 0
1 0
1 -1
1 -2
2 -2

Problem Resource: DWITE