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

from copy import deepcopy
H, W, K = map(int, input().split())

def clear(row, start, end, mult):
    if end - start + 1 < K:
        return 0
    gain = 0
    for i in range(start, end + 1):
        gain += mult * row[i]
        row[i] = 0
    return gain

def drop(board):
    for x in range(W):
        wp = 0
        for y in range(H):
            if board[y][x] > 0:
                board[wp][x] = board[y][x]
                if wp != y:
                    board[y][x] = 0
                wp += 1

def proceed(board, mult):
    gain = 0
    for row in board:
        start = -1
        num = -1
        for i in range(W):
            if row[i] == num:
                continue
            else:
                gain += clear(row, start, i-1, mult)
                num = row[i]
                start = i
        if num > 0:
            gain += clear(row, start, W-1, mult)
    drop(board)
    return gain

board_ = []
for _ in range(H):
    board_.append(list(map(int, input())))
board_.reverse()

ans = 0
for y in range(H):
    for x in range(W):
        board = deepcopy(board_)
        board[y][x] = 0
        drop(board)
        mult = 1
        cand = 0
        while True:
            gain = proceed(board, mult)
            if gain == 0:
                break
            cand += gain
            mult *= 2
        ans = max(ans, cand)
print(ans)


### FIXED CODE ###

from copy import deepcopy
H, W, K = map(int, input().split())

def clear(row, start, end, mult):
    if end - start + 1 < K:
        return 0
    gain = 0
    for i in range(start, end + 1):
        gain += mult * row[i]
        row[i] = 0
    return gain

def drop(board):
    for x in range(W):
        wp = 0
        for y in range(H):
            if board[y][x] > 0:
                board[wp][x] = board[y][x]
                if wp != y:
                    board[y][x] = 0
                wp += 1

def proceed(board, mult):
    gain = 0
    for row in board:
        start = -1
        num = -1
        for i in range(W):
            if row[i] == num:
                continue
            else:
                gain += clear(row, start, i-1, mult)
                num = row[i]
                start = i
        if num > 0:
            gain += clear(row, start, W-1, mult)
    drop(board)
    return gain

board_ = []
for _ in range(H):
    board_.append(list(map(int, input())))
board_.reverse()

ans = 0
for y in range(H):
    for x in range(W):
        board = deepcopy(board_)
        board[y][x] = 0
        drop(board)
        mult = 1
        cand = 0
        while True:
            gain = proceed(board, mult)
            if gain == 0:
                break
            cand += gain
            mult *= 2
        ans = max(ans, cand)
print(ans)
### BUGGY CODE ###

#A,B,C,D=map(int,input().split(" "))

import collections

mod=2019
a=input()

N=len(a)
t=[0]*mod
ans=0

for i in range(N):
  u=int(a[i::])
  v=u % mod
  t[v] += 1
  
#tt = collections.Counter(t)

for i in range(len(t)):
  if i==0:
    ans += t[i]
  else:
    ans += (t[i]-1)*t[i]//2

print(ans)

### FIXED CODE ###

mod=2019
a=input()

N=len(a)
t=[0]*mod
t[0]=1

w=1
u=0

for i in range(N):
  u=int(a[N-1-i]) * w + u
  v=u % mod
  t[v] += 1
  w *=10
  w %= mod

ans=0
for i in t:
  ans += (i-1)*i//2

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

X = str(input())
while X.count("ST") > 0:
  X = X.replace("ST","")

print(len(X))

### FIXED CODE ###

X = str(input())
X = X.replace("ST","")
lx = len(X)
s_count = 0
t_count = 0
for i in range(lx):
  if X[i] == "S":
    s_count += 1
  else:
    if s_count:
      s_count -= 1
    else:
      t_count += 1
   
print(s_count + t_count)
### BUGGY CODE ###

x, y, z, k = map(int, input().split())
cs = list(map(int, input().split()))
bs = list(map(int, input().split()))
a_s = list(map(int, input().split()))
a_s.sort(reverse=True)
bs.sort(reverse=True)
cs.sort(reverse=True)

list = []
i = -1
flag = True
minlist = 0
for a in a_s:
    if minlist >= (a + bs[0] + cs[0]):
        break
    for b in bs:
        if minlist >= (a + b + cs[0]):
            break
        for c in cs:
            abc = a + b +c
            if minlist >= abc:
                break
            # if i >= k:
            if flag and i >= k:
                list.sort(reverse=True)
                minlist = list[k]
                flag = False

            list.append(abc)
            i += 1
list.sort(reverse=True)
for i in range(k):
    print(list[i])


### FIXED CODE ###

x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

ab = []
for ai in a:
  for bi in b:
    ab.append(ai + bi)
ab.sort(reverse = True)

abc = []

for abi in ab[:k]:
  for ci in c:
    abc.append(abi + ci)
abc.sort(reverse = True)

for abci in abc[:k]:
  print(abci)
### BUGGY CODE ###

def main2():
    #1:初期化
    N,W = map(int,input().split())
    wv = []
    for _ in range(N):
        wv.append(list(map(int,input().split())))
    dp = [[W+1]*(1000*N+1) for i in range(N+1)] #valueの最大値は10**3なので全てが10**3でも入るような配列を用意．
    #print(*dp,sep="\n")

    #2:初期値(dp[0][0]だけだと結果が合わない)
    for i in range(N+1):
        dp[i][0] = 0

    #3:dp実行部(貰うDP)
    for i in range(1,N+1):
        for j in range(1,1000*N+1):
            if wv[i-1][1] <= j: #dpの横が重さだが，jが重さ以下ならそもそも入れられない．
                dp[i][j] = min(dp[i-1][j], dp[i-1][j-wv[i-1][1]]+wv[i-1][0])
            else:
                dp[i][j] = dp[i-1][j]
            #print(i,j)
            #print(*dp,sep="\n")

    #4:出力
    #print(*dp,sep="\n")
    output = 0
    for i in range(1000*N+1):
        if dp[N][i] <= W:
            output = i
    print(output)

if __name__ == '__main__':
    main2()

### FIXED CODE ###

def main():
    #1:初期化
    N,W = map(int,input().split())
    dp = [W+1]*(N*10**3+1)

    #2:初期値
    dp[0] = 0

    #3:dp実行部(貰うDP)
    for i in range(N):
        w, v = map(int,input().split())
        for i in range(N*10**3, v-1, -1):
            tmp = dp[i-v] + w
            if dp[i] > tmp:
                dp[i] = tmp
        #print(dp,sep="\n")

    #4:出力
    output = 0
    for i in range(N*10**3+1):
        if dp[i] <= W:
            output = i
    print(output)

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

N = int(input())

A = list(map (int, input().split()))
B = 1

for i in range(N):
    B *= A[i]

if B > 10**18:
    print(-1)
else:
    print(B)

### FIXED CODE ###

N = int(input())

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

res = A[0]

if 0 in A:
    print(0)
    exit()

for i in range(N-1):
    res = res*A[i+1]
    if res > 10**18:
        res = -1
        break



print(res)
### BUGGY CODE ###

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

for i in range(1,n+1):
    num=a.count(i)
    while True:
        if i in a:
            a.remove(i)
        else:
            break
    print(num)

### FIXED CODE ###

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

cnt=[0]*(n+1)
for i in range(n-1):
    cnt[a[i]]+=1

for i in range(1,n+1):
    print(cnt[i])
### BUGGY CODE ###

n = int(input())
count = 0
for i in range(1,n):
    for j in range(1,n):
        if i*j <= n-1:
            count += 1
        else:
            continue
print(count)


### FIXED CODE ###

import math
n = int(input())
count = 0
for i in range(1,n):
    for j in range(i,n):
        if i*j <= n-1:
            if i != j:
                count += 2
            else:
                count += 1
        else:
            break
print(count)
### BUGGY CODE ###

from collections import deque

H, W = map(int, input().split())
S = []
white_num = 0
for _ in range(H):
    s = input()
    white_num += s.count('.')
    S.append(s)

C = [[-1]*W for _ in range(H)]
C[0][0] = 0
q = deque()
q.append((0, 0, 0))
xlist = [0, 0, 1, -1]
ylist = [1, -1, 0, 0]
while len(q) > 0:
    x, y, c = q.popleft()
    C[x][y] = c + 1
    for i in range(4):
        mx = x + xlist[i]
        my = y + ylist[i]
        if mx < 0 or my < 0 or mx >= H or my >= W or S[mx][my] == '#' or C[mx][my] >= 0:
            continue
        q.append((mx, my, c+1))
if C[H-1][W-1] == -1:
    print(-1)
else:
    print(white_num - C[H-1][W-1])


### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
S = ['#'*(W+2)]
white_num = 0
for _ in range(H):
    s = input()
    white_num += s.count('.')
    S.append('#'+s+'#')
S.append('#'*(W+2))

C = [[-1]*(W+2) for _ in range(H+2)]
C[1][1] = 1
q = deque()
q.append((1, 1))
xlist = [0, 0, 1, -1]
ylist = [1, -1, 0, 0]
while len(q) > 0:
    x, y = q.popleft()
    for i in range(4):
        mx = x + xlist[i]
        my = y + ylist[i]
        if S[mx][my] == '#' or C[mx][my] >= 0:
            continue
        C[mx][my] = C[x][y] + 1
        q.append((mx, my))
if C[H][W] == -1:
    print(-1)
else:
    print(white_num - C[H][W])
### BUGGY CODE ###

#!/usr/bin/env python3

import sys, math, copy
from collections import deque
# import fractions, itertools
# import numpy as np
# import scipy

HUGE = 2147483647
HUGEL = 9223372036854775807
ABC = "abcdefghijklmnopqrstuvwxyz"

def adj_node(path, neighbor):
    for end in [path[0], path[-1]]:
        for node in neighbor[end - 1]:
            if node not in path:  # slow
                is_begin = (end == path[0])
                return node, is_begin
    return None, True

def get_path():
    n, m = map(int, input().split())
    am = []
    bm = []
    for i in range(m):
        a, b = map(int, input().split())
        am.append(a)
        bm.append(b)
    assert len(am) == len(bm) == m

    neighbor = [[] for j in range(n)]
    for i in range(m):
        a, b = am[i], bm[i]
        neighbor[a - 1].append(b)
        neighbor[b - 1].append(a)

    path = deque([am[0], bm[0]])
    for j in range(10 ** 6):
        node, is_begin = adj_node(path, neighbor)
        if node is None:
            return path
        if is_begin:
            path.appendleft(node)
        else:
            path.append(node)

def main():
    path = get_path()
    print(len(path))
    print(" ".join(map(str, path)))

main()


### FIXED CODE ###

#!/usr/bin/env python3

import sys, math, copy
from collections import deque
# import fractions, itertools
# import numpy as np
# import scipy

HUGE = 2147483647
HUGEL = 9223372036854775807
ABC = "abcdefghijklmnopqrstuvwxyz"

def adj_node(path, paths, neighbor):
    for end in [path[0], path[-1]]:
        for node in neighbor[end - 1]:
            if node not in paths:
                is_begin = (end == path[0])
                return node, is_begin
    return None, True

def get_path():
    n, m = map(int, input().split())
    am = []
    bm = []
    for i in range(m):
        a, b = map(int, input().split())
        am.append(a)
        bm.append(b)
    assert len(am) == len(bm) == m

    neighbor = [[] for j in range(n)]
    for i in range(m):
        a, b = am[i], bm[i]
        neighbor[a - 1].append(b)
        neighbor[b - 1].append(a)

    path = deque([am[0], bm[0]])
    paths = set(path)
    for j in range(10 ** 6):
        node, is_begin = adj_node(path, paths, neighbor)
        if node is None:
            return path
        paths.add(node)
        if is_begin:
            path.appendleft(node)
        else:
            path.append(node)

def main():
    path = get_path()
    print(len(path))
    print(" ".join(map(str, path)))

main()
### BUGGY CODE ###

from collections import Counter


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())
a = list(map(int, input().split()))

c = Counter(a)
div = [make_divisors(i) for i in a]

ans = 0
for i in range(n):
    val = set(div[i]) & set(a)
    if len(val) == 1:
        if c[list(val)[0]] == 1:
            ans += 1

print(ans)


### FIXED CODE ###

from collections import Counter

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

# new = [key for key, val in Counter(a).most_common() if val == 1]
prime = [1] * 1000010

for i in set(a):
    # if prime[i]:
    for j in range(i + i, 1000001, i):
        prime[j] = 0

c = Counter(a)
ans = 0
for i in a:
    if prime[i] and c[i] == 1:
        ans += 1
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000000)
N, Q = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(N-1):
  a, b = map(lambda x:int(x)-1, input().split())
  graph[a] += [b]
  graph[b] += [a]

cnt = [0] * N
used = [0] * N
for _ in range(Q):
  p, x = map(int, input().split())
  p -= 1 
  cnt[p] += x

def dfs(u, pre):
  used[u] += 1
  if sum(used) == N:
    return
  for v in graph[u]:
    if v != pre:
      cnt[v] += cnt[u]
      dfs(v, u)
  return

dfs(0, -1)
print(*cnt)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.buffer.readline
def dfs(G,v,p):
    for nv in G[v]:
        if(nv==p):
            continue
        point[nv]+=point[v]
        dfs(G,nv,v)

N,Q=map(int,input().split())
G=[[] for i in range(N)]
for i in range(N-1):
    a,b=map(lambda x:int(x)-1,input().split())
    G[a].append(b)
    G[b].append(a)
point=[0]*N
for i in range(Q):
    p,x=map(int,input().split())
    point[p-1]+=x
dfs(G,0,-1)
print(*point)
### BUGGY CODE ###

N = int(input())

def f(n):
    flag = False
    #total = 0
    ans = 0
    i = 150
    for x in range(1,i):
        for y in range(1,i-x):
            for z in range(1,i-(x+y)):
                if (x + y + z)**2 - (x*y + y*z + x*z) == n:
                    #total += 1
                    flag = True
                    break
            if flag:
                break
        if flag:
            break
    if x == i-1:
        ans = 0
    elif x == y and  y== z:
        ans = 1
    elif x == y or y == z or x == z:
        ans = 3
    else:
        ans = 6
    return ans

for i in range(1,N+1):
    print(f(i))

### FIXED CODE ###

N = int(input())


ans = [0]*(N+1)
i = 102
for x in range(1,i):
    for y in range(1,i):
        for z in range(1,i):
            total = (x + y + z)**2 - (x*y + y*z + x*z)
            if total <= N:
                ans[total] += 1

for i in range(1,N+1):
    print(ans[i])
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
S = []
P = A[:N]
Q = A[2*N:]
for i in range(N):
    Q[i] *= -1
R = A[N:2*N]
p = [0]*(N+1)
q = [0]*(N+1)
import heapq
heapq.heapify(P)
heapq.heapify(Q)
sp = sum(P)
sq = sum(Q)
p[0] = sp
q[0] = sq

for i in range(1,N+1):
    heapq.heappush(P,R[i-1])
    heapq.heappop(P)
    heapq.heappush(Q,-R[-i])
    heapq.heappop(Q)
    sp = sum(P)
    sq = sum(Q)
    p[i] = sp
    q[i] = sq
ans = -(10**100)
for k in range(N+1):
    ans = max(ans,p[k] + q[N-k])
    
print(ans)


### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
S = []
P = A[:N]
Q = A[2*N:]
for i in range(N):
    Q[i] *= -1
R = A[N:2*N]
p = [0]*(N+1)
q = [0]*(N+1)
import heapq
heapq.heapify(P)
heapq.heapify(Q)
sp = sum(P)
sq = sum(Q)
p[0] = sp
q[0] = sq

for i in range(1,N+1):
    heapq.heappush(P,R[i-1])
    x = heapq.heappop(P)
    heapq.heappush(Q,-R[-i])
    y = heapq.heappop(Q)
    sp = sp + R[i-1] - x
    sq = sq - R[-i] - y
    p[i] = sp
    q[i] = sq
ans = -(10**100)
for k in range(N+1):
    ans = max(ans,p[k] + q[N-k])
    
print(ans)
### BUGGY CODE ###

from collections import Counter
n = int(input())
s = list(input())
mn = 10**6
for i in range(n-1):
    left = dict(Counter(s[:i]))
    right = dict(Counter(s[i+1:]))
    count = 0
    if 'W' in left:
        count += left["W"]
    if 'E' in right:
        count += right['E']
    mn = min(mn,count)
    if mn==count:
        ans = i
print(mn)

### FIXED CODE ###

n = int(input())
s = list(input())
ruiseki = []
W = 0
for i in range(n):
    if s[i]=="W":
        W += 1
    ruiseki.append(W)

mn = 10**6
for i in range(n):
    if i==0:
        left_W = 0
        right_E = (n-1)-(ruiseki[n-1]-ruiseki[0])
    elif i==n-1:
        left_W = ruiseki[n-2]
        right_E = 0
    else:
        left_W = ruiseki[i-1]
        right_E = (n-(i+1))-(ruiseki[n-1]-ruiseki[i])
    
    ans = left_W + right_E
    mn = min(mn,ans)
print(mn)
### BUGGY CODE ###

import sys, math, itertools, collections, bisect, heapq
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1
dydx4 = ((-1,0),(0,-1),(0,1),(1,0))
def check(i,j):
  return 0 <= i < h and 0 <= j < w 
def on_block(i,j):
  return S[i][j] == "#"
h,w = map(int,input().split())
ci,cj = map(int,input().split())
ci-=1;cj-=1
gi,gj = map(int,input().split())
gi-=1;gj-=1
S = [list(input()) for i in range(h)]
grid = [[inf] * w for i in range(h)]
grid[ci][cj] = 0
que = []
que.append((0,ci,cj))
while que:
  now,si,sj = heapq.heappop(que)
  if now > grid[si][sj]:continue
  for di,dj in dydx4:
    ni = si + di
    nj = sj + dj
    if not check(ni,nj):continue
    if on_block(ni,nj): continue
    else:
      if now < grid[ni][nj] :
        grid[ni][nj] = now
        heapq.heappush(que,(now,ni,nj))
  for i in range(si-2,si+3):
    for j in range(sj-2,sj+3):
      if not check(i,j):continue
      if on_block(i,j):continue
      else:
        if now + 1 < grid[i][j] :
          grid[i][j] = now + 1
          heapq.heappush(que,(now+1,i,j))
print(grid[gi][gj] if grid[gi][gj] != inf else -1)
# print(*grid,sep = "\n")

### FIXED CODE ###

import sys, math, itertools, collections, bisect, heapq
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1
dydx4 = ((-1,0),(0,-1),(0,1),(1,0))
def check(i,j):
  return 0 <= i < h and 0 <= j < w 
def on_block(i,j):
  return S[i][j] == "#"
h,w = map(int,input().split())
ci,cj = map(int,input().split())
ci-=1;cj-=1
gi,gj = map(int,input().split())
gi-=1;gj-=1
S = [list(input()) for i in range(h)]
grid = [[inf] * w for i in range(h)]
grid[ci][cj] = 0
que = collections.deque()
que.append((0,ci,cj))
while que:
  now,si,sj = que.popleft()
  if now > grid[si][sj]:continue
  for di,dj in dydx4:
    ni = si + di
    nj = sj + dj
    if not check(ni,nj):continue
    if on_block(ni,nj): continue
    else:
      if now < grid[ni][nj] :
        grid[ni][nj] = now
        que.appendleft((now,ni,nj))
        # heapq.heappush(que,(now,ni,nj))
  for i in range(si-2,si+3):
    for j in range(sj-2,sj+3):
      if not check(i,j):continue
      if on_block(i,j):continue
      else:
        if now + 1 < grid[i][j] :
          grid[i][j] = now + 1
          que.append((now+1,i,j))
          # heapq.heappush(que,(now+1,i,j))
print(grid[gi][gj] if grid[gi][gj] != inf else -1)
# print(*grid,sep = "\n")
### BUGGY CODE ###

N = int(input())
A = [int(i) for i in input().split()]

from fractions import gcd

L = [0, 0]
for ai in A:
    L.append(gcd(L[-1], ai))

R = [0, 0]
for ai in A[::-1]:
    R.insert(0, gcd(R[0], ai))

print(max(gcd(l, r) for l, r in zip(L, R)))


### FIXED CODE ###

N = int(input())
A = [int(i) for i in input().split()]

from fractions import gcd

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

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

print(max(gcd(l, r) for l, r in zip(L, R)))
### BUGGY CODE ###

from heapq import heappush, heappop, merge
from collections import defaultdict, deque

N, Q = map(int, input().split())
events = []
for _ in range(N):
    s, t, x = map(int, input().split())
    events.append((s-x, 1, x))
    events.append((t-x, -1, x))
events = deque(sorted(events))
D = []
for _ in range(Q):
    D.append(int(input()))

constructions = []
under_construction = defaultdict(bool)
ans = ''
for d in D:
    while events:
        if events[0][0] > d:
            break
        _, flag, coord = events.popleft()            
        if flag > 0:
            heappush(constructions, coord)
            under_construction[coord] = True
        else:
            under_construction[coord] = False
    while constructions:
        x = heappop(constructions)
        if under_construction[x]: # x is the minimum coordinate under construction
            heappush(constructions, x)
            ans += str(x) + '\n'
            break
    else: # no constructions
        ans += '-1\n'
print(ans)

### FIXED CODE ###

from heapq import heappush, heappop, merge
from collections import defaultdict
import sys
F = sys.stdin
def single_input(): return F.readline().strip("\n")
def line_input(): return F.readline().strip("\n").split()

def solve():
    N, Q = map(int, line_input())
    events = []
    for _ in range(N):
        s, t, x = map(int, line_input())
        events.append((s-x, 1, x))
        events.append((t-x, -1, x))
    for _ in range(Q):
        d = int(single_input())
        events.append((d, 2, d))
    events = sorted(events)

    constructions = []
    under_construction = defaultdict(bool)
    ans = ''
    for _, flag, coord in events:
        if flag == 1:
            heappush(constructions, coord)
            under_construction[coord] = True
        elif flag == -1:
            under_construction[coord] = False
        else:
            while constructions:
                x = heappop(constructions)
                if under_construction[x]: # x is the minimum coordinate under construction
                    heappush(constructions, x)
                    ans += str(x) + '\n'
                    break
            else: # no constructions
                ans += '-1\n'
    print(ans)
    
if __name__ == "__main__":
    solve()
### BUGGY CODE ###

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

cnt = 0
for i in range(n):
    for j in range(n):
        if i==j:
            continue

        if a[i]%a[j]==0:
            break
    else:
        cnt += 1
    continue

print(cnt)

### FIXED CODE ###

from collections import Counter


n = int(input())
a = list(map(int, input().split()))
c = Counter(a) # Count num and construct dictionary
c = sorted(c.items(), key=lambda x:x[0]) # align key
ans = 0
isOK = [True] * (10**6+1)

for k, v in c:
    if not isOK[k]:
        continue

    if v > 1:
        for i in range(k, len(isOK), k):
            isOK[i] = False
        continue

    ans += 1
    for i in range(2*k, len(isOK), k):
        isOK[i] = False

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

N = int(input())

def num_divisors_table(n):
  table = [0] * (n + 1)
  for i in range(1, n + 1):
    for j in range(i, n + 1, i):
      table[j] += j
  return sum(table)

print(num_divisors_table(N))

### FIXED CODE ###

N = int(input())

def num_divisors_table(n):
  table = [0] * (n + 1)
  for i in range(1, n + 1):
    for j in range(i, n + 1, i):
      table[j] += j
  return sum(table)

print(num_divisors_table(N))
### BUGGY CODE ###

N = int(input())
S = input()
St = []
for i in range(N):
  St += [ord(S[i])-97]
  
#初期化
dp=[[0 for i in range(N+1)] for j in range(N+1)]

#DP:dp[i][j] Sのi文字目以降とj文字目以降の最大マッチング
for i in range(N-1,-1,-1):
  for j in range(N-1, i-1, -1):
    dp[i][j] = max(dp[i][j+1],dp[i+1][j])
    if St[i] == St[j]:
      dp[i][j] = min(max(dp[i][j], dp[i+1][j+1]+1), j-i)
      
print(max(sum(dp, [])))

### FIXED CODE ###

N = int(input())
S = input()
from collections import deque

def is_ok(l):
    hs = set()
    q = deque()
    for i in range(N-l+1):
        h = S[i:i+l]
        if h in hs:
            return True
        q.append(h)
        if len(q) >= l:
            hs.add(q.popleft())
    return False

ok = 0
ng = N//2+1
while ng-ok > 1:
    m = (ng+ok)//2
    if is_ok(m):
        ok = m
    else:
        ng = m
print(ok)