提示: 欢迎访问OurACM平台。
Problem 1304 Recaman's Sequence

Accept: 692    Submit: 1990
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

The Recaman's sequence is defined by a(0)=0; for m>0, a(m)=a(m-1)-m if the resulting a(m) is positive and not already in the sequence, otherwise a(m)=a(m-1)+m.

The first few numbers in the Recaman's Sequence is 0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9, ...

Given k, your task is to calculate a(k).

Input

The input consists of several test cases. Each line of the input contains an integer k where 0<=k<=500000.

The last line contains an integer -1, which should not be processed.

Output

For each k given in the input, print one line containing a(k) to the output.

Sample Input

7 10000 -1

Sample Output

20 18658

Source

Shanghai2004 Preliminary

Submit  Back  Status  Discuss