Yo`nalishlar
Hozirda online

Statistika

Masalalar soni: 909

Foydalanuvchilar soni: 8825

Jo'natishlar soni: 714634

Muhokama yozuvlari: 4541

Yangiliklar soni: 98

Yangiliklar izohlari: 1179


So'ngi izohlar

705. Inverse problem to Gray code
Vaqt limiti: 1 sekund
Xotira limiti: 64 MB

One can determine the Gray code by its number using a very simple function: G(x) = x xor (x div 2), where xor stands for bitwise exclusive OR (bitwise modulo 2 addition), and div means integer division. It is interesting to note that function G(x) is invertible, which means it is always possible to uniquely restore x given the value of G(x). Write a program to restore number x from the given value of G(x).

Input

The input file contains an integer number y, the value of G(x) (0≤y≤109).

Output

The output file should contain a single integer x such that G(x) = y.

Samples

Input

Output

1

15
10

2

1723
1234

3

0
0

 

Tayyorladi: Azat Yusupov
Text from: Moscow subregional
Mening urinishlarim(0) Muhokama (0) Jo'natish Eng yaxshi yechimlar Barcha muvaffaqiyatli urinishlar(63) Barcha urinishlar(104)