Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3639
Guess a Function

Time Limit: 2 Seconds      Memory Limit: 65536 KB

We define that

g(x) = x^(x/2)

h1(x) = x / m1 * m1 + ( x + s1) % m1

h2(x) = x / m2 * m2 + ( x + s2) % m2

f(x) = g( h2( g( h1( g( x ) ) ) ) )

All above are integer arithmetic, and '^' is binary xor, for example, 8/3 = 2 , 5 ^ 12 = 9. m1, m2, s1, s2 are 4 positive integers less than 345678, and fixed in all cases. But they are not explicitly given, you should guess them from the sample. (0.3m1 < s1< m1, 0.3m2 < s2<m2)

What's more, your submission limit is 1KB!

Input

Each line is a case. Every case is an integer x,( 0≤ x< 232).

Output

Each case a line, please output f(x).

Sample Input

Sample Output

Hint

Please download the sample. Every case in test is also in sample.


Author: ZHOU, Yuchen
Contest: ZOJ Monthly, August 2012
Submit    Status