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

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n = inp()
s = input()
res = 0
for num in itertools.product(range(10), repeat=3):
    p = 0
    for i in range(n):
        if int(s[i]) == num[p]:
            p += 1
            if p == 3:
                res += 1
                break
print(res)

### FIXED CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n = inp()
s = input()
res = 0
a = [str(i) for i in range(10)]
for num in itertools.product(a, repeat=3):
    p = 0
    for i,j in enumerate(s):
        if j == num[p]:
            p += 1
            if p == 3:
                break
    if p == 3:
        res += 1
print(res)
### BUGGY CODE ###

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

N = int(input())
ans = 0

for i in range(1,N+1):
    a = make_divisors(i)
    a = len(a)
    ans += i * a 
    #print(i*a)

print(ans)

### FIXED CODE ###

import math
n = int(input())
ans = 0

for i in range(1,n+1):
    N = math.floor(n / i)
    l = i * N
    s = N / 2 * (i + l)
    ans += s

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

n,m = map(int,input().split())
a = list(map(int,input().split()))
for i in range(m):
  a.sort()
  a[a.index(max(a))]//=2
print(sum(a))

### FIXED CODE ###

from heapq import *
n,m = map(int,input().split())
a = list(map(lambda x:-int(x),input().split()))
heapify(a)
for i in range(m):
  heappush(a,-(-heappop(a)//2))
print(-sum(a))
### BUGGY CODE ###

N = int(input())
p = list(map(float, input().split()))

dp = [[0]*(N+1) for _ in range(N+1)]# dp[i][j]: i枚目まで投げた時, j枚表になってる確率.(i枚の選び方によって変わらん?(dp[N][:]だけみるから途中はどんな順番でもいいってこと？))
dp[0][0] = 1 # 0枚投げた時は, 0枚が表っていう事象しかあり得ない.(dp[0][0]=1で,dp[0][1:]=0)

for i in range(1, N+1):
  for j in range(0, N+1):
    if j - 1 < 0:
      dp[i][j] = dp[i-1][j]*(1-p[i-1])
    else:
      dp[i][j] = (dp[i-1][j-1]*p[i-1]) + (dp[i-1][j]*(1-p[i-1]))

if N % 2==0:
  ans = sum(dp[N][int(N/2):])
else:
  ans = sum(dp[N][int(N//2)+1:])

print(ans)





    

### FIXED CODE ###

N = int(input())
p = list(map(float, input().split()))

dp = [[0]*(N+1) for _ in range(N+1)]# dp[i][j]: i枚目まで投げた時, j枚表になってる確率.(i枚の選び方によって変わらん?(dp[N][:]だけみるから途中はどんな順番でもいいってこと？))
dp[0][0] = 1 # 0枚投げた時は, 0枚が表っていう事象しかあり得ない.(dp[0][0]=1で,dp[0][1:]=0)

for i in range(1, N+1):
  for j in range(0, N+1):
    if j - 1 < 0:
      dp[i][j] = dp[i-1][j]*(1-p[i-1])
    else:
      dp[i][j] = (dp[i-1][j-1]*p[i-1]) + (dp[i-1][j]*(1-p[i-1]))

if N % 2==0:
  ans = sum(dp[N][int(N/2):])
else:
  ans = sum(dp[N][int(N//2)+1:])

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

n = int(input())
a = list(map(int, input().split()))
q = int(input())
for i in range(q):
    b, c = map(int,input().split()) 
    while b in a:
        s = a.index(b)
        a[s] = c

    print(sum(a))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
q = int(input())
dic = [0 for _ in range(10 ** 5 + 1)]
count = 0
for i in a:
    dic[i] += 1
    count += i

for i in range(q):
    b, c = map(int,input().split())
    count -= b * dic[b]
    dic[c] += dic[b]
    count += c * dic[b]
    dic[b] = 0
    print(count)
### BUGGY CODE ###

#!/usr/bin/env python3
from collections import defaultdict
n=int(input())
s=input()
count=0
for le in range(1,n-1):
    mojiretu=defaultdict(int)
    for i in range(n-le+1):
        j=i+le
        if mojiretu[s[i:j]]:
            if mojiretu[s[i:j]]<=i:
                count=max(count,j-i)
        else:mojiretu[s[i:j]]=j
# while True:
#     for i in range(n)
print(count)


### FIXED CODE ###

N=int(input())
S=input()

class RollingHash():
    BASE1 = 1007
    BASE2 = 2009
    MOD1 = 1000000007
    MOD2 = 1000000009
 
    def __init__(self, s, opt=2):
        self.n = len(s)
        self.opt = opt
        self.hash1 = [0] * (self.n + 1)
        self.power1 = [1] * (self.n + 1)
        if opt == 2:
            self.hash2 = [0] * (self.n + 1)
            self.power2 = [1] * (self.n + 1)
        for i, e in enumerate(s):
            self.hash1[i + 1] = (self.hash1[i] * self.__class__.BASE1 + ord(e)) % self.__class__.MOD1
            self.power1[i + 1] = (self.power1[i] * self.__class__.BASE1) % self.__class__.MOD1
            if opt == 2:
                self.hash2[i + 1] = (self.hash2[i] * self.__class__.BASE2 + ord(e)) % self.__class__.MOD2
                self.power2[i + 1] = (self.power2[i] * self.__class__.BASE2) % self.__class__.MOD2
 
    def get(self, l: int, r: int):
        res1 = self.hash1[r] - self.hash1[l] * self.power1[r - l] % self.__class__.MOD1
        if(res1 < 0):
            res1 += self.__class__.MOD1
        if self.opt == 2:
            res2 = self.hash2[r] - self.hash2[l] * self.power2[r - l] % self.__class__.MOD2
            if(res2 < 0):
                res2 += self.__class__.MOD2
        return (res1, res2) if self.opt == 2 else res1


    
rh = RollingHash(S, opt=1)

def check(n: int):
    d = dict()
    for i in range(N - n + 1):
        p = rh.get(i, i + n)
        if p in d.keys():
            if(i - d[p] >= n):
                return True
        else:
            d[p] = i
    return False
    
ok, ng = 0, N // 2 + 1
while ng - ok > 1:
    mid = (ok + ng) // 2
    if check(mid):
        ok = mid
    else:
        ng = mid
print(ok)
### BUGGY CODE ###

N = int(input())
T = [[] for i in range(N+1)]
for _ in range(N-1):
    a, b, c = map(int, input().split())
    T[a].append([b,c])
    T[b].append([a,c])

Q, K = map(int, input().split())
shortest_path = [0 for _ in range(N+1)]
V, queue = set([K]), T[K]
while len(queue) > 0:
    v = queue.pop(0)
    shortest_path[v[0]] = v[1]
    for u in T[v[0]]:
        if u[0] not in V:
            queue.append([u[0], u[1] + v[1]])
    V.add(v[0])

for _ in range(Q):
    x, y = map(int, input().split())
    print(shortest_path[x] + shortest_path[y])

### FIXED CODE ###

from collections import deque

N = int(input())
T = [{} for i in range(N+1)]
for _ in range(N-1):
    a, b, c = map(int, input().split())
    T[a][b] = c
    T[b][a] = c

Q, K = map(int, input().split())
shortest_path = [0 for _ in range(N+1)]
queue = deque([[v, T[K][v], K] for v in T[K].keys()])
for _ in range(N-1):
    v = queue.popleft()
    shortest_path[v[0]] = v[1]
    queue.extend([[u, T[v[0]][u] + v[1], v[0]] for u in T[v[0]].keys() if u != v[2]])

for _ in range(Q):
    x, y = map(int, input().split())
    print(shortest_path[x] + shortest_path[y])
### BUGGY CODE ###

a,b,x =map( int, input().split() )

cnt = 0
for i in range(a,b+1):
	if i % x == 0:
		cnt += 1

print(cnt)

### FIXED CODE ###

a,b,x =map( int, input().split() )

cnt = 0

start  = ( a - 1) // x
end = b// x 

print(end - start)
### BUGGY CODE ###

n, k = map(int, input().split())
p = [0] + list(map(int, input().split()))
c = [0] + list(map(int, input().split()))

score_cnt = [None] * (n + 1)
for i in range(1, n + 1):
    now = i
    cnt = 0
    score = 0
    for _ in range(n):
        now = p[now]
        score += c[now]
        cnt += 1
        if now == i:
            score_cnt[i] = [score, cnt]
            break

ans = - 10 ** 20
for i in range(1, n + 1):
    now = i
    score = 0
    left = k
    for j in range(n):
        now = p[now]
        score += c[now]
        left -= 1
        if left >= 0:
            times = left // score_cnt[now][1]
            score_loop = score + times * score_cnt[now][0]
            ans = max(ans, score, score_loop)

print(ans)


### FIXED CODE ###

n, k = map(int, input().split())
p = [0] + list(map(int, input().split()))
c = [0] + list(map(int, input().split()))

score_cnt = [None] * (n + 1)
for i in range(1, n + 1):
    now = i
    cnt = 0
    score = 0
    for _ in range(n):
        now = p[now]
        score += c[now]
        cnt += 1
        if now == i:
            score_cnt[i] = [score, cnt]
            break

ans = - 10 ** 20
for i in range(1, n + 1):
    now = i
    score = 0
    left = k
    for j in range(n):
        now = p[now]
        score += c[now]
        left -= 1
        if left >= 0:
            times = left // score_cnt[now][1]
            score_loop = score + times * score_cnt[now][0]
            ans = max(ans, score, score_loop)

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

n, k = map(int, input().split())
pb = 0
count = 0
if n >= k:
  pb += (n-k+1)/n
  count = k - 1
else:
  count = n
 
for i in range(1, count+1):
  mul = 0
  while k > i ** mul:
    mul += 1
  pb = pb +  (1/n) * (1 / (2**mul))
print(pb)

### FIXED CODE ###

n, k = map(int, input().split())
pb = 0
 
for i in range(1, n+1):
  mul = 0
  
  while k > i * (2 ** mul):
    mul += 1
    
  pb += 1/(n*(2**mul))
print(pb)
### BUGGY CODE ###

#!/usr/bin/python3.6
import sys
input = sys.stdin.readline
INF = 10**9

s = input().rstrip()[::-1]
n = len(s)
# DP[i-th item][0:pay just / 1:pay over]
dp = [[INF] * 2 for _ in range(n + 1)] 
dp[0][0] = 0

for i, ch in enumerate(s):
    a = int(ch)
    dp[i+1][0] = min(dp[i+1][0], dp[i][0] + a)
    dp[i+1][0] = min(dp[i+1][0], dp[i][1] + a)
    dp[i+1][1] = min(dp[i+1][1], dp[i][0] + 10 - a + 1)
    dp[i+1][1] = min(dp[i+1][1], dp[i][1] + 10 - a - 1)

print(min(dp[n]))

### FIXED CODE ###

#!/usr/bin/python3.6
import sys
input = sys.stdin.readline
INF = 10**9

a = [int(item) for item in list(input().rstrip())]
n = len(a)
# DP[i-th item][0:pay just / 1:pay over]
dp = [[INF] * 2 for _ in range(n + 1)] 
dp[0][0] = 0

for i, item in enumerate(a):
    dp[i+1][0] = min(dp[i+1][0], dp[i][0] + item, dp[i][1] + item)
    dp[i+1][1] = min(dp[i+1][1], dp[i][0] + 10 - item + 1, dp[i][1] + 10 - item - 1)

print(min(dp[n]))
### BUGGY CODE ###

# classを使うのをやめてlistで実施する
# dfsを再帰でなくstackを用いて書く
from collections import deque
import sys
input = sys.stdin.readline

def dfs():
    stk1 = deque([0])
    stk2 = deque([])
    while stk1:
        v = stk1.pop()
        visited[v] = True
        stk2.append(v)
        for i in range(len(AL[v][CHILDREN])):
            u = AL[v][CHILDREN][i]
            if visited[u]:
                AL[v][CHILDREN][i] = None
                continue
            stk1.append(u)

    for i in range(n - 1, -1, -1):
        v = stk2[i]
        for u in AL[v][CHILDREN]:
            if u is None:  continue
            AL[v][SIZE] += AL[u][SIZE]

def anaaki(v):
    ret = pow(2, n - 1, p) - 1
    for ch in AL[v][CHILDREN]:
        if ch is None: continue
        ret -= pow(2, AL[ch][SIZE], p) - 1
        ret %= p
    ret -= pow(2, n - AL[v][SIZE], p) - 1
    ret %= p
    return ret

n = int(input())
SIZE = 0
CHILDREN = 1
AL = [[1, []] for _ in range(n)]
visited = [False] * n
p = 10 ** 9 + 7

for i in range(n - 1):
    a, b = [int(x) - 1 for x in input().split()]
    AL[a][CHILDREN].append(b)
    AL[b][CHILDREN].append(a)

dfs()
numer = 0
for i in range(n):
    numer += anaaki(i)
    numer %= p

denom = pow(2, n, p)
print(numer * pow(denom, p - 2, p) % p)

### FIXED CODE ###

# classを使うのをやめてlistで実施する
from collections import deque
import sys
sys.setrecursionlimit(10 ** 9)
import sys
input = sys.stdin.readline

def dfs(v):
    visited[v] = True
    for i in range(len(AL[v][CHILDREN])):
        u = AL[v][CHILDREN][i]
        if visited[u]:
            AL[v][CHILDREN][i] = None
            continue
        AL[v][SIZE] += dfs(u)
    return AL[v][SIZE]


def anaaki(v):
    ret = powp - 1
    for ch in AL[v][CHILDREN]:
        if ch is None: continue
        ret -= pow(2, AL[ch][SIZE], p) - 1
        ret %= p
    ret -= pow(2, n - AL[v][SIZE], p) - 1
    ret %= p
    return ret

n = int(input())
SIZE = 0
CHILDREN = 1
AL = [[1, []] for _ in range(n)]
visited = [False] * n
p = 10 ** 9 + 7
powp = pow(2, n - 1, p)

for i in range(n - 1):
    a, b = [int(x) - 1 for x in input().split()]
    AL[a][CHILDREN].append(b)
    AL[b][CHILDREN].append(a)

dfs(0)
numer = 0
for i in range(n):
    numer += anaaki(i)
    numer %= p

denom = pow(2, n, p)
print(numer * pow(denom, p - 2, p) % p)
### BUGGY CODE ###

# 組み合わせの数を出力
import sys
input = sys.stdin.readline

n = int(input())
s = [sorted(input()) for _ in range(n)]
t = 0
dup = []
# sが空っぽになるまで重複するものを消して差分を控える
while s:
    t = len(s)
    pop = s.pop()
    try:
        while True:
            s.remove(pop)
    except ValueError:
        pass
    dup.append(t-len(s))

ans = sum(c*(c-1)//2 for c in dup)
print(ans)


### FIXED CODE ###

import sys
import collections
input = sys.stdin.readline

n = int(input())
s = [''.join(sorted(input())) for _ in range(n)]
dup = collections.Counter(s).values()

ans = sum(c*(c-1)//2 for c in dup)
print(ans)
### BUGGY CODE ###

R, G, B, N = map(int, input().split())
ans = 0
mb = N//B+1
for r in range(N//R+1):
    for g in range(N//G+1):
        b = (N - r*R - g*G)/B
        if 0 <= b < mb and int(b) == b:
            ans += 1
print(ans)

### FIXED CODE ###

R, G, B, N = map(int, input().split())
ans = 0
mb = N//B+1
for r in range(N//R+1):
    for g in range(N//G+1):
        b = (N - r*R - g*G)/B
        if 0 <= b < mb and int(b) == b:
            ans += 1
print(ans)
### BUGGY CODE ###

N = int(input())
L = [i for i in map(int,input().split())]
S = set(L)
for i in range(1,N+1):
    if i in S:
        print(L.count(i))
    else:
        print(0)

### FIXED CODE ###

N = int(input())
L = [i for i in map(int,input().split())]
ans = dict()
for i in range(1,N+1):
    ans[i] = 0
for el in L:
    if el in ans:
        ans[el] += 1
for i in range(1,N+1):
    print(ans[i])
### BUGGY CODE ###

K = int(input())
n = 1000000

if K % 2 == 0:
    print(-1)
elif K % 7 == 0:
    amari = 10
    for i in range(n):
        if amari % int(9 * (K / 7)) == 1:
            print(i + 1)
            break
        else:
            amari = amari * 10
else:
    amari = 70
    for i in range(n):
        if amari % int(9 * K) == 7:
            print(i + 1)
            break
        else:
            amari = amari * 10

### FIXED CODE ###

k = int(input())
m = 0
 
for i in range(k):
    m = (m * 10 + 7) % k
    if m == 0:
        break
    elif i == k - 1:
        print(-1)
        exit()
 
print(i + 1)
### BUGGY CODE ###

N,M = map(int,input().split())
A = [int(input()) for m in range(M)]
dp = (N+1)*[0]
dp[0] = 1

for n in range(1,N+1):
  if n in A:
    dp[n] = 0
  else:
    dp[n] = (dp[n-2]+dp[n-1])%(10**9+7)

print(dp[-1])

### FIXED CODE ###

MOD = 10**9 + 7

N,M = map(int,input().split())
dp = [0]*(N+1)
dp[0] = 1
A = set(int(input()) for _ in range(M)) # 禁止地帯

for i in range(1,N+1):
  if i in A:
    continue
  x = dp[i-1]
  if i > 1:
    x += dp[i-2]
  dp[i] = x%MOD

answer = dp[N]
print(answer)
### BUGGY CODE ###

H,N = map(int,input().split())
MAXH = H+1
DP = [float("inf")]*MAXH
DP[0] = 0
a = []
b = []
for i in range(N):
  A,B = map(int,input().split())
  a.append(A)
  b.append(B) 
for i in range(MAXH):
  if DP[i] == float("inf"):
    continue    
  for j in range(N):
        DP[min(i+a[j],H)] = min(DP[min(i+a[j],H)],DP[i]+b[j])
print(DP[H])


### FIXED CODE ###

H,N = map(int,input().split())
MAXH = H+1
DP = [float("inf")]*MAXH
DP[0] = 0
a = [0]*N
b = [0]*N
for i in range(N):
  a[i],b[i] = map(int,input().split())
for i in range(MAXH):
  if DP[i] == float("inf"):
    continue    
  for j in range(N):
        DP[min(i+a[j],H)] = min(DP[min(i+a[j],H)],DP[i]+b[j])
print(DP[H])
### BUGGY CODE ###

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

a = [1]
p = [1]
for i in range(N):
  a.append(a[i]*2 + 3)
  p.append(p[i]*2 + 1)
def f(n, x):
#  print (n, a[n], x)
  if n == 0:
    return 0
  elif n == 1:
    return "BPPPB"[:x].count("P")
  else: 
    if x <= 0:
      return 0
    elif x <= 1 + a[n-1]:
      return f(n-1, x-1)  
    else:
      return f(n-1,a[n-1])+f(n-1,x - 2 - a[n-1]) +1
print (f(N, X))

### FIXED CODE ###

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

a = [1]
p = [1]
for i in range(N):
  a.append(a[i]*2 + 3)
  p.append(p[i]*2 + 1)
def f(n, x):
#  print (n, a[n], x)
  if n == 0:
    return 0 if x<= 0 else 1
  elif n == 1:
    return "BPPPB"[:x].count("P")
  else: 
    if x <= 0:
      return 0
    elif x <= 1 + a[n-1]:
      return f(n-1, x-1)  
    else:
      return p[n-1] + f(n - 1,x - 2 - a[n-1]) + 1
print (f(N, X))
### BUGGY CODE ###

N = int(input())
s = [sorted(list(input())) for i in range(N)]

#出現文字列
dict = {}

ans = 0

for i in range(N):

    s_i = str(s[i])

    if s_i in dict:
        #組み合わせが増えるので
        dict[s_i] = dict[s_i] + 1

        ans += dict[s_i]
        continue

    for j in range(i+1,N):
        dict[s_i] = 0

print(ans)


### FIXED CODE ###

N = int(input())
s = ["".join(sorted(input())) for i in range(N)]

#print(s)

#出現文字列
sdict = {}

for i in range(N):

    s_i = str(s[i])

    if s_i in sdict:
        #組み合わせが増えるので
        sdict[s_i]+= 1
        continue

    else:
        sdict[s_i] = 1

ans = 0
for i in sdict.values():
    ans += i*(i-1)//2
print(ans)
### BUGGY CODE ###

H, W, A, B = map(int, input().split())

m = 10**9 + 7

fc = [1] * (H + W)
for i in range(2, H+W):
    fc[i] = fc[i - 1] * i % m

import functools
@functools.lru_cache(maxsize=None)
def fact(n):
    if n == 0: return 1
    return n * fc[n - 1] % m

def mod_pow(x, n, mod):
    if n == 0: return 1
    d, m = n >> 1, n & 1
    p = mod_pow(x, d, mod)
    return (p * p * (x if m else 1)) % mod

def rev(n):
    return mod_pow(n, m - 2, m)

def cr(c, r):
    return fact(c + r) * rev(fact(c) * fact(r) % m) % m


ans = 0
for c in range(B, W):
    ans += cr(c, H - 1 - A) * cr(W - 1 - c, A - 1)
print(ans % m)

### FIXED CODE ###

H, W, A, B = map(int, input().split())

m = 10**9 + 7

import functools
@functools.lru_cache(maxsize=None)
def cr(c, r):
    return fc[c + r] * ic[c] * ic[r] % m

fc = [1] * (H + W)
for i in range(2, H+W):
    fc[i] = fc[i - 1] * i % m
ic = [pow(x, m-2, m) for x in fc]

ans = 0
for c in range(B, W):
    ans += cr(c, H - 1 - A) * cr(W - 1 - c, A - 1) % m
print(ans % m)
### BUGGY CODE ###

from collections import Counter

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

divisors = []
for i in range(n):
    for j in range(1, int(a[i] ** 0.5) + 1):
        if a[i] % j == 0:
            divisors.append(j)
            if j != a[i] // j:
                divisors.append(a[i] // j)

d = Counter(divisors)
ans = [k for k, v in d.items() if v >= n - 1]
print(max(ans))

### FIXED CODE ###

from fractions import gcd

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

left = [0 for _ in range(n + 1)]
right = [0 for _ in range(n + 1)]
for i in range(n):
    left[i + 1] = gcd(left[i], a[i])

for i in reversed(range(n)):
    right[i] = gcd(right[i + 1], a[i])

ans = 0
for i in range(n):
    l = left[i]
    r = right[i+1]
    ans = max(ans, gcd(l, r))

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

hp,n=map(int,input().split())

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

dp=[10**30]*(10**4+1)

dp[hp]=0

for a,b in skills:
    for h in range(hp,0,-1):
        if h-a>=0:
            dp[h-a]=min(dp[h-a],dp[h]+b)
        else:
            dp[0]=min(dp[0],dp[h]+b)
            
print(dp[0])

### FIXED CODE ###

h,n=map(int,input().split())

a=[]
b=[]
for _ in range(n):
    x,y=map(int,input().split())
    a.append(x)
    b.append(y)
    
# print(a)
# print(b)

INF=float("inf")

dp=[INF]*(h+1)
dp[h]=0

for aa,bb in zip(a,b):
    for hh in range(h,0,-1):
        if hh-aa>=0:
            dp[hh-aa]=min(dp[hh-aa],dp[hh]+bb)
        else:
            dp[0]=min(dp[0],dp[hh]+bb)
            
print(dp[0])
# print(dp)
### BUGGY CODE ###

x = int(input())

pl = [2]

if x == 2:
    print(2)
    exit()

cnt = 3
f = False

while True:
    if cnt == x:
        f = True
    for i in range(len(pl)):
        if cnt % pl[i] == 0:
            break
    else:
        pl.append(cnt)
        if f:
            print(cnt)
            exit()
    cnt += 1

### FIXED CODE ###

import math

x = int(input())

while True:
    for i in range(2, int(math.sqrt(x))+1):
        if x % i == 0:
            break
    else:
        print(x)
        exit()
    x += 1
### BUGGY CODE ###

import sys
import numpy as np
from numba import njit
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
def update(A):
    N = len(A)
    B = np.zeros_like(A)
    for i, x in enumerate(A):
        l = max(0, i - x)
        r = min(N - 1, i + x)
        B[l] += 1
        if r + 1 < N:
            B[r + 1] -= 1
    B = np.cumsum(B)
    return B
 
N, K = map(int, readline().split())
A = np.array(read().split(), np.int64)
 
K = min(K, 100)
for _ in range(K):
    A = update(A)
print(' '.join(A.astype(str)))

### FIXED CODE ###

import sys
import numpy as np
from numba import njit
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
@njit('(i8[::1],)', cache=True)
def update(A):
    N = len(A)
    B = np.zeros_like(A)
    for i, x in enumerate(A):
        l = max(0, i - x)
        r = min(N - 1, i + x)
        B[l] += 1
        if r + 1 < N:
            B[r + 1] -= 1
    B = np.cumsum(B)
    return B
 
N, K = map(int, readline().split())
A = np.array(read().split(), np.int64)
 
K = min(K, 100)
for _ in range(K):
    A = update(A)
print(' '.join(A.astype(str)))
### BUGGY CODE ###

# -*- coding: utf-8 -*-

import re

n = int(raw_input())
a = map(int, re.split("\s", raw_input()))
left = 0
right = 0
mask = 10**9 + 7

com = [1]*(n+2)

tmp = 1
for i in range(1, n+2):
        tmp *= i % mask
        com[i] = tmp

for i in range(0, n + 1):
        x = a.index(a[i])
        if a[i] in a[x+1:]:
                left = i
                right = a[x+1:].index(a[i]) + x + 1
                break

for i in range(1, n + 2):
        ans = (com[n + 1] / (com[i] * com[n + 1 - i]))
        m = com[i - 1] * com[left + n - right - i + 1]
        x = 0
        if m != 0:
                x = (com[left + n - right] / m)
        print (ans - x) % mask


### FIXED CODE ###

# -*- coding: utf-8 -*-

from collections import Counter
import re

def pow(a, x):
        y = 1
        p = a % mask
        n = x
        while (n > 0):
                if ((n % 2) == 0):
                        p = (p * p) % mask
                        n /= 2
                else:   
                        y = (y * p) % mask
                        n -= 1
        return y

n = int(raw_input())
a = map(int, re.split("\s", raw_input()))
left = 0
right = 0

mask = 10**9 + 7
invm = 10**9 + 5

com = [1]*(n+2)
inv = [1]*(n+2)

tmp = 1 
for i in range(1, n+2):
        tmp = (tmp * i) % mask
        com[i] = tmp
        inv[i] = pow(tmp, invm) % mask

counter = Counter(a)
dup = counter.most_common(1)[0][0]
left = a.index(dup)
right = a[left+1:].index(dup) + left + 1

for i in range(1, n + 2):
        ans = (com[n + 1] * (inv[i] * inv[n + 1 - i]))

        if ((left + n - right - i + 1) >= 0):
                ans -= (com[left + n - right] * inv[i - 1] * inv[left + n - right - i + 1])
        print ans % mask
### BUGGY CODE ###

N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
j=0
for i in range(M):
    A[A.index(max(A[:j+1]))]=A[A.index(max(A[:j+1]))]//2
    j=j+1
    if j==200:
        A.sort(reverse=True)    
        j=0
print(sum(A))

### FIXED CODE ###

import heapq
N,M=map(int,input().split())
A=list(map(lambda x: x*(-1),list(map(int,input().split()))))
A.sort()
B=[]
for i in range(N):
    heapq.heappush(B,A[i])
for i in range(M):
    heapq.heappush(B,(((heapq.heappop(B))*(-1))//2)*(-1))
print((sum(B))*(-1))