VECTAR10 - Card Game

Changu and Mangu have an ordered deck of n cards numbered 1 to n with card 1 at the top and card n at the bottom. They want to play a game. They perform a wierd operation as long as there are at least two cards in the deck: Changu throws away the top card and then Mangu moves the card that is now on the top of the deck to the bottom of the deck. Your task is to find the last remaining card.

Input

Each line of input (except the last) contains a positive number n ≤ 1000000. The last line contains 0 and this line should not be processed. Input will not contain more than 500000 lines.

Output

For each number from input produce one line of output giving the last remaining card.

Example

Sample Input:
2
3
4
0

Sample Output:
2
2
4

Warning: Large I/O data, be careful with certain languages


Added by:Piyush Kumar
Date:2016-07-05
Time limit:0.100s-3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY

hide comments
2016-07-17 19:36:45
just open ur eyes and check other test cases....!!!!
2016-07-10 06:59:50
Finally AC!!

Last edit: 2016-07-11 12:19:38
2016-07-08 21:25:32
ac in one go<3
2016-07-08 19:40:25
cin/cout AC in 1.60 sec..same code with printf/scanf AC in .17 sec strange..
2016-07-07 14:00:10
bit fun :-) nice 1 go AC :-)
2016-07-07 13:07:37 Som
@Piyush can you please check my submission ,I am getting a WA
2016-07-07 12:40:47
Took me one hour to figure out this :
if(i&(i-1)==0) is not same as if((i&(i-1))==0).
2016-07-06 12:43:53 hanstan
AC 0.04s :3

Re: Congrats, you have matched my fastest solution :)

Last edit: 2016-07-06 13:25:50
2016-07-06 06:04:53
Got TLE with Python3 , but AC wiith C
2016-07-06 00:27:15
Nice

Last edit: 2016-07-06 22:48:33
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.