Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

#!/usr/bin/env python
# ワーシャルフロイド+全探索

import numpy as np
import itertools

def main():
    N, M, R = map(int, input().split())
    rs = map(int, input().split())
    inf = float('inf')
    cost = [[inf]*N for _ in range(N)]

    # グラフ作る
    for _ in range(M):
        a, b, c = map(int, input().split())
        cost[a-1][b-1] = c
        cost[b-1][a-1] = c
    
    # ワーシャルフロイドで全頂点間距離算出
    for k in range(N):
        for i in range(N):
            for j in range(N):
                cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])

    # 組み合わせ全探索
    ans = inf
    for route in itertools.permutations(rs):
        d = 0
        for i in range(R-1):
            d += cost[route[i]-1][route[i+1]-1]
        ans = min(ans, d)
    
    print(int(ans))


if __name__=='__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python
# ワーシャルフロイド+全探索

import numpy as np
import itertools

def main():
    N, M, R = map(int, input().split())
    rs = list(map(int, input().split()))
    inf = float('inf')
    cost = [[inf]*N for _ in range(N)]

    # グラフ作る
    for i in range(N):
        cost[i][i] = 0

    for _ in range(M):
        a, b, c = map(int, input().split())
        cost[a-1][b-1] = c
        cost[b-1][a-1] = c
    
    # ワーシャルフロイドで全頂点間距離算出
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if cost[i][k]+cost[k][j] < cost[i][j]:
                    cost[i][j] = cost[i][k] + cost[k][j]

    # 組み合わせ全探索
    ans = inf
    for route in itertools.permutations(rs):
        d = 0
        for i in range(R-1):
            d += cost[route[i]-1][route[i+1]-1]
            if d > ans:
                break
        ans = min(ans, d)
    
    print(int(ans))


if __name__=='__main__':
    main()
### BUGGY CODE ###

import numpy as np
import sys
input = sys.stdin.readline
H,W,K=map(int,input().split())
CO=np.array([[0]*W]*H)
DO=np.array([[0]*W]*H)
for i in range(H):
 C=input()
 for j in range(W):
  DO[i][j]=int(C[j])
F=1000000
for s in range(2**(H-1)):
 D=0
 E=0
 Sui=[0]*(H-1)
 for t in range(H-1):
  if ((s >> t) & 1):
   Sui[t]+=1
 for m in range(H-1):
  E+=Sui[m]
 CO[H-1]=DO[H-1]
 for k in range(H-1):
  if Sui[k]==0:
   CO[H-k-2]=DO[H-k-2]+CO[H-k-1]
   CO[H-k-1]=[0]*W
  else:
   CO[H-k-2]=DO[H-k-2]
 for h in range(W-1):
  if np.amax(CO[:,h])>K:
   E=1000000
   break
  elif np.amax(CO[:,h])<=K and np.amax(np.sum(CO[:,h:h+2],axis=1))>K:
   D+=1
  else:
   CO[:,h+1]=np.sum(CO[:,h:h+2],axis=1)
 if np.amax(CO[:,W-1])>K:
  E=1000000
 if D==0 and E==0:
  F=0
 elif E==0:
  continue
 else:
  F=min(F,D+E)
print(F)

### FIXED CODE ###

import sys
input = sys.stdin.readline
H,W,K=map(int,input().split())
CO=[[0 for i in [0]*W] for j in [0]*H]
DO=[[0 for i in [0]*W] for j in [0]*H]
for i in range(H):
 C=input()
 for j in range(W):
  DO[i][j]=int(C[j])
CO[H-1]=DO[H-1]
F=1000000
for s in range(2**(H-1)):
 D=0
 E=0
 Sui=[0]*(H-1)
 for t in range(H-1):
  if ((s >> t) & 1):
   Sui[t]+=1
 for m in range(H-1):
  E+=Sui[m]
 for k in range(H-1):
  if Sui[k]==0:
   for i in range(W):
    CO[H-k-2][i]=DO[H-k-2][i]+CO[H-k-1][i]
  else:
   for i in range(W):
    CO[H-k-2][i]=DO[H-k-2][i]
 lst=[0]*H
 for h in range(W):
  c=max(CO[x][h] for x in range(H))
  d=max(lst[y]+CO[y][h] for y in range(H))
  if c>K:
   E=1000000
   break
  elif d>K:
   D+=1
   lst=[0]*H
  for z in range(H):
   lst[z]+=CO[z][h]
 F=min(F,D+E)
print(F)
### BUGGY CODE ###

x, y, a, b, c = map(int,input().split())
red = sorted(list(map(int,input().split())))[a-x:]
green = sorted(list(map(int,input().split())))[b-y:]
white = sorted(list(map(int,input().split())))
rcnt = 0
gcnt = 0
ans = 0
#print(red,green,white)

for i in range(x+y):
#    print(red,green,white)    
    if red[-1] == max(red[-1],green[-1],white[-1]):
#        print('hoge')
        rcnt += 1
        ans += red.pop(-1)
        if len(red) == 0:
            red = [0]
    elif green[-1] == max(red[-1],green[-1],white[-1]):
#        print('huga')
        gcnt += 1
        ans += green.pop(-1)
        if len(green) == 0:
            green = [0]
    else:
        if red[0] < green[0]:
            rcnt += 1
            red.pop(0)
            if len(red) == 0:
                red = [0]
        else:
            gcnt += 1
            green.pop(0)
            if len(green) == 0:
                green = [0]
#        print('foo')
        ans += white.pop(-1)
        if len(white) == 0:
            white = [0]


print(ans)

### FIXED CODE ###

x, y, a, b, c = map(int,input().split())
red = sorted(list(map(int,input().split())),reverse=True)[:x]
green = sorted(list(map(int,input().split())),reverse=True)[:y]
white = sorted(list(map(int,input().split())),reverse=True)

l = sorted(red+green+white,reverse=True)[:x+y]
print(sum(l))
### BUGGY CODE ###

n,q = [int(x) for x in input().split()]
s = input()
lst = []
for _ in range(q):
    l,r = [int(x) for x in input().split()]
    lst.append([l,r])

a_lst = [x for x in range(n) if s[x] == "A"]
cnt = 0
for i in range(q):
    for x in a_lst:
        if lst[i][0]-1 <= x and lst[i][1] > x+1:
            if s[x+1] == "C":
                cnt += 1
    print(cnt)
    cnt = 0

### FIXED CODE ###

n,q = [int(x) for x in input().split()]
s = input()

t = [0]*(n+1)
for i in range(n):
    t[i+1] = t[i] + (1 if s[i:i+2] == "AC" else 0)

for _ in range(q):
    l,r = [int(x) for x in input().split()]
    print(t[r-1]-t[l-1])
### BUGGY CODE ###

def main():
    # n:人数, a:身長リスト
    n = int(input())
    a = list(map(int, input().split()))
    # Li=i+Ai, Ri=i-Aiを満たすL,Rを作成
    L = [(i+a[i]) for i in range(n)]
    R = [(i-a[i]) for i in range(n)]
    # Li=X=Rj,i<jを満たす組が存在する時count+=1
    count = 0
    for i,Li in enumerate(L):
        if (Li in R):
            j_list = [idx for idx,x in enumerate(R) if i<idx and x==Li]
            for j in j_list:
                 count+=1
    print(count)

main()


### FIXED CODE ###

from collections import Counter

def main():
    # n:人数, a:身長リスト
    n = int(input())
    a = list(map(int, input().split()))
    # Li=i+Ai, Ri=i-Aiを満たすL,Rを作成
    L = [0]*n
    R = [0]*n
    for i,ai in enumerate(a):
        L[i] = i+ai
        R[i] = i-ai
    # Li=X=Rj,i<jを満たす組が存在する時count+=1
    count = 0
    c = Counter(R)
    for Li in L:
        count += c.get(Li,0)

    print(count)

main()
### BUGGY CODE ###

s = input()
q = int(input())

for i in range(q):
  query = input()
  if query[0] == '1':
    s = s[::-1]
  elif query[2] == '1':
    s = query[4] + s
  else:
    s  = s + query[4]
print(s)

### FIXED CODE ###

s = input()
q = int(input())

cnt_reverse = False
left = ''
for i in range(q):
  query = input()
  
  if query[0] == '1':
    cnt_reverse = not cnt_reverse
  elif (query[2] == '1' and not cnt_reverse) or (query[2] == '2' and cnt_reverse):
    left = left + query[4]

  else:
    s  = s + query[4]
s = left[::-1] + s
if cnt_reverse:
  s = s[::-1]
print(s)
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
cnt=0
for i in range(n):
  c=0
  while l[i]!=1:
    if l[i]%2==0:
      l[i]=l[i]//2
      c+=1
  cnt+=c
print(cnt)

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
cnt=0
for i in range(n):
  c=0
  while l[i]%2==0:
    l[i]=l[i]//2
    c+=1
  cnt+=c
print(cnt)
### BUGGY CODE ###

def bellmanford(xyw, n, start):
    """2次元配列[[x,y,weight]...], n, start(開始位置)を受け取る"""
    inf = float("inf")
    dist = [inf]*(n+1)
    dist[start] = 0

    for _ in range(n-1):
        for x,y,w in xyw:
            if dist[x] == inf:
                continue
            if dist[y] > dist[x] + w:
                dist[y] = dist[x] + w
    result = dist[n-1]
    negative = [0]*n
    for _ in range(n):
        for x, y, w in xyw:
            if dist[x] == inf:
                continue
            if dist[y] > dist[x] + w:
                dist[y] = dist[x] + w
                negative[y] = True
            if negative[x]:
                negative[y] = True
    return inf if negative[n-1] else -result


N, M = map(int, input().split())
ABC = (map(int, input().split()) for i in range(M))
ABC = [(a-1,b-1,-c) for a,b,c in ABC]

print(bellmanford(ABC, N, 0))


### FIXED CODE ###

def bellmanford(xyw, n, start):
    inf = float("inf")
    dist = [inf]*n
    dist[start] = 0

    for _ in range(n-1):
        for x,y,w in xyw:
            if dist[x] == inf:
                continue
            if dist[y] > dist[x] + w:
                dist[y] = dist[x] + w
    result = dist[n-1]
    negative = [0]*n
    for _ in range(n):
        for x, y, w in xyw:
            if dist[x] == inf:
                continue
            if dist[y] > dist[x] + w:
                dist[y] = dist[x] + w
                negative[y] = True
            if negative[x]:
                negative[y] = True
    return inf if negative[n-1] else -result


N, M = map(int, input().split())
ABC = (map(int, input().split()) for i in range(M))
ABC = [(a-1,b-1,-c) for a,b,c in ABC]

print(bellmanford(ABC, N, 0))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2, r + 1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p - 1, r, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

n = int(input())
al = list(map(int, input().split()))
al_cnt = [0] * (n + 1)

for i in range(1, n + 1):
    al_cnt[i] = al.count(i)
max_cnt = 0

for j in range(1, n + 1):
    if al_cnt[j] >= 2:
        max_cnt += cmb(al_cnt[j], 2)

for l in range(n):
    if al_cnt[al[l]] >= 3:
        ans = max_cnt - cmb(al_cnt[al[l]], 2) + cmb(al_cnt[al[l]] - 1, 2)
        print(ans if ans > 0 else 0)
    else:
        ans = max_cnt - cmb(al_cnt[al[l]], 2)
        print(ans if ans > 0 else 0)



### FIXED CODE ###

from collections import Counter

n = int(input())
al = list(map(int, input().split()))
al_cnt = Counter(al)
ans = sum([i * (i - 1) // 2 for i in al_cnt.values()])
for j in al:
    print(ans - al_cnt[j] + 1)
### BUGGY CODE ###

n,m=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(m)]

r=[[]*n for _ in range(n)]
f=[True]*n
d=[0]
b=[n+1]*n

for i in a:
    r[i[0]-1].append(i[1]-1)
    r[i[1]-1].append(i[0]-1)

o=0
#print(r[now][0])

b[o]=0
#print(now)
for _ in range(n):
    for i in r[o]:
        #i=r[now][j]
        if(b[i]==n+1):
            b[i]=o
            d.append(i)
    if(d):
        o=d[0]
        del d[0]

f=0
for i in b[1:]:
    if(i==n+1):
        f=1
if (f==0):
    print("Yes")
    for i in b[1:]:
        print(i+1)
else:
    print("No")

    

### FIXED CODE ###

from collections import deque
n,m=map(int,input().split())

r=[[] for _ in range(n)]
d=deque()
b=[n+1]*n
for _ in range(m):
    a,z=map(int,input().split())
    r[a-1].append(z-1)
    r[z-1].append(a-1)

o=0
f=1
b[o]=0
for _ in range(n):
    for i in r[o]:
        if(b[i]==n+1):
            b[i]=o
            d.append(i)
    if(d):
        o=d.popleft()
        f+=1
    else:
        break

if (f==n):
    print("Yes")
    for i in b[1:]:
        print(i+1)
else:
    print("No")
### BUGGY CODE ###

import numpy as np

N = int(input())
X = np.array([int(n) for n in input().split()])
iX = np.argsort(X)
sX = X[iX]

A = [0] * N

for i in range(N):
    L = np.concatenate([sX[:i], sX[i+1:]])
    A[iX[i]] = L[(N-2)//2]

for a in A:
    print(a)


### FIXED CODE ###

import numpy as np

N = int(input())
X = np.array([int(n) for n in input().split()])
iX = np.argsort(X)
sX = X[iX]

A = [0] * N

for i in range(N):
    if i < N // 2:
        ans = sX[N//2]
    else:
        ans = sX[(N-2)//2]
    A[iX[i]] = ans

for a in A:
    print(a)
### BUGGY CODE ###

h,w,m=list(map(int, input("").split()))
l=[]
out=0
o=0
hb=[]
wb=[]
for i in range(h):
    hb.append([0,i+1])
for i in range(w):
    wb.append([0,i+1])

bo=[]
for i in range(m):
    a,b=list(map(int, input("").split()))
    hb[a-1][0]+=1
    wb[b-1][0]+=1
    bo.append([a,b])
hb.sort()
wb.sort()
for i in hb:
    for j in wb:
        o=i[0]+j[0]
        if [i[1],j[1]] in bo:
            o-=1
        #print([i[1],j[1]] ,o)
        if o>out:
            out=o
print(out)


### FIXED CODE ###

h,w,m=list(map(int, input("").split()))
bo=[]
hb=[0]*h
wb=[0]*w
for i in range(m):
    a,b=list(map(int, input("").split()))
    #各行列に爆弾いくつあるか
    hb[a-1]+=1
    wb[b-1]+=1
    #爆弾の座標
    bo.append([a,b])
#ソート
mwb=[]
mhb=[]
#爆弾数が最大の行と列番号をメモ
hmax=max(hb)
wmax=max(wb)
for i in range(h):
    if hb[i]==hmax:
        mhb.append(i)
for i in range(w):
    if wb[i]==wmax:
        mwb.append(i)
c=0
#最大の爆弾数の行と列に含まれる爆弾数=cの確認
for h,w in bo:
     #h in mhb and w in mwb
    if(hb[h-1] == hmax and wb[w-1] == wmax):
        c+=1
#行と列の最大爆弾数の和
out=hmax+wmax
#行と列の最大数の積がcと一致するなら必ず重複があるので－1
if c==len(mwb)*len(mhb):
    out-=1
print(out)
### BUGGY CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

def factorization(n):
    primen, degree, primend = [], [], {}
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            primen.append(i)
            degree.append(cnt)
            primend[i] = cnt
    if temp!=1:
        primen.append(temp)
        degree.append(1)
        primend[temp] = 1
    if primen==[]:
        primen.append(n)
        degree.append(1)
        primend[n] = 1
    return degree

def main():
    N = int(input())
    ret = 0
    for i in range(1,N+1):
        x = factorization(i)
        cnt = 1
        for xx in x:
            cnt*=(xx+1)
        ret += i * cnt

    print(ret-1)

if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

def main():
    N = int(input())
    ret = 0
    for i in range(1,N+1):
        x = (N//i)
        ret += x*(x+1)*i//2
    print(ret)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

N,Y = list(map(int,input().split()))

for x in range(0,Y//10000+1):
    for y in range(0,(Y-x*10000)//5000+1):
        if (Y-x*10000-y*5000)%1000 == 0 and Y-x*10000-y*5000 >= 0:
            if x+y+(Y-x*10000-y*5000)//1000 == N:
                print(x,y,(Y-x*10000-y*5000)//1000)
                exit()
            
print(-1,-1,-1)

### FIXED CODE ###

N,Y = list(map(int,input().split()))

for x in range(0,N+1):
    for y in range(0,N+1-x):
        if (Y-x*10000-y*5000)%1000 == 0 and Y-x*10000-y*5000 >= 0:
            if x+y+(Y-x*10000-y*5000)//1000 == N:
                print(x,y,(Y-x*10000-y*5000)//1000)
                exit()
            
print(-1,-1,-1)
### BUGGY CODE ###

N=int(input())
l=[]
for h in range(N):
    s=input()
    if s not in l:
        l.append(s)
print(len(l))



### FIXED CODE ###

N=int(input())
S=[input() for _ in range(N)]
print(len(set(S)))
### BUGGY CODE ###

import sys

# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
import heapq
import decimal
# import statistics
import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n = ni()
    s = input()

    c = collections.Counter(s)

    ans = 0
    for i in range(1, n + 1):
        for t in itertools.combinations(c.keys(), i):
            tmp = 1
            for ti in t:
                tmp *= c[ti] % MOD
            ans += tmp
            ans %= MOD

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
import heapq
import decimal
# import statistics
import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n = ni()
    s = input()

    c = collections.Counter(s)

    ans = 1
    for v in c.values():
        ans *= v + 1
        ans %= MOD
    ans = (ans - 1) % MOD
    print(ans)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

# 以下ペースト可
# start 21:14
a, b = [int(item) for item in input().split()]

if b > a:
    c = a
    a = b
    b = c


# 最大公約数を求める
def gcd(a, b):
    while b > 1:
        a, b = b, a%b
    return a

# 公約数でかつ素数の_listを求める
prime_devisor_list = [1]

import math

def is_prime(num):
    if num in [1, 2]:
        return True
    else:
        for i in range(2, int(math.sqrt(num)) + 1):
            if num % i == 0:
                return False
        return True

for i in range(2, gcd(a, b)+1):
    if a % i == 0 and b % i == 0:
        # i can be ans
        # check pirme

        if is_prime(i):
            prime_devisor_list.append(i)

# 数をこたえる
print(len(prime_devisor_list))


### FIXED CODE ###

# start 21:14
a, b = [int(item) for item in input().split()]

# 素因数リスト
import math
def factor(num):
    divisor_list = [1]
    divisor = 2
    max_prime = int(math.sqrt(num))
    while max_prime >= divisor:
        if num % divisor == 0:
            divisor_list.append(divisor)
            num //= divisor

        else:
            divisor += 1
    divisor_list.append(num)
    return divisor_list

def gcd(a, b):
    if b == 0: return a
    return gcd(b, a % b)

cd_list = set(factor(gcd(a, b)))

print(len(cd_list))
### BUGGY CODE ###

N = int(input())
print(sum(range(N)))

### FIXED CODE ###

N = int(input())
print(((N-1)*N)//2)
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))

l = [0 for j in range(0, m)]
l[0] = 1
s = 0
ans = 0

for i in range(0, n):
    s += a[i]
    ans += l[s%m]
    l[s%m] += 1

print(ans)

### FIXED CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))

d = {0: 1}
s = 0
ans = 0

for i in range(0, n):
    s += a[i]
    if s%m in d:
        d[s%m] += 1
    else:
        d[s%m] = 1
    ans += d[s%m]-1

print(ans)
### BUGGY CODE ###

import collections
N,M,Q = map(int,(input().split()))
s = [[0]*(N+1) for _ in range(N+1)]
L = [0]*M
d = collections.defaultdict(int)
for i in range(M):
    L,R = map(int,(input().split()))
    d[(L,R)] += 1
for i in range(1,N+1):
    for j in range(1,N+1):
        s[i][j] = s[i][j-1] + d[(i,j)]
for i in range(Q):
    p,q = map(int,(input().split()))
    ans = 0
    for j in range(p,q+1):
        ans += s[j][q]-s[j][p-1]
    print(ans)

### FIXED CODE ###

import bisect
import collections
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
MOD = 10**9+7

N,M,Q = map(int,(input().split()))
s = [[0]*(N+1) for _ in range(N+1)]
L = [0]*M
d = defaultdict(int)
for i in range(M):
    L,R = map(int,(input().split()))
    d[(L,R)] += 1
for i in range(1,N+1):
    for j in range(1,N+1):
        s[i][j] = s[i][j-1] + d[(i,j)]
for i in range(Q):
    p,q = map(int,(input().split()))
    ans = 0
    for j in range(p,q+1):
        ans += s[j][q]-s[j][p-1]
    print(ans)
### BUGGY CODE ###

S = input()
n = len(S)
count = 0
mod = 0
mods = [0] * 2019
mods[0] = 1
x = 1
for s in reversed(S):
    mod = (mod + (int(s) * x)) % 2019
    mods[mod] = mods[mod] + 1
    x = x * 10

for v in mods:
    count = count + v*(v-1)//2

print(count)


### FIXED CODE ###

reverse_S = input()[::-1]
n = len(reverse_S)
count = 0
mod = 0
mods = [0] * 2019
mods[0] = 1
x = 1
for s in reverse_S:
    mod = (mod + (int(s) * x)) % 2019
    mods[mod] = mods[mod] + 1
    x = x * 10
    x = x % 2019

for v in mods:
    count = count + v*(v-1)//2

print(count)
### BUGGY CODE ###

import sys
N, X = map(int, input().split())
sys.setrecursionlimit(1000000000)


def dfs(level, idx, cnt_p):
    if X == idx+1:
        return 0
    elif X < 2**(level+1)-3+2:
        return cnt_p + dfs(level-1, idx+1, cnt_p)
    elif X == 2**(level+1)-3+2:
        return 2**(level)-1 + 1
    else:
        return cnt_p + 2**(level)-1 + 1 + dfs(level-1, idx+2**(level+1)-2, cnt_p)


ans = dfs(N, 0, 0)
print(ans)


### FIXED CODE ###

N,X = map(int, input().split())

a,p = [1],[1]
for i in range(N):
    a.append(a[i]*2+3)
    p.append(p[i]*2+1)

def f(n,x):
    if n==0:
        return 1 if x>=1 else 0
    if x==1:
        return 0
    elif x<=1+a[n-1]:
        return f(n-1, x-1)
    else:
        return p[n-1]+1+f(n-1, x-2-a[n-1])
    
print(f(N,X))
### BUGGY CODE ###

N,M = map(int,input().split())
XY = []
for i in range(M):
    xy = list(map(int,input().split()))
    XY.append(xy)
p = [i+1 for i in range(N)]
ans = []
stack = []
alr = []
xy1 = []
for xy in XY:
    xy1.append(xy[1])
for i in range(1,N+1):
    if i not in xy1:
        stack.append(i)
        alr.append(i)

while len(stack) > 0:
    p1 = stack.pop(-1)
    flag = True
    for xy in XY:
        if p1 == xy[0]:
            alr.append(xy[1])
            stack.append(xy[1])
        if (p1 == xy[1]) and (xy[0] not in ans):
            flag = False
    if flag:
        ans.append(p1)

    
dp = [0 for i in range(len(ans))]

for i in range(len(ans)):
    for j in range(i):
        if [ans[j],ans[i]] in XY:
            dp[i] = max(dp[i],dp[j]+1)


print(max(dp))        


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**5+10)
input = sys.stdin.readline

N,M = map(int,input().split())
XY = [[] for m in range(N)]
for l in range(M):
    x,y = map(int,input().split())
    XY[x-1].append(y-1)

dp = [-1 for k in range(N)]
def search(i):
    if dp[i] != -1:
        return dp[i]
    c = 0
    start = XY[i]
    for s in start:
        c = max(c,search(s)+1)
    dp[i] = c
    return dp[i]

a = 0
for i in range(N):
    a = max(a,search(i))
print(a)
### BUGGY CODE ###

from collections import deque

n = int(input())

to_battle_with = [deque(map(int, input().split())) for _ in range(n)]

for i in range(n):
    for j in range(n - 1):
        to_battle_with[i][j] -= 1

day_count = 0
remained_battles = (n * (n - 1)) // 2

while remained_battles:
    battled_today = set()

    no_battle_today = True
    for player in range(n):
        if not to_battle_with[player]:
            continue

        next_opponent = to_battle_with[player][0]
        if player in battled_today or next_opponent in battled_today:
            continue

        if not to_battle_with[next_opponent]:
            continue

        if to_battle_with[next_opponent][0] == player:
            battled_today.add(next_opponent)
            battled_today.add(player)
            to_battle_with[player].popleft()
            to_battle_with[next_opponent].popleft()
            remained_battles -= 1
            no_battle_today = False
    if no_battle_today:
        print(-1)
        break
    day_count += 1

if not no_battle_today:
    print(day_count)


### FIXED CODE ###

import sys
from collections import deque

input = sys.stdin.readline

n = int(input())

to_battle_with = [deque([i - 1 for i in map(int, input().split())]) for _ in range(n)]


def update_battle(player, battle_set, to_battle_with):
    if not to_battle_with[player]:
        return
    next_opponent = to_battle_with[player][0]
    if not to_battle_with[next_opponent]:
        return
    if to_battle_with[next_opponent][0] == player:
        if player > next_opponent:
            player, next_opponent = next_opponent, player
        battle_set.add((player, next_opponent))


battles_today = set()
for player in range(n):
    update_battle(player, battles_today, to_battle_with)

day_count = 0
battle_count = 0
num_all_battles = (n * (n - 1)) // 2

while battles_today:
    battles_tomorrow = set()
    for p1, p2 in battles_today:
        battle_count += 1
        to_battle_with[p1].popleft()
        to_battle_with[p2].popleft()
        for p in [p1, p2]:
            update_battle(p, battles_tomorrow, to_battle_with)
    battles_today = battles_tomorrow
    day_count += 1

if battle_count == num_all_battles:
    print(day_count)
else:
    print(-1)