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

# -*- coding: utf-8 -*-
from sys import stdin
import bisect
import functools


s_in = lambda: stdin.readline()[:-1]  # s = s_in()
d_in = lambda: int(stdin.readline())  # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split()))  # List = ds_in()

ORDER = 28


def under_order(x, n):
    """
    x: int
        target int number

    n: int, [0, 27]
        specific order
    """
    binary = bin(x)[2:]
    # binary = '0' * (ORDER - len(binary)) + binary
    binary = '0' * (28 - len(binary)) + binary
    return int(binary[-n-1:], 2)


def calc_count(b_, a_list_, pow2, N_):
    c1 = bisect.bisect_left(a_list_, pow2 - b_)
    c2 = bisect.bisect_left(a_list_, 2*pow2 - b_)
    c3 = bisect.bisect_left(a_list_, 3*pow2 - b_)
    return N_ - c3 + c2 - c1

N = d_in()
a_list = ds_in()
b_list = ds_in()

a_order_list = []
for i in range(ORDER):
    temp_list = list(map(under_order, a_list, [i] * N))
    temp_list.sort()
    a_order_list.append(temp_list)

temp_list = list(map(under_order, a_list, [ORDER-1] * N))
temp_list.sort()
a_order_list.append(temp_list)


ans = ''
for i in range(ORDER):
    count = list(map(functools.partial(calc_count, a_list_=a_order_list[i],
        pow2=2**i, N_=N), map(functools.partial(under_order, n=i), b_list)))

    if sum(count) % 2 == 1:
        ans += '1'
    else:
        ans += '0'


count = list(map(functools.partial(calc_count, a_list_=a_order_list[-1],
    pow2=2**ORDER, N_=N), b_list))
if sum(count) % 2 == 1:
    ans += '1'
else:
    ans += '0'

print(int(ans[::-1], 2))


### FIXED CODE ###

# -*- coding: utf-8 -*-
from sys import stdin
import numpy as np


d_in = lambda: int(stdin.readline())  # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split()))  # List = ds_in()

ORDER = 28


def np_search(b_list_, a_list_, pow2, N_):
    c1 = np.searchsorted(a_list_, pow2 - b_list_)
    c2 = np.searchsorted(a_list_, 2*pow2 - b_list_)
    c3 = np.searchsorted(a_list_, 3*pow2 - b_list_)
    return N_**2 - c3.sum() + c2.sum() - c1.sum()



N = d_in()
a_list = ds_in()
b_list = ds_in()


np_a = np.array(a_list)
np_b = np.array(b_list)
a_order_list = np.zeros((ORDER, N), dtype=int)
b_order_list = np.zeros((ORDER, N), dtype=int)
for i in range(1, ORDER+1):
    a_order_list[i-1, :] = np_a % 2**i
    b_order_list[i-1, :] = np_b % 2**i

a_order_list.sort(axis=1)

ans = ''
for i in range(ORDER):
    count = np_search(b_list_=b_order_list[i], a_list_=a_order_list[i],
            pow2=2**i, N_=N)
    if count % 2 == 1:
        ans += '1'
    else:
        ans += '0'

count = np_search(b_list_=b_order_list[-1], a_list_=a_order_list[-1],
        pow2=2**ORDER, N_=N)

if count % 2 == 1:
    ans += '1'
else:
    ans += '0'

print(int(ans[::-1], 2))
### BUGGY CODE ###

def binsearch(l, r, fn):
    while r - l > 1:
        m = (l + r) // 2
        if fn(m):
            l = m
        else:
            r = m
    return l

def main():
    X, Y, Z, K = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    C = sorted(map(int, input().split()), reverse=True)
    AB = sorted((a + b for a in A for b in B), reverse=True)
    def helper(x):
        r = 0
        t = len(C) - 1
        for ab in AB:
            while t >= 0 and C[t] + ab < x:
                t -= 1
            r += t + 1
        return r >= K
    l = binsearch(AB[-1] + C[-1], AB[0] + C[0] + 1, helper)
    r = []
    for ab in AB:
        for c in C:
            if ab + c < l:
                break
            r.append(ab + c)
            if len(r) == K:
                break
        if len(r) >= K:
            break

    r.sort(reverse=True)
    print('\n'.join(str(i) for i in r))

main()





### FIXED CODE ###

def binsearch(l, r, fn):
    while r - l > 1:
        m = (l + r) // 2
        if fn(m):
            l = m
        else:
            r = m
    return l

def main():
    X, Y, Z, K = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    C = sorted(map(int, input().split()), reverse=True)
    AB = sorted((a + b for a in A for b in B), reverse=True)
    def helper(x):
        r = 0
        t = len(C) - 1
        for ab in AB:
            while t >= 0 and C[t] + ab < x:
                t -= 1
            r += t + 1
            if r >= K:
                return True
            if t < 0:
                return False
        return r >= K
    l = binsearch(AB[-1] + C[-1], AB[0] + C[0] + 1, helper)
    r = []
    t = len(C) - 1
    for ab in AB:
        while t >= 0 and C[t] + ab < l + 1:
            t -= 1
        if t < 0:
            break
        r.extend(ab + c for c in C[:t + 1])
    r.sort(reverse=True)
    r += [l] * (K - len(r))
    print('\n'.join(str(i) for i in r))

main()
### BUGGY CODE ###

import math

def combinations_count(n, r):
    if r>n:
        return 0
    if n==0 or n==1:
        return 0
    if n==r:
        return 1
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


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

memo = [0] * (2*(10**5))
num_list = [0] * (2*(10**5))

for i in range(n):
    num_list[a[i]] += 1

for i in range(n):
    num = a[i]
    if memo[num] != 0:
        print(memo[num])
    else:
        cnt = 0
        for j in range(2*(10**5)):
            if j != num:
                cnt += combinations_count(num_list[j], 2)
            else:
                cnt += combinations_count(num_list[j]-1, 2)
        print(cnt)
        memo[num] = cnt

### FIXED CODE ###

from collections import Counter

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

c = Counter(a)   # c: Counter({1: 3, 2: 2})など
for k, v in c.items():
    re[k] = v*(v-1) // 2

total = sum(re)
for i in a:
    print(total - re[i] + (c[i]-1)*(c[i]-2) // 2)
### BUGGY CODE ###

a=int(input())
b=0
c=int(a**(1/2))
for i in range(-2000,2000):
    for j in range(-2000,2000):
        if((i**5)-(j**5)==a):
            b=1
            break
    if(b==1):
        break
print(i,j)

### FIXED CODE ###

a=int(input())
b=0
c=int(a**(1/2))
for i in range(-1000,1000):
    for j in range(-1000,1000):
        if((i**5)-(j**5)==a):
            b=1
            break
    if(b==1):
        break
print(i,j)
### BUGGY CODE ###

from collections import deque, defaultdict
import sys
input=sys.stdin.readline


def solve():
    H, W, K = map(int, input().split())
    y1, x1, y2, x2 = map(int, input().split())
    l = [[1 if s=="@" else 0 for s in input()] for _ in range(H)]
    INF = 10**12

    x1 -= 1
    y1 -= 1
    x2 -= 1
    y2 -= 1

    ddy = [0, 0, -1, 1]
    ddx = [-1, 1, 0, 0]

    dist = defaultdict(lambda :INF)
    dist[(y1, x1)] = 0
    q = deque([(y1, x1)])

    while q:
        y, x = q.popleft()
        for i, (dy, dx) in enumerate(zip(ddy, ddx)):
            for j in range(1, K+1):
                if not (0<=y+dy*j<H and 0<=x+dx*j<W):
                    continue
                if l[y+dy*j][x+dx*j]:
                    break

                if dist[(y+dy*j, x+dx*j)] > dist[(y, x)] + 1:
                    dist[(y+dy*j, x+dx*j)] = dist[(y, x)] + 1
                    q.append((y+dy*j, x+dx*j))


    ans = dist[(y2, x2)]
    print(ans if ans!=INF else -1)


if __name__ == "__main__":
    solve()


### FIXED CODE ###

from collections import deque, defaultdict
import sys
input=sys.stdin.readline


def solve():
    H, W, K = map(int, input().split())
    y1, x1, y2, x2 = map(int, input().split())
    l = [[1 if s=="@" else 0 for s in input()] for _ in range(H)]
    INF = 10**12

    x1 -= 1
    y1 -= 1
    x2 -= 1
    y2 -= 1

    ddy = [0, 0, -1, 1]
    ddx = [-1, 1, 0, 0]

    dist = defaultdict(lambda :INF)
    dist[(y1, x1)] = 0
    q = deque([(y1, x1)])

    while q:
        y, x = q.popleft()
        for dy, dx in zip(ddy, ddx):
            for j in range(1, K+1):
                if not (0<=y+dy*j<H and 0<=x+dx*j<W):
                    break
                if l[y+dy*j][x+dx*j]:
                    break

                if dist[(y+dy*j, x+dx*j)] > dist[(y, x)] + 1:
                    dist[(y+dy*j, x+dx*j)] = dist[(y, x)] + 1
                    q.append((y+dy*j, x+dx*j))
                elif dist[(y+dy*j, x+dx*j)] == dist[(y, x)] + 1:
                    continue
                else:
                    break


    ans = dist[(y2, x2)]
    print(ans if ans!=INF else -1)


if __name__ == "__main__":
    solve()
### BUGGY CODE ###

n, m = map(int, input().split())
p, y = [0 for _ in range(m)], [0 for _ in range(m)]
year_list = [[] for _ in range(n)]
for i in range(m):
    p[i], y[i] = map(int, input().split())
    year_list[p[i] - 1].append(y[i])
for j in range(n):
    year_list[j].sort()
for i in range(m):
    x = year_list[p[i] - 1].index(y[i]) + 1
    print(str(p[i]).zfill(6) + str(x).zfill(6))

### FIXED CODE ###

import bisect
def index(alist, x):
    i = bisect.bisect_left(alist, x)
    if i != len(alist) and alist[i] == x:
        return i
    raise ValueError

n, m = map(int, input().split())
p, y = [0] * m, [0] * m
year_list = [[] for _ in range(n)]
for i in range(m):
    p[i], y[i] = map(int, input().split())
    year_list[p[i] - 1].append(y[i])
for j in range(n):
    year_list[j].sort()
for i in range(m):
    x = index(year_list[p[i] - 1], y[i]) + 1
    print(str(p[i]).zfill(6) + str(x).zfill(6))
### BUGGY CODE ###

n = int(input())
aa = list(map(int, input().split()))
bit = [[0] * 21 for _ in range(n)]
for i, a in enumerate(aa):
    for j in range(21):
        a, m = divmod(a, 2)
        if m: bit[i][j] = 1
#for x in bit:
#    print(x)
last = [-1] * 21
L = R = 0
ans = 0
while R < n:
    out = []
    nextL = []
    for j in range(21):
        if bit[R][j]:
            if last[j] == -1:
                last[j] = R
            else:
                out.append(j)
                nextL.append(last[j])
                last[j] = R
    #    print(L,R,ans,last)
    if out:
        #        print(out)
        d1 = R - L
        L = max(nextL) + 1
        d2 = R - L + 1
        #        print(d1,d2,(d1+d2)*(d1-d2+1)//2)
        ans += (d1 + d2) * (d1 - d2 + 1) // 2
        for j in range(21):
            if last[j] < L:
                last[j] = -1
    R += 1
d = n - L
ans += d * (d + 1) // 2
print(ans)


### FIXED CODE ###

n = int(input())
aa = list(map(int, input().split()))
bit = [[0] * 21 for _ in range(n)]
for i, a in enumerate(aa):
    for j in range(21):
        a, m = divmod(a, 2)
        if m: bit[i][j] = 1
#for x in bit:
#    print(x)
last = [-1] * 21
L = R = 0
ans = 0
while R < n:
    out = []
    nextL = []
    for j in range(21):
        if bit[R][j]:
            if last[j] == -1:
                last[j] = R
            else:
                out.append(j)
                nextL.append(last[j])
                last[j] = R
    #    print(L,R,ans,last)
    if out:
        #        print(out)
        d1 = R - L
        L = max(nextL) + 1
        d2 = R - L + 1
        #        print(d1,d2,(d1+d2)*(d1-d2+1)//2)
        ans += (d1 + d2) * (d1 - d2 + 1) // 2
        for j in range(21):
            if last[j] < L:
                last[j] = -1
    R += 1
d = n - L
ans += d * (d + 1) // 2
print(ans)
### BUGGY CODE ###

# -*- coding:utf-8 -*-
n = int(raw_input())
a = [[int(k),i+1] for i,k in enumerate(raw_input().split())]
a.sort(reverse=True)
z = [l[1] for l in a]
s=[0]*n
a.append([0,0])
for i,p in enumerate(a[:-1]):
    if not p[0] == a[i+1][0]:
        q = p[0] - a[i+1][0]
        y = z[:i+1]
        s[min(y)-1] += (i+1)*q

for t in s:
    print(t)

### FIXED CODE ###

# -*- coding:utf-8 -*-
n = int(raw_input())
a = [[int(k),i+1] for i,k in enumerate(raw_input().split())]
a.sort(reverse=True)
z = [l[1] for l in a]
s=[0]*n
a.append([0,0])
min_a_i = float('inf')
for i,p in enumerate(a[:-1]):
    min_a_i = min(min_a_i, a[i][1])
    if not p[0] == a[i+1][0]:
        q = p[0] - a[i+1][0]
        s[min_a_i-1] += (i+1)*q

for t in s:
    print(t)
### BUGGY CODE ###

# vim: set fileencoding=utf-8 :


def main():
    k, s = map(int, raw_input().split())
    patterns = []

    # 重複していいからとにかくpushする
    for x in range(k + 1):
        nokori = s - x
        for y in range(k + 1):
            if 0 <= nokori - y <= k:
                z = nokori - y
                patterns.append([x, y, z])

    ct = len(patterns)
    print(ct)


if __name__ == "__main__":
    main()


### FIXED CODE ###

# vim: set fileencoding=utf-8 :
k, s = map(int, raw_input().split())
patterns = []
ct = 0

for x in range(k + 1):
    nokori = s - x
    for y in range(k + 1):
        if 0 <= nokori - y <= k:
            ct += 1

print(ct)
### BUGGY CODE ###

from fractions import gcd
from functools import reduce

mod = 10 ** 9 + 7

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm(numbers):
    return reduce(lcm_base, numbers, 1)

# print('input >>')
N = int(input())
A = list(map(int,(input().split())))

lcmn = lcm(A)

ans = 0
for A_ in A:
    ans += (lcmn // A_) % mod

# print('-----output-----')
print(int(ans%mod))

### FIXED CODE ###

from fractions import gcd
from functools import reduce

mod = 10 ** 9 + 7

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm(numbers):
    return reduce(lcm_base, numbers, 1)

# print('input >>')
N = int(input())
A = list(map(int,(input().split())))

lcmn = lcm(A)

ans = 0
for i in range(len(A)):
    ans += lcmn // A[i]

# print('-----output-----')
print(int(ans%mod))
### BUGGY CODE ###


p = int(input())

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

lis = [0] * (p+1)

for i in range(p):

    if i == 0:
        lis[1] = 1
        lis[0] = 0

    else:
        
        nlis = [0] * (p+1)

        for j in range(p+1):
            nlis[j] += lis[j] * (-1 * i)
            if j != 0:
                nlis[j] += lis[j-1]

        lis = nlis

#print (lis) = (x-0)*(x-1)*…*(x-p+1)の各項の係数
#ラグランジュ補完を実際に計算していく
#参考　https://mathtrain.jp/hokan

ans = [0] * p

for i in range(p):

    #fi(x)を計算 (x-i)でlisを割る
    if a[i] == 0:
        continue

    nlis = [0] * p

    for j in range(p-1,-1,-1):

        if j == p-1:
            nlis[j] = lis[j+1]
        else:
            nlis[j] = (lis[j+1] - nlis[j+1] * (-1 * i))

    for j in range(p):
        ans[j] += nlis[j]

for i in range(p):
    ans[i] = (p - ans[i]) % p
print (" ".join(map(str,ans)))


### FIXED CODE ###


p = int(input())

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

lis = [0] * (p+1)

for i in range(p):

    if i == 0:
        lis[1] = 1
        lis[0] = 0

    else:
        
        nlis = [0] * (p+1)

        for j in range(p+1):
            nlis[j] += lis[j] * (-1 * i)
            if j != 0:
                nlis[j] += lis[j-1]
            nlis[j] %= p

        lis = nlis

#print (lis) = (x-0)*(x-1)*…*(x-p+1)の各項の係数
#ラグランジュ補完を実際に計算していく
#参考　https://mathtrain.jp/hokan

ans = [0] * p

for i in range(p):

    #fi(x)を計算 (x-i)でlisを割る
    if a[i] == 0:
        continue

    nlis = [0] * p

    for j in range(p-1,-1,-1):

        if j == p-1:
            nlis[j] = lis[j+1]
        else:
            nlis[j] = (lis[j+1] - nlis[j+1] * (-1 * i)) % p

    for j in range(p):
        ans[j] += nlis[j]

for i in range(p):
    ans[i] = (p - ans[i]) % p
print (" ".join(map(str,ans)))
### BUGGY CODE ###


import sys
input = lambda : sys.stdin.readline().rstrip()

# 小さすぎても怒られるので
from collections import defaultdict
n = int(input())
sys.setrecursionlimit(max(1000, 2*n))

cs = [0] + [int(c) for c in input().split()]
ns = defaultdict(set)
for _ in range(n-1):
    a,b = [int(c) for c in input().split()]
    ns[a].add(b)
    ns[b].add(a)

def dfs(ns, prev, now, toru, results):
    end = defaultdict(int)
    k = cs[now]
    end[k] = 1
    s = 1 # nowで終わるパスの種類
    tmp_s2_sum = 0
    usList = defaultdict(list)
    for u in ns[now]:
        if u==prev:
            continue
        tmp_end, tmp_toru, tmp_s = results[u]  # dfs(ns, now, u, toru)
        for kk,vv in tmp_end.items():
            if kk!=k:
                end[kk] += vv
            usList[kk].append((vv, tmp_s))
        end[k] += tmp_s
        s += tmp_s
        tmp_s2_sum += tmp_s**2
    for kk,vv in usList.items():
        if kk!=k:
            x_sum = 0
            x2_sum = 0
            for item in vv:
                toru[kk] += (s - item[1]) * item[0]
                x_sum += item[0]
                x2_sum += item[0]**2
            toru[kk] -= (x_sum**2 - x2_sum) / 2
    toru[k] += (1 + ((s-1)**2 - tmp_s2_sum)/2 + (s-1))
#     print(now, prev, end, toru, s)
    results[now] = end, toru, s

toru = [0] * (n+1)
q = [(1, -1)] # now, prev
args = []
while q:
    u, prev = q.pop()
    args.append((u,prev))
    for v in ns[u]:
        if prev==v:
            continue
        q.append((v, u))
results = {}
for arg in args[::-1]:
    dfs(ns, arg[1], arg[0], toru, results)

for item in toru[1:]:
    print(int(item))

### FIXED CODE ###


import sys
# 小さすぎても怒られるので
from collections import defaultdict
n = int(input())
sys.setrecursionlimit(max(1000, 2*n))

cs = [0] + [int(c) for c in input().split()]
ns = defaultdict(set)
for _ in range(n-1):
    a,b = [int(c) for c in input().split()]
    ns[a].add(b)
    ns[b].add(a)

ans = [0] * (n+1) # kを通らないパスの総数
minus = [0] * (n+1) # uの部分木のうち
minus0 = defaultdict(int)
st = {k: [] for k in range(1, n+1)}
nextu = {}
def dfs(u, prev, ans):
    global minus, st, minus0
    k = cs[u]
    st[k].append(u)
    ss = 1
    for v in ns[u]:
        if v==prev:
            continue
        nextu[u] = v
        s = dfs(v, u, ans)
        ss += s
        tmp = s - minus[v]
        ans[k] += (int(tmp * (tmp - 1) / 2) + tmp)
    st[k].pop()
    if st[k]:
        minus[nextu[st[k][-1]]] += ss
    else:
        minus0[k] += ss
#     print(ss)
    return ss

dfs(1, -1, ans)
for k in range(1, n+1):
    tmp = n - minus0[k]
    ans[k] += (int(tmp * (tmp - 1) / 2) + tmp)
    
total = int(n * (n+1) / 2)
for i in range(1, n+1):
    print(total - ans[i])
### BUGGY CODE ###

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

N, M = map(int, input().split())
P = [None] * M
Y = [None] * M
for i in range(M):
    p, y = map(int, input().split())
    P[i] = p
    Y[i] = y

ken = [None] * N
for i in range(N):
    ken[i] = []

for i in range(M):
    ken[P[i] - 1].append(Y[i])

for i in range(N):
    ken[i] = sorted(ken[i])

city_info = [None] * M

k = 0

while(k < M):
    for l in range(N):
        for m in range(len(ken[l])):
            city_info[k] = [ken[l][m], l + 1, m + 1]
            k += 1


def createID(p, x):
    output_p = str(p)
    output_x = str(x)
    p_len = len(output_p)
    x_len = len(output_x)
    while p_len < 6:
        output_p = "0" + output_p
        p_len += 1
    while x_len < 6:
        output_x = "0" + output_x
        x_len += 1

    return output_p + output_x


for i in range(M):
    # Y[i]を探してきてprint
    for j in range(M):
        if city_info[j][0] == Y[i]:
            print(createID(city_info[j][1], city_info[j][2]))
            break


### FIXED CODE ###

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

# from time import time
# 
# start = time()


def six(n):
    n_str = str(n)
    while len(n_str) < 6:
        n_str = "0" + n_str

    return n_str


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

id_list = [None] * M
dic_P = {}
info = []
info_idx = 0

for i in range(M):
    P, Y = map(int, input().split())
    id_list[i] = [P, Y, ""]
    if P in dic_P.keys():
        info[dic_P[P]].append([i, P, Y])
    else:
        dic_P[P] = info_idx
        info_idx += 1
        info.append([[i, P, Y]])

for group in info:
    group.sort(key=lambda a_i: a_i[2], reverse=False)
    for i, pair in enumerate(group):
        id = six(pair[1]) + six(i+1)
        id_list[pair[0]] = id

for id in id_list:
    print(id)

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

from itertools import combinations
from fractions import gcd
N = int(input())
A = list(map(int,input().split()))

comb = list(combinations(A,len(A)-1))
max_gcd = 0
for i in range(len(comb)):
  temp_gcd = comb[i][0]
  for j in range(1,len(comb[i])):
    temp_gcd = gcd(temp_gcd,comb[i][j])
  max_gcd = max(max_gcd,temp_gcd)

print(max_gcd)

### FIXED CODE ###

from fractions import gcd
N = int(input())
A = list(map(int,input().split()))

L = [0]
R = [0]
for i in range(N-1):
  L.append(gcd(L[i],A[i]))
  R.append(gcd(R[i],A[-i-1]))

max_gcd = 0
for i in range(N):
  max_gcd = max(max_gcd, gcd(L[i],R[-i-1]))

print(max_gcd)
### BUGGY CODE ###

def strTint(s):
    return ord(s)-96
def main():
    N = int(input())
    S = input()
    #N = 5000
    #S = "a"*N
    import time
    star = time.time()
    
    b = 27
    mod1 = 10**9+7
    mod2 = 10**9+9
    D = {}
    for i in range(N):
        H = strTint(S[i])
        H1 = H%mod1
        H2 = H%mod2
        if not (H1,H2) in D:
            D[(H1,H2)] = [1,i,i]
        for j in range(i+1,min(i+N//2+2,N)):
            H1 = (H1*b + strTint(S[j]))%mod1
            H2 = (H2*b + strTint(S[j]))%mod2
            if not (H1,H2) in D:
                D[(H1,H2)] = [j-i+1,i,i]
            else:
                D[(H1,H2)][-1] = i
    
    ans = 0
    for i in D:
        L = D[i][0]
        tmp = 0
        if D[i][1] + L <= D[i][-1] and ans < L:
            ans = L
    g = time.time()
    #print(g-star)
    print(ans)
    
main()

### FIXED CODE ###

def z_algo(S):
    N = len(S)
    A = [0]*N
    i = 1; j = 0
    A[0] = l = len(S)
    while i < l:
        while i+j < l and S[j] == S[i+j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while l-i > k < j - A[k]:
            A[i+k] = A[k]
            k += 1
        i += k; j -= k
    return A

def main():
    N = int(input())
    S = input()
    #N = 5000
    #S = "a"*N
    import time
    star = time.time()
    A = [[] for i in range(N)]
    for i in range(N):
        A[i] = [0]*i + z_algo(S[i:])
    ans = 0
    for i in range(N):
        for j in range(N):
            if i + A[i][j] <= j and ans < A[i][j]:
                ans = A[i][j]
    
    g = time.time()
    #print(g-star)
    print(ans)
    
main()
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
#a = list(reversed(sorted(a)))
ans = 0
#minV = 10**15
total = sum(a)
#print(total)

while True:
    if m <= 0:
        break
    maxV = max(a)
    idx = a.index(maxV)
#    total = total - maxV + (maxV // 2)
    a[idx] = a[idx] // 2

#    a[0] = a[0] // 2
#    a = list(reversed(sorted(a)))
    m -= 1

ans = sum(a)
print(ans)

### FIXED CODE ###

import heapq

n, m = map(int, input().split())
a = []
#a = list(map(int, input().split()))
#a = list(reversed(sorted(a)))
#heapq.heapify(a)
for i in input().split():
    heapq.heappush(a, -int(i))

ans = 0

for i in range(len(a)):
    while True:
        if m <= 0:
            break

        maxV = heapq.heappop(a)
#        print('maxV: ' + str(maxV))
        heapq.heappush(a, -(-maxV // 2))
        m -= 1
        # print('m: ' + str(m))
        # print('a: ' + str(a))
ans = -sum(a)
print(ans)
### BUGGY CODE ###

def soinsu(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

n=int(input())
a=soinsu(n)
c=[]
if n>=2:
    for i in range(max(a)):
        c.append(0)
for i in a:
    c[i-1]+=1
z=0
for i in c:
    d=1
    e=1
    while e<=i:
        z+=1
        d+=1
        e=d*(d+1)/2
print(z)

### FIXED CODE ###

n=int(input())
import math
s=round(math.sqrt(n))+1

i=2
c1=0
c2=1
ans=0
while i<=s:
    if n%i==0:
        n//=i
        c1+=1
        if c1==c2:
            c1=0
            c2+=1
            ans+=1
    else:
        c2=1
        i+=1
        c1=0
if n>s:
    ans+=1
    
print(ans)