Amr bought a new video game "Guess Your Way Out!". The goal of the game is to find an exit from the maze that looks like a perfect binary tree of height h. The player is initially standing at the root of the tree and the exit from the tree is located at some leaf node. 

Let's index all the leaf nodes from the left to the right from 1 to 2^{h}. The exit is located at some node n where 1 ≤ n ≤ 2^{h}, the player doesn't know where the exit is so he has to guess his way out!

Amr follows simple algorithm to choose the path. Let's consider infinite command string "LRLRLRLRL..." (consisting of alternating characters 'L' and 'R'). Amr sequentially executes the characters of the string using following rules:  Character 'L' means "go to the left child of the current node";  Character 'R' means "go to the right child of the current node";  If the destination node is already visited, Amr skips current command, otherwise he moves to the destination node;  If Amr skipped two consecutive commands, he goes back to the parent of the current node before executing next command;  If he reached a leaf node that is not the exit, he returns to the parent of the current node;  If he reaches an exit, the game is finished. 

Now Amr wonders, if he follows this algorithm, how many nodes he is going to visit before reaching the exit?


-----Input-----

Input consists of two integers h, n (1 ≤ h ≤ 50, 1 ≤ n ≤ 2^{h}).


-----Output-----

Output a single integer representing the number of nodes (excluding the exit node) Amr is going to visit before reaching the exit by following this algorithm.


-----Examples-----
Input
1 2

Output
2
Input
2 3

Output
5
Input
3 6

Output
10
Input
10 1024

Output
2046


-----Note-----

A perfect binary tree of height h is a binary tree consisting of h + 1 levels. Level 0 consists of a single node called root, level h consists of 2^{h} nodes called leaves. Each node that is not a leaf has exactly two children, left and right one. 

Following picture illustrates the sample test number 3. Nodes are labeled according to the order of visit.

[Image]

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Mathematics

Tree algorithms

Implementation


Solutions:
import sys
import math
MAXNUM = math.inf
MINNUM = -1 * math.inf
ASCIILOWER = 97
ASCIIUPPER = 65

def getInt():
	return int(sys.stdin.readline().rstrip())

def getInts():
	return map(int, sys.stdin.readline().rstrip().split(' '))

def getString():
	return sys.stdin.readline().rstrip()

def printOutput(ans):
	sys.stdout.write(str(ans) + '\n')

def solve(h, n):
	heightNodes = [1 for _ in range(51)]
	for height in range(1, 51):
		heightNodes[height] = 2 ** height + heightNodes[height - 1]
	curPos = 2 ** (h - 1)
	depth = h
	add = 2 ** (h - 1)
	direction = -1
	total = 0
	while True:
		if depth == 0:
			break
		if curPos >= n and direction == -1 or (curPos < n and direction == 1):
			total += 1
			depth -= 1
			add //= 2
			curPos += direction * add
		else:
			total += heightNodes[depth - 1]
		direction *= -1
	return total

def readinput():
	(h, n) = getInts()
	printOutput(solve(h, n))
readinput()


(height, n) = list(map(int, input().split()))
s = height
reverted = False
for h in range(height - 1, -1, -1):
	if n > 2 ** h:
		more = True
		n -= 2 ** h
	else:
		more = False
	if more ^ reverted:
		s += 2 * 2 ** h - 1
	reverted = not more
print(s)


(h, n) = (int(x) for x in input().split())
(leftPlus, rightPlus) = (1, 2 ** h)
answer = 1
curLevel = 0
delim = 2 ** (h - 1)
while curLevel != h:
	h -= 1
	if n <= delim:
		answer += leftPlus
		(leftPlus, rightPlus) = (max(rightPlus // 2, leftPlus // 2), 1)
		delim -= 2 ** (h - 1)
	else:
		answer += rightPlus
		(leftPlus, rightPlus) = (1, max(rightPlus // 2, leftPlus // 2))
		delim += 2 ** (h - 1)
print(answer - 1)


(h, n) = map(int, input().split())
l = 1
r = 2 ** h
ans = 0
now = 'l'
for i in range(h, 0, -1):
	if n < (l + r) / 2 and now == 'l':
		now = 'r'
		r -= 2 ** (i - 1)
		ans += 1
	elif n < (l + r) / 2 and now == 'r':
		r -= 2 ** (i - 1)
		ans += 2 ** i
	elif n > (l + r) / 2 and now == 'l':
		l += 2 ** (i - 1)
		ans += 2 ** i
	else:
		now = 'l'
		l += 2 ** (i - 1)
		ans += 1
print(ans)


import math

def is_left_son(num):
	if num == num // 2 * 2:
		return True
	else:
		return False

def bin_search(place, depth):
	answer = ''
	length = 2 ** depth
	while length > 1:
		if place > length / 2:
			answer += 'R'
			place -= length / 2
		else:
			answer += 'L'
		length = length / 2
	return answer

def traverse(depth, route):
	answer = 0
	cur_vert = 1
	cur_dir = 'L'
	while route:
		if route[0] == 'R':
			cur_vert = cur_vert * 2 + 1
		else:
			cur_vert = cur_vert * 2
		if cur_dir == route[0]:
			answer += 1
		else:
			answer += 2 ** depth
		depth -= 1
		route = route[1:]
		cur_dir = 'R' if is_left_son(cur_vert) else 'L'
	return answer
(h, n) = (int(x) for x in input().split())
amount_visited = 0
cur_pos = 1
print(traverse(h, bin_search(n, h)))


(h, n) = map(int, input().split())
p = 1 << h - 1
i = r = 0
n -= 1
while h:
	r += 1
	if n >= p:
		j = 1
		n -= p
	else:
		j = 0
	if j ^ i:
		r += p + p - 1
	else:
		i = 1 - i
	p >>= 1
	h -= 1
print(r)


(h, n) = map(int, input().split())
left = True
bit = str.zfill(bin(n - 1)[2:], h)
ans = 1
for d in bit:
	if left and d == '1' or (not left and d == '0'):
		ans += 2 ** h
	else:
		ans += 1
		left = not left
	h -= 1
print(ans - 1)


(h, n) = map(int, input().split())
total = 2 ** (h + 1) - 1
sum_v = 0
range_v = (0, 2 ** h - 1)
prev_r = range_v
x = n - 1
left = False
curr_h = 0

def in_range(r, x):
	return r[0] <= x <= r[1]

def range_width(r):
	return r[1] - r[0] + 1

def update_range(r, l):
	w = range_width(r) // 2
	st = r[0] if l else r[0] + w
	return (st, st + w - 1)
while range_width(range_v) != 0:
	left = not left
	tmp = range_v
	if in_range(range_v, x):
		range_v = update_range(range_v, left)
		sum_v += 1
		curr_h += 1
	else:
		range_v = update_range(prev_r, left)
		sum_v += 2 ** (h - curr_h + 1) - 1
	prev_r = tmp
print(sum_v - 1)


(h, n) = map(int, input().split())
L = 0
R = 1

def count_nodes(h, n, direction):
	if h == 0:
		return 0
	i_am_on = R if n > 2 ** (h - 1) else L
	new_n = n if i_am_on == L else n - 2 ** (h - 1)
	inter_nodes = 1 if direction == i_am_on else 2 ** h
	return inter_nodes + count_nodes(h - 1, new_n, 1 - i_am_on)
print(count_nodes(h, n, L))


__author__ = 'Konrad Strack'

def command_gen():
	while True:
		yield 'L'
		yield 'R'

def solve():
	(h, n) = [int(x) for x in input().split()]
	leaves = 2 ** h
	path = []
	(left, right) = (1, leaves)
	for i in range(h):
		middle = (left + right) // 2
		if n <= middle:
			path.append('L')
			right = middle
		else:
			path.append('R')
			left = middle + 1
	command = command_gen()
	sum = 0
	hi = h
	for p in path:
		cmd = next(command)
		if p != cmd:
			sum += 2 ** hi - 1
			next(command)
		hi -= 1
	sum += len(path)
	print(sum)

def __starting_point():
	solve()
__starting_point()


(H, n) = map(int, input().split(' '))
res = 0
s = 0
for h in range(H, 0, -1):
	res += 1
	if s ^ (n > 1 << h - 1):
		res += (1 << h) - 1
	else:
		s ^= 1
	if n > 1 << h - 1:
		n -= 1 << h - 1
print(res)


from sys import stdin, stdout
nmbr = lambda : int(input())
lst = lambda : list(map(int, input().split()))

def fn(s, e, left, dpth):
	global ans
	if s == e:
		return
	mid = s + e >> 1
	left ^= 1
	nodes = (1 << h - dpth + 1) - 1
	if s <= n <= mid:
		if left == 0:
			ans += nodes // 2
		fn(s, mid, 1, dpth + 1)
	else:
		if left == 1:
			ans += nodes // 2
		fn(mid + 1, e, 0, dpth + 1)
for _ in range(1):
	(h, n) = lst()
	ans = 0
	end = 1 << h
	mid = (1 + end) // 2
	if 1 <= n <= mid:
		fn(1, mid, 1, 1)
	else:
		ans += (1 << h) - 1
		fn(mid + 1, end, 0, 1)
	print(ans + h)


(h, n) = map(int, input().split())
n = n - 1 + (1 << h)
res = h
for i in range(1, h + 1):
	a = n & 1 << i
	b = n & 1 << i - 1
	if not (a == 0) ^ (b == 0):
		res += (1 << i) - 1
print(res)


from collections import defaultdict, deque, Counter
from sys import stdin, stdout
from heapq import heappush, heappop
import math
import io
import os
import math
import bisect

def isPrime(x):
	for i in range(2, x):
		if i * i > x:
			break
		if x % i == 0:
			return False
	return True

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(int(i))
			n = n / i
	if n > 2:
		l.append(n)
	return list(set(l))

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def sieve(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def digits(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def ceil(n, x):
	if n % x == 0:
		return n // x
	return n // x + 1

def mapin():
	return map(int, input().split())

def solve(a, b, size):
	msf = -1000000000.0
	meh = 0
	for i in range(b, size):
		meh = meh + a[i]
		if msf < meh:
			msf = meh
		if meh < 0:
			meh = 0
	return msf
t = 1
ll = [2 ** i for i in range(60)]
for _ in range(t):
	(h, n) = mapin()
	l = [0] * (h + 1)
	l[h] = n
	z = h
	c = ll[h - 1]
	while z:
		te = l[z]
		if l[z] > ll[z - 1]:
			te = l[z] - ll[z - 1]
		z -= 1
		l[z] = te
	i = 0
	ans = 0
	curr = 0
	while h > 0:
		if i & 1 == 0:
			if l[h] <= ll[h - 1]:
				ans += 1
				i += 1
			else:
				ans += ll[h]
		elif l[h] > ll[h - 1]:
			ans += 1
			i += 1
		else:
			ans += ll[h]
		h -= 1
	print(ans)


(h, p) = map(int, input().split())
ans = 0
ml = 0
gl = True
while h >= 1:
	h -= 1
	if p > ml and p <= ml + (1 << h):
		if gl:
			ans += 1
			gl = not gl
		else:
			ans += 2 * (1 << h)
	else:
		ml += 1 << h
		if not gl:
			ans += 1
			gl = not gl
		else:
			ans += 2 * (1 << h)
print(f'{ans}')


def main():
	(h, n) = map(int, input().split())
	(c, m) = (0, 2 ** h)
	r = 0
	while m > 1:
		if c == 0:
			if n > m // 2:
				r += m - 1
				n -= m // 2
				c = 1 - c
		elif n > m // 2:
			n -= m // 2
		else:
			r += m - 1
			c = 1 - c
		c = 1 - c
		r += 1
		m //= 2
	print(r)
main()


def pow1(x, base):
	sq = 1
	while base > 0:
		if base % 2:
			base -= 1
			sq = sq * x
		base //= 2
		x = x * x
	return sq
(h, n) = map(int, input().split())
levels = pow1(2, h)
(cur, be, en) = (1, 1, levels)
last = 1
while h:
	(mid, flag) = ((be + en) // 2, 0)
	if n <= mid:
		(en, flag) = (mid, 0)
	else:
		(be, flag) = (mid + 1, 1)
	if flag != last:
		cur += 1
	else:
		cur += pow1(2, h)
	last = flag
	h -= 1
print(cur - 1)


def ans():
	(h, n) = [int(i) for i in input().split()]
	div = 2 ** (h - 1)
	mystr = ''
	for i in range(h):
		if n > div:
			mystr += 'G'
			div += 2 ** (h - i - 2)
		else:
			mystr += 'L'
			div -= 2 ** (h - i - 2)
	if mystr[0] == 'L':
		ans = 1
	elif mystr[0] == 'G':
		ans = 2 ** h
	for i in range(len(mystr) - 1):
		if mystr[i + 1] == mystr[i]:
			ans += 2 ** (h - i - 1)
		else:
			ans += 1
	print(ans)
	return
ans()


(h, n) = [int(_) for _ in input().split()]
start = 1
end = 2 ** h
last = 'l'
ans = 0
for i in range(h):
	mid = (start + end) // 2
	if n <= mid:
		end = mid
		if last == 'l':
			last = 'r'
			ans += 1
		else:
			ans += 2 ** (h - i)
	else:
		start = mid
		if last == 'r':
			last = 'l'
			ans += 1
		else:
			ans += 2 ** (h - i)
print(ans)


def main():
	(h, n) = read()
	n -= 1
	n = bin(n)[2:]
	n = '0' * (h - len(n)) + n
	s = ''
	for i in range(h):
		if i and n[i - 1] == '0':
			s += '1' if n[i] == '0' else '0'
		else:
			s += n[i]
	ct = 0
	for i in range(h):
		ct += 1
		if s[i] == '1':
			ct += 2 ** (h - i) - 1
	print(ct)

def read(mode=2):
	inputs = input().strip()
	if mode == 0:
		return inputs
	if mode == 1:
		return inputs.split()
	if mode == 2:
		return list(map(int, inputs.split()))

def write(s='\n'):
	if s is None:
		s = ''
	if isinstance(s, list):
		s = ' '.join(map(str, s))
	s = str(s)
	print(s, end='')
write(main())


(h, n) = list(map(int, input().split()))
z = 2
z1 = 1
p = 0
r = 0
h2 = 0
h3 = 2 ** h
while p < h:
	if n <= h2 + h3 // z and r == 0:
		z1 += 1
		z *= 2
		r = 1
	elif n > h2 + h3 // z and r == 0:
		h2 += h3 // z
		z1 += 2 ** (h - p)
		z *= 2
		r = 0
	elif n <= h2 + h3 // z and r == 1:
		z1 += 2 ** (h - p)
		z *= 2
		r = 1
	elif n > h2 + h3 // z and r == 1:
		h2 += h3 // z
		z1 += 1
		z *= 2
		r = 0
	p += 1
print(z1 - 1)


(h, n) = map(int, input().split())
h -= 1
n -= 1
l = 0
r = 2 << h
ll = True
ans = 0
i = 0
while r - l > 1:
	m = (l + r) // 2
	if ll == (n < m):
		ans += 1
	else:
		ans += 1 << h - i + 1
	if n < m:
		r = m
		ll = False
	else:
		l = m
		ll = True
	i += 1
print(ans)


(h, n) = map(int, input().split())
w = 1
r = 0
n -= 1
while h:
	r += 1
	if w and n < 2 ** (h - 1) or (not w and n >= 2 ** (h - 1)):
		w = not w
	else:
		r += 2 ** h - 1
	if n >= 2 ** (h - 1):
		n -= 2 ** (h - 1)
	h -= 1
print(r)


import math
s = 'LRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLR'
(h, n) = [int(x) for x in input().split()]
n = 2 ** h - 1 + n
left = 2 ** h
right = 2 ** (h + 1) - 1
path = []
for i in range(h):
	center = (right + left) / 2
	if n > center:
		path.append('R')
		left = math.ceil(center)
	else:
		path.append('L')
		right = int(center)
cost = 1
for i in range(len(path)):
	if s[i] != path[i]:
		cost += 2 ** (h - i) - 1 + 1
		s = s[:i] + s[i + 1:]
	else:
		cost += 1
print(cost - 1)


(H, N) = [int(i) for i in input().split()]
result = 0
side = 0
for h in range(H, 0, -1):
	result += 1
	if side ^ (N > 1 << h - 1):
		result += (1 << h) - 1
	else:
		side ^= 1
	if N > 1 << h - 1:
		N -= 1 << h - 1
print(result)


def exponentiation(n):
	if n == 0:
		return 1
	elif n == 1:
		return 2
	t = exponentiation(n // 2)
	if n % 2 == 0:
		return t * t
	else:
		return t * t * 2
(h, n) = map(int, input().split())
a = []
temp = n - 1
for i in range(h):
	a.append(temp % 2)
	temp //= 2
a = a[::-1]
nodes_visited = 0
if a[0] == 1:
	nodes_visited += exponentiation(h)
else:
	nodes_visited += 1
for x in range(1, h):
	if a[x] == a[x - 1]:
		nodes_visited += exponentiation(h - x)
	else:
		nodes_visited += 1
print(nodes_visited)


def cnt_res(n):
	d = [1]
	s = 0
	for i in range(n):
		s += d[-1]
		d.append(d[-1] * 2)
	return s
(h, n) = map(int, input().split())
answ = 0
l = 1
r = 2 ** h
b = h
dir = 'L'
for i in range(h):
	if dir == 'L':
		if n > (l + r) / 2:
			answ += cnt_res(b) + 1
			l = (l + r) // 2 + 1
		elif n < (l + r) / 2:
			r = (l + r) // 2 + int(l + r % 2 != 0) - 1
			answ += 1
			dir = 'R'
		b -= 1
	else:
		if n < (l + r) / 2:
			answ += cnt_res(b) + 1
			r = (l + r) // 2 + int(l + r % 2 != 0) - 1
		elif n > (l + r) / 2:
			answ += 1
			l = (l + r) // 2 + 1
			dir = 'L'
		b -= 1
print(answ)


s = lambda x: sum((2 ** i for i in range(x + 1)))
(h, n) = map(int, input().split())
m = 2 ** h
ans = 0
d = 1
while 1:
	if h == 1:
		if d == 1:
			if n == 1:
				print(ans + 1)
			else:
				print(ans + 2)
		elif n == 2:
			print(ans + 1)
		else:
			print(ans + 2)
		break
	z = m // 2
	if n > z and d == 1:
		n -= z
		ans += s(h - 1) + 1
		d = 1
	elif n <= z and d == 1:
		ans += 1
		d = 0
	elif n <= z and d == 0:
		ans += s(h - 1) + 1
		d = 0
	elif n > z and d == 0:
		ans += 1
		d = 1
		n -= z
	h -= 1
	m = 2 ** h


def n_of_nodes(h):
	result = 0
	for i in range(h):
		result += 2 ** i
	return result
(h, n) = tuple(map(int, input().split()))
way = ''
t = h
while t:
	if n % 2:
		way = 'L' + way
		n //= 2
		n += 1
	else:
		way = 'R' + way
		n //= 2
	t -= 1
answer = 1
current = 'L'
t = h
for i in way:
	if i == current:
		answer += 1
		if current == 'L':
			current = 'R'
		else:
			current = 'L'
	else:
		answer += n_of_nodes(t) + 1
	t -= 1
print(answer - 1)


sl = [0] * 51
sl[0] = 1
for i in range(1, 51):
	sl[i] = sl[i - 1] + 2 ** i
(h, n) = map(int, input().split())
nl = []
n += sl[h - 1]
tn = n
nl.append(tn)
while tn != 1:
	tn = tn // 2
	nl.append(tn)
ans = 0
cn = 1
cp = False
while cn != n:
	tnl = []
	for i in range(h):
		tnl.append(cn)
		if cp == False:
			cn *= 2
		else:
			cn = cn * 2 + 1
		cp = not cp
	if cn == n:
		ans += h
		break
	tnl.append(cn)
	tnl = tnl[::-1]
	for i in range(1, h + 1):
		if nl[i] == tnl[i]:
			ans += sl[i - 1] + h - i + 1
			h = i - 1
			cn = tnl[i - 1]
			if cn == tnl[i] * 2:
				cn = tnl[i] * 2 + 1
				cp = False
			else:
				cn = tnl[i] * 2
				cp = True
			break
print(ans)


import sys

def main():
	rdl = list(map(int, input().split()))
	obx(rdl[0], rdl[1], 0, 1)

def obx(lvl, ind, kl, current):
	if lvl == 0:
		print(int(kl))
		sys.exit()
	all = 0
	for i in range(lvl + 1):
		all += 2 ** i
	all -= 1
	if ind > 2 ** lvl / 2:
		if current == 1:
			kl += all / 2 + 1
		else:
			kl += 1
			current *= -1
		obx(lvl - 1, ind - 2 ** lvl / 2, kl, current)
	else:
		if current == -1:
			kl += all / 2 + 1
		else:
			kl += 1
			current *= -1
		obx(lvl - 1, ind, kl, current)
main()


(h, n) = input().split(' ')
h = int(h)
n = int(n)
s = 'l'
ans = 0
for i in range(h, 0, -1):
	if n > pow(2, i - 1):
		if s == 'l':
			ans += pow(2, i)
		else:
			ans += 1
		s = 'l'
		n -= pow(2, i - 1)
	else:
		if s == 'r':
			ans += pow(2, i)
		else:
			ans += 1
		s = 'r'
print(ans)


def summ(x):
	ret = 1
	acc = 1
	while acc <= x:
		ret += acc
		acc *= 2
	return ret
(h, n) = list(map(int, input().split()))
ans = 1
lvl = 0
cur = 'L'
amnt = 2 ** h
while 1:
	if lvl == h:
		break
	if cur == 'L':
		if n <= amnt // 2:
			amnt //= 2
			cur = 'R'
			ans += 1
			lvl += 1
		else:
			amnt //= 2
			n -= amnt
			cur = 'L'
			ans += summ(amnt)
			lvl += 1
	elif n <= amnt // 2:
		amnt //= 2
		cur = 'R'
		ans += summ(amnt)
		lvl += 1
	else:
		amnt //= 2
		n -= amnt
		cur = 'L'
		ans += 1
		lvl += 1
print(ans - 1)


(h, n) = map(int, input().split())
(s, k) = (h, 2)
n += (1 << h) - 1
for i in range(h):
	if n & k ^ n << 1 & k == 0:
		s += k - 1
	k <<= 1
print(s)


import os
import sys
from math import *
from collections import *
from fractions import *
from bisect import *
from heapq import *
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def value():
	return tuple(map(int, input().split()))

def array():
	return [int(i) for i in input().split()]

def Int():
	return int(input())

def Str():
	return input()

def arrayS():
	return [i for i in input().split()]
(h, n) = value()
low = 1
high = 2 ** h
ans = 0
move = 0
while low < high:
	mid = low + (high - low) // 2
	if n <= mid:
		if move == 0:
			ans += 1
			move ^= 1
		else:
			ans += 2 ** h
		high = mid
	else:
		if move == 1:
			ans += 1
			move ^= 1
		else:
			ans += 2 ** h
		low = mid + 1
	h -= 1
print(ans)


(h, n) = map(int, input().split())
h += 1
moves = []
result = h - 1
n += 2 ** (h - 1) - 1
while n != 1:
	if n % 2 == 1:
		moves.append(1)
	else:
		moves.append(0)
	n //= 2
index_on_list = 0
ch = 1
while len(moves) > 0:
	if moves[-1] != index_on_list % 2:
		result += 2 ** (h - ch) - 1
	else:
		moves.pop()
		ch += 1
	index_on_list += 1
print(result)


S = input().split()
h = int(S[0])
n = int(S[1]) - 1
ans = 0
di = 0
while h > 0:
	h = h - 1
	if n >> h & 1 ^ di != 0:
		ans = 2 ** (h + 1) + ans
	else:
		ans = ans + 1
		di = di ^ 1
print(ans)


(h, N) = tuple((int(i) for i in input().split()))
L = 1
R = pow(2, h)
mode = 0
level = 0
ans = 0
while L != R:
	M = (L + R) // 2
	if N <= M:
		if mode == 0:
			mode = 1
			ans += 1
		else:
			ans += pow(2, h - level)
		R = M
	else:
		if mode == 0:
			ans += pow(2, h - level)
		else:
			mode = 0
			ans += 1
		L = M + 1
	level += 1
print(ans)


line = input().split()
h = int(line[0])
n = int(line[1])
last = 1
th = 2 ** h
ans = 1
l = 1
r = th
while th > 0:
	mid = (l + r) // 2
	if n <= mid:
		if last == 1:
			ans += 1
		else:
			ans += th
		last = 0
		r = mid
	else:
		if last == 0:
			ans += 1
		else:
			ans += th
		last = 1
		l = mid + 1
	th = th // 2
print(str(ans - 2))


(h, n) = map(int, input().split())
(s, k) = (0, 1 << h - 1)
while k:
	if n > k:
		s += 1 if s & 1 else k << 1
		n -= k
	else:
		s += k << 1 if s & 1 else 1
	k >>= 1
print(s)


(h, n) = map(int, input().split())
N = bin(n - 1)[2:]
N = '0' * (h - len(N)) + N
ans = 0
f = False
for i in range(h):
	if N[i] != ('1' if not f else '0'):
		f = not f
		ans += 1
	else:
		ans += 2 ** (h - i)
print(ans)


(h, n) = map(int, input().split())
ans = h
n = n - 1 + (1 << h)
for i in range(1, h + 1):
	if not (n & 1 << i == 0) ^ (n & 1 << i - 1 == 0):
		ans += (1 << i) - 1
print(ans)


import sys
from math import *
from fractions import gcd
readints = lambda : map(int, input().strip('\n').split())
(h, n) = readints()
path = ''
(lo, hi) = (1, 2 ** h)
while lo != hi:
	mid = (lo + hi) // 2
	if n <= mid:
		path += 'L'
		hi = mid
	else:
		path += 'R'
		lo = mid + 1
ans = 0
cur = 'L'
for i in range(len(path)):
	ans += 1
	if cur != path[i]:
		ans += 2 ** (h - i) - 1
	if path[i] == 'L':
		cur = 'R'
	else:
		cur = 'L'
print(ans)


(h, n) = map(int, input().split(' '))
ans = 0
left = True
for i in range(h):
	ch = h - i
	half = 2 ** (ch - 1)
	if n <= half:
		if left:
			ans += 1
			left = False
			continue
		else:
			ans += half * 2
			left = False
			continue
	elif left:
		ans += half * 2
		left = True
		n -= half
	else:
		ans += 1
		left = True
		n -= half
print(ans)


(h, exit) = map(int, input().split())
vis = 0
isLeft = True
L = 1
mid = 2 ** (h - 1)
R = 2 ** h
while L != R:
	if isLeft:
		if exit >= L and exit <= mid:
			vis += 1
			h -= 1
			R = mid
			mid = (L + R) // 2
		else:
			vis += 2 ** h - 1
	elif exit >= mid + 1 and exit <= R:
		vis += 1
		h -= 1
		L = mid + 1
		mid = (L + R) // 2
	else:
		vis += 2 ** h - 1
	isLeft = not isLeft
print(vis)


(h, n) = map(int, input().split())
t = bin(n - 1)[2:]
t = '0' * (h - len(t)) + t
res = 0
flag = True
for i in range(h):
	if t[i] == ('1' if flag else '0'):
		res += 2 ** (h - i)
	else:
		flag = not flag
		res += 1
print(res)


(h, n) = [int(i) for i in input().split()]
total = 2 ** h
ans = 0
i = 0
(l, r) = (1, 2 ** h)
curr = 0
while i <= h:
	mid = (l + r - 1) // 2
	if i == h - 1:
		if curr == 0:
			if l == n:
				ans += 1
			else:
				ans += 2
		elif l == n:
			ans += 2
		else:
			ans += 1
		break
	if curr == 0:
		if mid < n:
			ans += 2 ** (h - i)
			l = mid + 1
		else:
			ans += 1
			r = mid
			curr = 1
	elif n <= mid:
		ans += 2 ** (h - i)
		r = mid
	else:
		ans += 1
		l = mid + 1
		curr = 0
	i += 1
print(ans)