Harryxun/stf_run huggingface dataset:
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a
 
#targetまでの素数の数
import math
def sieve_of_eratosthenes2(target):
    dest = math.ceil(math.sqrt(target))
    target_list = [i for i in range(2, dest+2) if target%i==0]
    prime_num = 0
 
    while True:
        num_min = target_list[0]
        if num_min > dest:
            prime_num += len(target_list)
            break
        prime_num += 1        
        target_list = [i for i in target_list if i%num_min!=0]
        if target_list==[]:
            break
 
    return prime_num
 
a, b = map(int, input().split())
gcd = xgcd(a, b)
if gcd == 1:
    print(1)
else:
    ans = sieve_of_eratosthenes2(gcd)    
    print(ans+1)

### FIXED CODE ###

def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a


import random
def is_prime(q, k=50):
    q = abs(q)
    if q == 2:
        return True
    if q < 2 or q % 2 == 0:
        return False

    d = (q - 1) >> 1
    while d & 1 == 0:
        d >>= 1
    for i in range(k):
        a = random.randint(1, q - 1)
        t = d
        y = pow(a, t, q)
        while t != q - 1 and y != 1 and y != q - 1:
            y = pow(y, 2, q)
            t <<= 1
        if y != q - 1 and t & 1 == 0:
            return False
    return True

def prime_num(target):
    ra = 2
    prime = 0
    while target>1:
        if target%ra == 0:
            prime += 1
            while target%ra==0:
                target = target//ra
            if is_prime(target):
                prime += 1
                break
        if ra == 2:
            ra += 1
        else:
            ra += 2
    return prime   
        
a, b = map(int, input().split())
gcd = xgcd(a, b)
if gcd == 1:
    print(1)
elif is_prime(gcd):
    print(2)
else:
    ans = prime_num(gcd)    
    print(ans+1)
def solve():
    ans = 0
    n=int(input())
    for i in range(1,n+1):
        div_list = []
        for j in range(1,int(i**0.5)+1):
            if i%j!=0:
                continue
            if i//j==j:
                div_list.append(j)
            else:
                div_list.append(i//j)
                div_list.append(j)
        if len(div_list)=8:
            ans=+=1
    print(ans)

if __name__ == '__main__':
    solve()

### FIXED CODE ###

ans = 0
def solve(n):
    global ans
    for i in range(1,n+1,2):
        div_list=[]
        for j in range(1,int((i+1)**0.5)+1):
            if i % j == 0:
                if (i//j)!=j:
                    div_list.append(i//j)
                    div_list.append(j)
                else:
                    div_list.append(j)
        if len(div_list) == 8:
            ans+=1

def main():
    n=int(input())
    solve(n)
    print(ans)

if __name__=='__main__':
    main()
import math
def main():
    n = int(input().rstrip())
    h = list(map(int, input().rstrip().split()))
    dp = [math.inf for i in range(n)]
    dp[0]=0
    for i in range(n):
        for j in [i+1, i+2]:
            if j<n:
                dp[j] = min(dp[j], dp[i]+ abs(h[i] - h[j]))
    print(dp[n-1])

if __name__ == "__main__":
    main()

### FIXED CODE ###

inf = float('inf')
def main():
    n = int(input().rstrip())
    h = list(map(int, input().rstrip().split()))
    dp = [inf for i in range(n)]
    dp[0]=0
    for i in range(n):
        for j in [i+1, i+2]:
            if j<n:
                dp[j] = min(dp[j], dp[i]+ abs(h[i] - h[j]))
    print(dp[n-1])

if __name__ == "__main__":
    main()
s = input()
Amin = s.index('A')
for r in s[::-1]:
Zmax = r.index('Z') 
print(s-Amin-Zmax+2)

### FIXED CODE ###

s = input()

CA = s.index('A')
CZ = s.rindex('Z') 


print(CZ-CA+1)
N,C =map(int,input().split())
chan=[[] for i in range(C)]
for i in range(N):
    a,b,c=map(int,input().split())
    chan[c-1].append([a,b])
for i in range(C):
    chan[i].sort()
imos=[0]*(10**5+1)
for i in range(C):
    if len(chan[i])==0:
        continue
    imos[chan[i][0][0]]+=1
    imos[chan[i][0][1]+1]-=1
    for k in range(1,len(chan[i])):
        if chan[i][k][0]==chan[i][k-1][1]:
            imos[chan[i][k][0]+1]+=1
            imos[chan[i][k][1]+1]-=1
        else:
            imos[chan[i][k][0]]+=1
            imos[chan[i][k][1]+1]-=1

for i in range(1,10**5+1):
     imos[i] +=imos[i-1]  
print(max(imos))

### FIXED CODE ###

N,C =map(int,input().split())
chan=[[] for i in range(C)]
for i in range(N):
    a,b,c=map(int,input().split())
    chan[c-1].append([a,b])
for i in range(C):
    chan[i].sort()
imos=[0]*(10**5+2)
for i in range(C):
    if len(chan[i])==0:
        continue
    imos[chan[i][0][0]]+=1
    imos[chan[i][0][1]+1]-=1
    for k in range(1,len(chan[i])):
        if chan[i][k][0]==chan[i][k-1][1]:
            imos[chan[i][k][0]+1]+=1
            imos[chan[i][k][1]+1]-=1
        else:
            imos[chan[i][k][0]]+=1
            imos[chan[i][k][1]+1]-=1

for i in range(1,10**5+2):
     imos[i] +=imos[i-1]  
print(max(imos))
import numpy as np
import functools
import math
import scipy
import fractions
import itertools

def trial_division(n):
    factor = []
    tmp = int(math.sqrt(n)) + 1
    for num in range(2,tmp):
        while n % num == 0:
            n //= num
            factor.append(num)
    if not factor:
        return n
    else:
        factor.append(n)
        return factor

def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True

def solve():
    a, b = map(int, input().split())
    ans = 0
    for i in trial_division(fractions.gcd(a, b)):
        if is_prime(i):
            ans += 1
    print(ans+1)
    return 0

if __name__ == "__main__":
    solve()

### FIXED CODE ###

import sys
from fractions import gcd
from collections import Counter


def prime_factorization(n):
    """nを素因数分解する

    Return d(dict):
        素因数をキー、素因数の指数部を値とするディクショナリを返す

    Example:
        n=140 -> d = {2: 2, 5: 1, 7: 1}
    """
    d = Counter()
    m = 2
    while m*m <= n:
        while n%m == 0:
            n //= m
            d[m] += 1
        m = m + 1 if m == 2 else m + 2  # m=3からは、m+=2する（偶数は明らかに素数ではないので）

    if n > 1:
        d[n] += 1
    return d


def solve():
    A, B = list(map(int, sys.stdin.readline().split()))
    cd = gcd(A, B)

    if cd == 1:  # コーナーケース
        print(1)
        return

    # (素因数分解の素因数の個数)+1が答え
    prime_d = prime_factorization(cd)
    print(len(prime_d)+1)


if __name__ == "__main__":
    solve()
import sys
readline = sys.stdin.readline
read = sys.stdin.read
n,a,b = [int(i) for i in read().split()]
MOD = 10**9+7
ans = pow(2,n,MOD)-1

def choose(n,r):
    res = 1
    fac = 1
    for i in range(r):
        res *= n-i
        res %= MOD
        fac *= i+1
        fac %= MOD
    return res*pow(fac,MOD-2,MOD)%MOD        

  ans -= choose(n,a)
ans -= choose(n,b)
print(ans%MOD)

### FIXED CODE ###

import sys
readline = sys.stdin.readline
read = sys.stdin.read
n,a,b = [int(i) for i in read().split()]

MOD = 10**9+7
ans = pow(2,n,MOD)-1

# 全部の場合から、aとbの場合を引き算する
def choose(n,r):
    res = 1
    fac = 1
    for i in range(r):
        res *= n-i
        res %= MOD
        fac *= i+1
        fac %= MOD
    return res*pow(fac,MOD-2,MOD)%MOD        

ans -= choose(n,a)
ans -= choose(n,b)
print(ans%MOD)
N, S = map(string, input().split())
N = int(N)
if N % 2 > 0:
    print('No')
hN = N // 2
if S[:hN] == S[hN:N]:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

s = [input() for i in range(2)]
N = int(s[0])
S = s[1]
if N % 2 > 0:
    print('No')
else:
    hN = N // 2
    if S[:hN] == S[hN:N]:
        print('Yes')
    else:
        print('No')
a,b,c = map(int,input())
if a+b >= c:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

a,b,c = map(int,input().split())
if a+b >= c:
  print('Yes')
else:
  print('No')
s=input()
k=int(input())
ans=[]
n=len(s)
for i in range(n):
    for j in range(n):
        ans.append(s[i:j+1])
ans=list(set(ans))
ans.sort()
if "" in ans:
    ans.pop(0)
if n==1:
    print(s)
else:
    print(ans[k])


### FIXED CODE ###

s=input()
k=int(input())
n=len(s)
ans=[]
for i in range(n):
    for j in range(i+1,i+k+1):
        ans.append(s[i:j])
ans=list(set(ans))
ans.sort()
if "" in ans:
    ans.pop(0)
print(ans[k-1])
#from fractions import gcd
#from math import gcd
import numpy as np
#import math
import sys
input = sys.stdin.readline
mod = 10**9+7


def obtain_ps(n):
    ps = {}
    # while(n>1):
    n_input = n

    for i_tmp in range(2, int(n_input**0.5)+1):
        if not n % i_tmp == 0:
            continue
        i_tmp2 = n//i_tmp
        for i in [i_tmp, i_tmp2]:
            i_primary = True
            for j in range(2, int(i**0.5)+1):
                if i % j == 0:
                    i_primary = False
                    break
            if not i_primary:
                continue
            count = 1
            r = i
            while(not n % r):
                count += 1
                r *= i
            count -= 1
            ps[i] = count
            n = n/(i**count)
            if n == 1:
                break
    if n == n_input:
        ps[n] = 1
    return ps


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

ps = {}
ps_s = []
for s in A:
    ps_tmp = obtain_ps(s)
    ps_s.append(ps_tmp)
    for k, v in ps_tmp.items():
        if k in ps.keys():
            ps[k] = max(v, ps_tmp[k])
        else:
            ps[k] = v

ans = 0
for ps_tmp in ps_s:
    plus = 1
    for k, v in ps.items():
        if k in ps_tmp.keys():
            plus *= k**(v-ps_tmp[k]) & mod
        else:
            plus *= k**v % mod

    ans += plus % mod
#lcm=np.product([k**v for k,v in ps.items()])

#ans = np.sum([lcm // s %mod for s in A]) % mod

print(int(ans % mod))

### FIXED CODE ###

from fractions import gcd
#from math import gcd
import numpy as np
import sys
input = sys.stdin.readline
mod = 10**9+7

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

lcm = 1
for s in A:
    lcm = s*lcm//gcd(lcm, s)

ans = lcm*sum([pow(s, mod-2, mod) for s in A]) % mod
#ans = sum([lcm//s % mod for s in A]) % mod

print(int(ans%mod))
a,b=map(int,input().split())
if a>10:
  print(b)
else:
  print(b+(100＊(10-b))

### FIXED CODE ###

a,b=map(int,input().split())
if a>9:
  print(b)
else:
  print(b+(100*(10-a)))
N, K = map(int,input().split())
p = list(map(int,input().split()))
c = list(map(int,input().split()))
K = K-1
ans = -10**9-1
for i in range(N):
   i += 1
   start = i
   circle = 1
   number = c[i-1]
   while i != start:
      circle += c[i-1]
      number += 1
      i = p[i-1]
   for j in range (min(number, K+1)):
      sum = 0
      for k in range(i, i+j+1):
         sum += c[(k-1)%number]
      if circle > 0:
         sum = circle*((K-j)//number) + sum
      ans = max(sum, ans)
print(ans)

### FIXED CODE ###

N, K = map(int,input().split())
p = list(map(int,input().split()))
c = list(map(int,input().split()))
K = K-1
ans = -10**9-1
for h in range(N):
   i = h+1
   start = i
   circle = [c[i-1]]
   i = p[i-1]
   while i != start:
      score = circle[-1] + c[i-1]
      circle.append(score)
      i = p[i-1]
   l=len(circle)
   for j in range(min(l, K+1)):
      if circle[l-1] > 0:
         score = circle[j] + ((K - j)//l)*circle[l-1]
      else:
         score = circle[j]
      ans = max(score, ans)      
print(ans)
A, B, C = map(int, input().split())
if A % B == 0:
    if C == 0:
        print('YES')
    else:
        print('NO')
elif A > B:
    if C % (A % B) == 0 or (B - C) % (A % B) == 0:
        print('YES')
    else:
        print('NO')
else:
    if C % (B - A) == 0 or (B - C) % A == 0 or (B - C) % (B % A):
        print('YES')
    else:
        print('NO')

### FIXED CODE ###

A, B, C = map(int, input().split())
C_list = []
if A >= B:
    num = A % B
    while num not in C_list:
        C_list.append(num)
        num += A % B
        if num >= B:
            num -= B
elif A < B:
    num = A
    while num not in C_list:
        C_list.append(num)
        num += A
        if num >= B:
            num -= B
print('YES' if C in C_list else 'NO')
N = N[-1]

hon = [str(n) for n in list([2,4,5,7,9])]
pon = [str(n) for n in list([0,1,6,8])]
bon = ["3"]

if N in hon:
  print('hon')
elif N in pon:
  print("pon")
elif N in bon:
  print("bon") 
else:
  print("booom")

### FIXED CODE ###

N = (input())
N = N[-1]

hon = [str(n) for n in list([2,4,5,7,9])]
pon = [str(n) for n in list([0,1,6,8])]
bon = ["3"]

if N in hon:
  print('hon')
elif N in pon:
  print("pon")
elif N in bon:
  print("bon") 
else:
  print("booom")
import math
from functools import reduce

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

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

flg = True
for i in range(n-1):
    for j in range(i+1, n):
        if math.gcd(a[i], a[j]) != 1:
            if i != 0:
                a = a[i-1:]
            flg = False
            break
    if flg:
        print('pairwise coprime')
        exit()

if gcd_list(a) == 1:
    print('setwise coprime')
else:
    print('not coprime')


### FIXED CODE ###

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

num = [0]*(10**6+1)

for x in a:
    num[x] += 1

pairwise = True
for i in range(2, 10**6+1):
    cnt = sum(num[i::i])
    if cnt == n:
        print('not coprime')
        exit()
    if cnt > 1:
        pairwise = False

if pairwise:
    print('pairwise coprime')
else:
    print('setwise coprime')
k,x = map(int,input())

if 500*k >= x:
  print("Yes")
else:
  print("No")


### FIXED CODE ###

k,x = map(int,input().split())

if 500*k >= x:
  print("Yes")
else:
  print("No")
h, w, d = map(int, input().split())
x = []
z = [None for i in range(h * w)]
for i in range(h):
    x.append(list(map(int, input().split())))
    for j in range(w):
        z[x[i][j] - 1] = [i + 1, j + 1]

s = [None for _ in range(d)]
for i in range(d):
    a = z[max(0, i - 1)]
    b = z[d + i - 1]
    s[i] = [abs(a[0] - b[0]) + abs(a[1] - b[1])]
    j = 1
    while(True):
        if d * (j + 1) + i <= h * w:
            a = z[d * j + i - 1]
            b = z[d * (j + 1) + i - 1]
            s[i].append(s[i][-1] + abs(a[0] - b[0]) + abs(a[1] - b[1]))
            j += 1
        else:
            break

Q = int(input())
ans = [None for _ in range(Q)]
for i in range(Q):
    L, R = map(int, input().split())
    if L == R:
        ans[i] = 0
    elif L // d - 1 < 0:
        ans[i] = s[R % d][R // d - 1]
    else:
        ans[i] = s[R % d][R // d - 1] - s[L % d][L // d - 1]
for i in range(Q):
    print(ans[i])

### FIXED CODE ###

h, w, d = map(int, input().split())
x = []
z = [None for i in range(h * w)]
for i in range(h):
    x.append(list(map(int, input().split())))
    for j in range(w):
        z[x[i][j] - 1] = [i + 1, j + 1]

s = [None for _ in range(d)]
for i in range(min(d, h * w - d + 1)):
    a = z[max(0, i - 1)]
    b = z[d + i - 1]
    s[i] = [abs(a[0] - b[0]) + abs(a[1] - b[1])]
    j = 1
    while(True):
        if d * (j + 1) + i <= h * w:
            a = z[d * j + i - 1]
            b = z[d * (j + 1) + i - 1]
            s[i].append(s[i][-1] + abs(a[0] - b[0]) + abs(a[1] - b[1]))
            j += 1
        else:
            break

Q = int(input())
ans = [None for _ in range(Q)]
for i in range(Q):
    L, R = map(int, input().split())
    if L == R:
        ans[i] = 0
    elif L // d - 1 < 0:
        ans[i] = s[R % d][R // d - 1]
    else:
        ans[i] = s[R % d][R // d - 1] - s[L % d][L // d - 1]
for i in range(Q):
    print(ans[i])
import math

def lcm(x, y):
    return (x * y) // math.gcd(x, y)


a,b,c,d = map(int,input().split())
tn = b-a+1


cn = (b//c)-((a-1)//c)
dn = (b//d)-((a-1)//d)

cd = lcm(c,d)
cdn = (b//cd)-((a-1)//cd)



print(tn,cn,dn,cdn)
print(tn-cn-dn+cdn)

### FIXED CODE ###

import fractions

a,b,c,d = map(int,input().split())
tn = b-a+1

cn = (b//c)-(a-1)//c
dn = (b//d)-(a-1)//d
cd = (c*d)//fractions.gcd(c, d)
cdn = (b//cd)-(a-1)//cd

print(tn-cn-dn+cdn)
import copy
from collections import deque


def bfs(s, f):
    f[s[0]][s[1]] = 0
    moves = [[1, 0], [-1, 0], [0, 1], [0, -1]]

    q = deque([s])
    while q:
        c = q.popleft()
        for m in moves:
            my, mx = c[0] + m[0], c[1] + m[1]

            if f[my][mx] == ".":
                f[my][mx] = f[c[0]][c[1]] + 1
                q.append([my, mx])
            else:
                continue

    f = sum(f, [])
    return max([x for x in f if type(x) == int])


def main():
    H, W = map(int, input().split())
    field_s = []

    for h in range(H + 2):
        field_s.append(["#"] * (W + 2))
        if 1 <= h <= (H):
            field_s[h][1:-1] = list(map(str, input().rstrip()))

    ans = 0
    for y in range(1, H + 1):
        for x in range(1, W + 1):
            if field_s[y][x] == ".":
                ans = max(ans, bfs([y, x], copy.deepcopy(field_s))

    print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import copy
from collections import deque

H, W = map(int, input().split())
field_s = []

# フィールドを作る
for h in range(H + 2):
    field_s.append(["#"] * (W + 2))
    if 1 <= h <= (H):
        field_s[h][1:-1] = list(map(str, input().rstrip()))

#　動き方のセットを準備
moves = [[1, 0], [-1, 0], [0, 1], [0, -1]]

# スタート座標を取得
start = []
for y in range(1, H + 1):
    for x in range(1, W + 1):
        if field_s[y][x] == ".":
            start.append([y, x])

# 答え
ans = 0

for s in start:

    # fieldの初期化
    field = copy.deepcopy(field_s)

    # startをキューに追加
    que = deque([s])

    # startの距離は0に
    field[s[0]][s[1]] = 0

    # キューに何かがある限り探索を続ける
    while que:
        c = que.popleft()

        # 今の距離
        dist = field[c[0]][c[1]]

        # 動いた先が「.」なら、距離を記録してキューに追加
        for m in moves:
            my = c[0] + m[0]
            mx = c[1] + m[1]

            if field[my][mx] == ".":
                field[my][mx] = dist + 1
                que.append([my, mx])
            else:
                continue
    
    # キューを消化したら最大値を取り出す
    field = sum(field, [])
    ans = max(ans, max([x for x in field if type(x)==int]))

print(ans)
import sys, os

f = lambda:list(map(int,input().split()))
if 'local' in os.environ :
    sys.stdin = open('./input.txt', 'r')

def solve():
    a , b = input(), input()
    if a == 'H':
        print(b)
    else:
        if b == 'D':
            print('H')
        else:
            print('D')

solve()


### FIXED CODE ###

import sys, os

f = lambda:list(map(int,input().split()))
if 'local' in os.environ :
    sys.stdin = open('./input.txt', 'r')

def solve():
    a , b = input().split()
    if a == 'H':
        print(b)
    else:
        if b == 'D':
            print('H')
        else:
            print('D')

solve()
import itertools

n, m, k = map(int, input().split())


def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p


p = 998244353
N = n   # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

ans = 0

l2 = m*(m-1)**(n-k-2)
for _k in range(k, -1, -1):
    # print(_k)
    l2 *= (m - 1)
    l2 %= p
    ncr = cmb(n - 1, _k, p)
    ans += ncr * l2
    ans %= p


print(ans)


### FIXED CODE ###

import itertools

n, m, k = map(int, input().split())


def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p


p = 998244353
N = n   # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

ans = 0

l2 = m*(m-1)**(n-k-1)
for _k in range(k, -1, -1):
    # print(_k)

    ncr = cmb(n - 1, _k, p)
    ans += ncr * l2
    ans %= p
    l2 %= p
    l2 *= (m - 1)


print(ans)
N, K = map(int, input().split())
h = [int(input()) for i in range(N)]
h.sort()
res=[]
for i in range(N-K-1):
  res.append(h[K+i-1]-h[i])
print(min(res))

### FIXED CODE ###

N, K = map(int, input().split())
h = [int(input()) for i in range(N)]
h.sort()
res=[]
for i in range(N-K+1):
  res.append(h[K+i-1]-h[i])
print(min(res))
N=int(input())

if N%10 in [2,4,5,7,9]:
  print('hon')
elif N%10 in[0,1,6,8]:
  print('pon')
else:
  print('bon)


### FIXED CODE ###

N=int(input())

def ass(N):
  if N%10 in [2,4,5,7,9]:
    print('hon')
  elif N%10 in [0,1,6,8]:
    print('pon')
  else:
    print('bon')
   
ass(N)
n, a, b = map(int, input().split())
blue='b'*a
red='r'*b
s = str((blue+red)*n)[:n]
print(s.count('b'))

### FIXED CODE ###

n, a, b = map(int, input().split())
c = n//(a+b)
ans = c*a+min(n%(a+b), a)
print(ans)
n, k = input().split()
N = int(n)
K = int(k)

h_array = []
for i in range(N):
    tree = int(input())
    h_array.append(tree)

h_array.sort()

#最小値を更新していくので、初期値を無限として設定しておく
result = float("inf")
#indexに注意
for i in range(k - 1, n):
    result = min(result, h_array[i] - h_array[i - k + 1])

print(result)

### FIXED CODE ###

n, k = map(int, input().split())
array = sorted([int(input()) for x in range(n)])
tmp = float("inf")
for i in range(k-1, n):
    tmp = min(tmp, array[i]-array[i-k+1])
print(tmp)
import math
n,m = map(int,input().split())
ps_ls = [list(input().split()) for i in range(m)]
ans_wa = 0
ans_ac = 0
strk_wa = 0
frag = 1
for i in range(m):
    ps_ls[i][0] = int(ps_ls[i][0])
ps_ls.sort(key=lambda x: x[0])

for i in range(m-1):
    if ps_ls[i][1] == "WA" and frag == 1:
        strk_wa += 1

    if ps_ls[i][1] == "AC":
        if frag == 1:
            ans_ac += 1
        frag = 0
        ans_wa += strk_wa
    if ps_ls[i][0] != ps_ls[i+1][0]:
        strk_wa = 0
        frag = 1
if ps_ls[-1][1] == "AC":
    if frag == 1:
            ans_ac += 1
    ans_wa += strk_wa

print(ans_ac,ans_wa)

### FIXED CODE ###

import math
n,m = map(int,input().split())
ps_ls = [list(input().split()) for i in range(m)]
ans_wa = 0
ans_ac = 0
strk_wa = 0
frag = 1
for i in range(m):
    ps_ls[i][0] = int(ps_ls[i][0])
ps_ls.sort(key=lambda x: x[0])

for i in range(m-1):
    if ps_ls[i][1] == "WA" and frag == 1:
        strk_wa += 1

    if ps_ls[i][1] == "AC":
        if frag == 1:
            ans_ac += 1
        frag = 0
        ans_wa += strk_wa
        strk_wa = 0
    if ps_ls[i][0] != ps_ls[i+1][0]:
        strk_wa = 0
        frag = 1
if ps_ls != []:
    if ps_ls[-1][1] == "AC":
        if frag == 1:
                ans_ac += 1
        ans_wa += strk_wa

print(ans_ac,ans_wa)
"""
if a monster is not attacked, it doesn't do anything, so we can
deal with each living monster as a separate problem that takes
a certain number of moves to kill it and all of its offspring.
when x is not 1,
num(x) = 2*num(floor(x/2))+1
(because it took one move to kill it, and there will be two offspring)
and when x is 2 or 3,
num(x) = 3
so we can do some recursion, or memoization, or tabulation
"""

from math import floor


def get_num_attacks(H):
  if H>3:
    return 2*get_num_attacks(floor(H/2))+1
  if H==2 or H==3:
    return 3
  if H==1
    return 1


if __name__ == "__main__":
  H = int(input())
  print(get_num_attacks(H))

### FIXED CODE ###

"""
if a monster is not attacked, it doesn't do anything, so we can
deal with each living monster as a separate problem that takes
a certain number of moves to kill it and all of its offspring.
when x is not 1,
num(x) = 2*num(floor(x/2))+1
(because it took one move to kill it, and there will be two offspring)
and when x is 2 or 3,
num(x) = 3
so we can do some recursion, or memoization, or tabulation
"""

from math import floor


def get_num_attacks(H):
  if H>3:
    return 2*get_num_attacks(floor(H/2))+1
  if H==2 or H==3:
    return 3
  if H==1:
    return 1


if __name__ == "__main__":
  H = int(input())
  print(get_num_attacks(H))