OROSNAKE - Ouroboros Snake

Ouroboros is a mythical snake from ancient Egypt. It has its tail in its mouth and continuously devours itself.

The Ouroboros numbers are binary numbers of 2^n bits that have the property of "generating" the whole set of numbers from 0 to 2^n - 1. The generation works as follows: given an Ouroboros number, we place its 2^n bits wrapped in a circle. Then, we can take 2^n groups of n bits starting each time with the next bit in the circle. Such circles are called Ouroboros circles for the number n. We will work only with the smallest Ouroboros number for each n.

Example: for n = 2, there are only four Ouroboros numbers. These are 0011; 0110; 1100; and 1001. In this case, the smallest one is 0011. Here is the Ouroboros circle for 0011:

subir imagenes


The table describes the function o(n;k) which calculates the k-th number in the Ouroboros circle of the smallest Ouroboros number of size n. This function is what your program should compute.

Input

The input consists of several test cases. For each test case, there will be a line containing two integers n and k (1<=n<=15; 0<=k<2^n). The end of the input file is indicated by a line containing two zeros. Don't process that line.

Output

For each test case, output o(n;k) on a line by itself.

Example

Input:
2 0
2 1
2 2
2 3
0 0

Output:
0
1
3
2

Added by:Daniel Gómez Didier
Date:2008-11-24
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:PUJ Internal Contest

hide comments
2017-10-21 18:44:53
Some fascinating connections behind these numbers, from computer security to neuroscience. Had no idea about any of that last night when taking a look at what looked like a regular binary puzzle. Great problem.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.