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

class PreallocatedQueue:
    def __init__(self, n, init_val):
        self.queue = [init_val] * n #根にサイズを負の値で格納する。
        self.l = 0
        self.r = 0
        self.n = n
        self.init_val = init_val
        self.count = 0

    def append(self, val):
        if self.count == self.n:
            if self.r == 0:
                self.queue = self.queue + [self.init_val] * self.n
            else:
                self.queue = self.queue[self.l:] + self.queue[:self.r] + [self.init_val] * self.n
                self.l = 0
            self.r = self.n
            self.n *= 2
        self.queue[self.r] = val
        self.r = (self.r + 1) % self.n
        self.count += 1

    def popleft(self):
        if self.count == 0:
            raise IndexError('popleft from empty queue')
        val = self.queue[self.l]
        self.l = (self.l + 1) % self.n
        self.count -= 1
        return val

    def pop(self):
        if self.count == 0:
            raise IndexError('pop from empty queue')
        val = self.queue[self.r - 1]
        self.r = (self.r - 1) % self.n
        self.count -= 1
        return val
    
    def size(self):
        return self.count
    
    def __bool__(self):
        return self.count != 0

def fast_bellman_ford(n, s, graph, edge_n, init_val): #どう？
    d = [init_val] * n
    d[s] = 0
    q = PreallocatedQueue(edge_n, 0)
    q.append(s)
    for _ in range(n):
        m = q.count
        for _ in range(m):
            vf = q.popleft()
            for vt, w in graph[vf]:
                if d[vt] > d[vf] + w:
                    d[vt] = d[vf] + w
                    q.append(vt)
        if not q:
            break
    if q: #閉路の存在
        minus_inf = -float('inf')
        while q:
            m = q.count
            for _ in range(m):
                vf = q.popleft()
                for vt, w in graph[vf]:
                    if d[vt] > d[vf] + w:
                        d[vt] = minus_inf
                        q.append(vt)
    return d

n, m = map(int, input().split())
graph = [[] for _ in range(n)]
for i in range(m):
    a, b, w = map(int, input().split())
    graph[a-1].append((b-1, -w))
d = fast_bellman_ford(n, 0, graph, 2 * m, float('inf'))
print(-d[-1] if d[-1] != -float('inf') else 'inf')






### FIXED CODE ###

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

edges = []
for i in range(m):
    a, b, w = map(int, input().split())
    edges.append((a-1, b-1, w))

init_val = -10 ** 9 * 1000
d = [init_val] * n
d[0] = 0
for _ in range(n):
    updated = False
    for a, b, w in edges:
        if d[a] != init_val and d[b] < d[a] + w:
            d[b] = d[a] + w
            updated = True
    if not updated:
        break
if updated: #閉路の存在
     for a, b, w in edges:
        if d[a] != init_val and d[b] < d[a] + w:
            d[b] = d[a] + w
            if b == n - 1:
                print('inf')
                quit()
print(d[n-1])
### BUGGY CODE ###

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

visited=[-1 for i in range(N)]
Q,K=map(int,input().split())
visited[K-1]=0
q=[K-1]
while q:
  u=q.pop(0)
  for v,d in tree[u]:
    if visited[v]==-1:
      visited[v]=visited[u]+d
      q.append(v)
    
for i in range(Q):
  x,y=map(int,input().split())
  print(visited[x-1]+visited[y-1])

### FIXED CODE ###

N=int(input())
tree=[[] for i in range(N)]
for i in range(N-1):
  a,b,c=map(int,input().split())
  tree[a-1].append((b-1,c))
  tree[b-1].append((a-1,c))
from collections import deque
visited=[-1 for i in range(N)]
Q,K=map(int,input().split())
visited[K-1]=0
q=deque([])
q.append(K-1)
while q:
  u=q.popleft()
  for v,d in tree[u]:
    if visited[v]==-1:
      visited[v]=visited[u]+d
      q.append(v)
    
for i in range(Q):
  x,y=map(int,input().split())
  print(visited[x-1]+visited[y-1])
### BUGGY CODE ###

N=int(input())
ans=1
for i in range(1,N+1):
  ans*=i

result=ans%(10**9+7)
print(result)

### FIXED CODE ###

import math
N=int(input())
ans=1

ans=math.factorial(N)
result=ans%(10**9+7)
print(result)
### BUGGY CODE ###

import copy
a,b,c,k = map(int,input().split())

if a == b == c:
    print(0)
    exit()

cnt = 0
while True:
    if cnt >= k:
        print(a - b)
        break
    aa = copy.deepcopy(a)
    bb = copy.deepcopy(b)
    cc = copy.deepcopy(c)

    a = bb + cc
    b = aa+cc
    c = aa + bb
    cnt += 1
    if abs(a-b) >= 10**18:
        print('Unfair')
        break



### FIXED CODE ###

a,b,c,k = map(int,input().split())

x = abs(a-b)
if x > 10**18:
    print('Unfair')
else:
    if k % 2 == 0:
        print(a - b)
    else:
        print(b-a)
### BUGGY CODE ###

if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split()))

    sum_list = [a[i]*a[j] for i in range(0, n-1) for j in range(i+1, n)]

    print(sum(sum_list) % (10**9 + 7))




### FIXED CODE ###

if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split()))
    cumsum_a = [0] * len(a)
    cumsum_a[0] = a[0]
    for i in range(1, len(a)):
        cumsum_a[i] += cumsum_a[i-1] + a[i]

    sum_val = 0
    num = 10 ** 9 + 7
    for i in range(0, n - 1):
        sum_val += a[i] * (cumsum_a[-1] - cumsum_a[i])
        if sum_val > num:
            sum_val %= num
    print(sum_val)
### BUGGY CODE ###

from collections import defaultdict
MAX_N = 10 ** 3 + 1
MAX_M = 2 * (10 ** 3) + 1
INF = -(10 ** 100)

def bfs(graph, N, M):
    que = []
    que.append([0, 0])
    visited = defaultdict(list)
    result = INF
    while (len(que) > 0):
        now = que[0]
        que.pop(0)

        pos = now[0]
        cost = now[1]

        if (pos in visited):
            visited_cost = visited[pos][0]
            visited_cnt = visited[pos][1]
            if (visited_cost >= cost):
                continue
            if (visited_cnt >= MAX_N):
                continue
            visited[pos] = [cost, visited_cnt + 1]
        else:
            visited[pos] = [cost, 0]

        if (pos == N - 1):
            result = max(result, cost)

        for val in graph[pos]:
            nxt = val[0]
            nxt_cost = val[1]
            if (nxt not in visited):
                que.append([nxt, nxt_cost + cost])
            elif(nxt_cost + cost > visited[nxt][0]):
                que.append([nxt, nxt_cost + cost])
    if (visited[N - 1][1] >= MAX_N):
        return (0, False)
    return (result, True)


if __name__ == "__main__":
    N, M = map(int, input().split())
    graph = defaultdict(list)
    for x in range(M):
        a,b,c = map(int, input().split())
        a -= 1
        b -= 1
        graph[a].append([b, c])
    res,ok = bfs(graph, N, M)
    if (not ok):
        print ('inf')
    else:
        print (res)


### FIXED CODE ###


MAX_N = 10 ** 3 + 10
MAX_M = 2 * (10 ** 3) + 1
INF = 10 ** 13

def bfs(graph, N, M):
    que = []
    que.append([0, 0])
    visited = [-INF for x in range(MAX_N)]
    update_cnt = [0 for x in range(MAX_N)]
    result = -INF
    while (len(que) > 0):
        now = que[0]
        que.pop(0)

        pos = now[0]
        cost = now[1]
        if (visited[pos] > cost):
            continue
        for val in graph[pos]:
            nxt = val[0]
            nxt_cost = val[1]

            if (cost + nxt_cost > visited[nxt] and update_cnt[nxt] < MAX_M):
                visited[nxt] = cost + nxt_cost
                update_cnt[nxt] += 1
                que.append([nxt, nxt_cost + cost])

    if (update_cnt[N - 1] >= MAX_N):
        return (0, False)
    return (visited[N - 1], True)


if __name__ == "__main__":
    N, M = map(int, input().split())
    graph = [[] for x in range(MAX_N)]
    for x in range(M):
        a,b,c = map(int, input().split())
        a -= 1
        b -= 1
        graph[a].append([b, c])
    res,ok = bfs(graph, N, M)
    if (not ok):
        print ('inf')
    else:
        print (res)
### BUGGY CODE ###

import collections
n,m=map(int,input().split())
A=[]
for i in range(n):
  A.append([int(_) for _ in input().split()])
D=dict()
for i in range(m):
  D[i+1]=1
ans=n
for _ in range(m):
  p=[]
  append=p.append
  for i in range(n):
    for j in range(m):
      aij=A[i][j]
      if D[aij]==1:
        append(aij)
        break
  a,b=collections.Counter(p).most_common()[0]
  if b<ans:
    ans=b
  D[a]=0
print(ans)

### FIXED CODE ###

import collections
n,m=map(int,input().split())
A=[]
for i in range(n):
  A.append([int(_) for _ in input().split()])
D=dict()
for i in range(m):
  D[i+1]=1
ans=n
for _ in range(m):
  p=[]
  for i in range(n):
    for j in range(m):
      if D[A[i][j]]==1:
        p.append(A[i][j])
        break
  pp=collections.Counter(p).most_common()
  a,b=pp[0]
  ans=min(ans,b)
  D[a]=0
print(ans)
### BUGGY CODE ###

from bisect import bisect_left

n = int(input())
lll = list(map(int, input().split()))
lll.sort()
ans = 0

for i in range(n - 2):
    li = lll[i]
    for j in range(i + 1, n - 1):
        k = bisect_left(lll, li + lll[j], lo=j)
        ans += k - j - 1
print(ans)


### FIXED CODE ###

from bisect import bisect_left

n = int(input())
lll = list(map(int, input().split()))
lll.sort()
ans = 0

for i in range(n - 2):
    li = lll[i]
    for j in range(i + 1, n - 1):
        k = bisect_left(lll, li + lll[j], lo=j)
        ans += k - j - 1
print(ans)
### BUGGY CODE ###

data_num = int(input())
price = list([int(input()) for i in range(data_num)])
cnt = 0
deff_price = -999999999
tmp_price = 0

for i in range(data_num-1):
    tmp_price = max(price[i+1:])-price[i]
    if tmp_price>deff_price:
            deff_price = tmp_price

print(str(deff_price))

### FIXED CODE ###

data_num = int(input())
cnt = 0
deff_price = -999999999
min_price = 0
tmp_price = 0

for i in range(data_num):
    price = int(input())
 
    if i ==0:
        min_price = price
    elif price - min_price > deff_price:
        deff_price = price - min_price
    
    if price < min_price:
        min_price = price

print(str(deff_price))
### BUGGY CODE ###

# N,Kの把握
l1 = list(map(int, input().split()))
N = l1[0]
K = l1[1]
 

#空リストを作成。a,bを把握し、リストにaを追加、b回。これをN回くりかえし
l3 = []
for i in range(N):
	l2 = list(map(int, input().split()))
	a = l2[0]
	b = l2[1]
	if len(l3) >= K :
		if max(l3) <= a:
			pass #リストの要素数がKを上回っている場合、要素の最大値よりも大きい数は追加しない。
		else:
			adl=[a] * b
			l3 = l3 + adl
			for j in range(len(l3)-K):
				l3.remove(max(l3))
	else:
		adl=[a] * b
		l3 = l3 + adl
 
# リストをソートし、K番目を出力
l3.sort()
print(str(l3[K-1]))

### FIXED CODE ###

# N,Kの把握
l1 = list(map(int, input().split()))
N = l1[0]
K = l1[1]

#リストをすぐに作成するのが悪手。数値と回数をセット作成
dic = {}
for i in range(N):
	l2 = list(map(int, input().split()))
	a = l2[0]
	b = l2[1]
	if a in dic:
		dic[a] += b #既に存在する数値であればそのまま回数を＋
	else:
		dic.update({a: b}) #新規の数値であれば追加

dic = sorted(dic.items(), key=lambda x:x[0])

x = 0
for key, value in dic: #回数値を足していき、総回数＞＝Kとなったときの数値を出力する。
	x += value
	if x >= K:
		print(str(key))
		break
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

dp = [[] for _ in range(n)] 

for i in range(m):
    dp[ls[i][0] - 1].append(ls[i][1])

for j in range(n):
    dp[j].sort()

for k in range(m):
    th = dp[ls[k][0] - 1].index(ls[k][1]) + 1
    print(str(ls[k][0]).zfill(6) + str(th).zfill(6))

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    n, m = map(int, input().split())

    dp = [[] for _ in range(n)]
    ans = [0] * m

    for i in range(m):
        p, y = map(int, input().split())
        dp[p - 1].append((y, i))
    
    for j, k in enumerate(dp):
        k.sort()    
        for l, (s, t) in enumerate(k):
            ans[t] = str(j + 1).zfill(6) + str(l + 1).zfill(6)
    
    print(*ans, sep = "\n")


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

N,M=[int(s) for s in input().split()]
ls=[int(s) for s in input().split()]
ls.sort(reverse=True)
ls2=[0]
ls.append(-1)
index=0
for i in range(M):
  x=ls2[-1]
  if x<ls[index]:
    ls2.append(ls[index])
    index+=1
  ls2[-1]//=2
  ls2.sort()
#  print(ls2,index,ls)
print(sum(ls2)+sum(ls[index:])+1)


### FIXED CODE ###

import math
N,M=[int(s) for s in input().split()]
ls=[int(s) for s in input().split()]
ls.sort(reverse=True)
x=ls[0]
L=int(math.log2(x))
#2**L より大きいものをわける
def cut(lst,exp):
    for ii in range(len(lst)):
        if ii+1==len(lst):
            break
        if lst[ii+1]<exp:
           break
    return ii
m=M #残り回数
b=-1
ls3=[]
while True:
    if m==0:
        break
    a=b+1
    b=cut(ls,2**L)
    ls2=ls[a:b+1]
    ls3=ls3+ls2
    ls3.sort(reverse=True)
    for j in range(len(ls3)):
        ls3[j]=ls3[j]//2
        m-=1
        if m==0:
            break
    L-=1
#    print(ls3,m,b)
#print(ls3,ls[b+1:])
s=sum(ls3)+sum(ls[b+1:])
print(s)
### BUGGY CODE ###

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

n=int(input())
s=deque([])
cnt=0
for _ in range(n):
    s.append(sorted(deque(list(input()))))
for i in range(n):
    for j in range(n):
        if i<j:
            if s[i]==s[j]:
                cnt+=1
print(cnt)

### FIXED CODE ###

n=int(input())
L=[[] for _ in range(n)]
ans=0
for i in range(n):
    L[i]=sorted(list(input()))
L=sorted(L)
tmp=1
ans=0
for i in range(n-1):
    if L[i]==L[i+1]:
        tmp+=1
    else:
        ans+=tmp*(tmp-1)//2
        tmp=1
ans+=tmp*(tmp-1)//2
print(ans)
### BUGGY CODE ###

import sys


def input():
    return sys.stdin.readline().strip()


def restore(s):
    while len(s) > 1:
        s = s.replace("AA", "B")
        s = s.replace("BB", "A")
        s = s.replace("AB", "")
        s = s.replace("BA", "")
    return s


S = input()
T = input()
q = int(input())
for _ in range(q):
    a, b, c, d = map(int, input().split())
    r_s = restore(S[a - 1 : b])
    r_t = restore(T[c - 1 : d])
    print("YES") if r_s == r_t else print("NO")


### FIXED CODE ###

import sys
from itertools import accumulate


def input():
    return sys.stdin.readline().strip()


def acc(li, n):
    res = [0] * (n + 1)
    for i in range(n):
        if li[i] == "A":
            res[i + 1] = 1
        elif li[i] == "B":
            res[i + 1] = 2
    return list(accumulate(res))


def restore(x, y, li):
    return (li[y] - li[x - 1]) % 3


S = input()
T = input()
N = len(S)
M = len(T)

acc_S = acc(S, N)
acc_T = acc(T, M)

q = int(input())
for _ in range(q):
    a, b, c, d = map(int, input().split())
    v_S = restore(a, b, acc_S)
    v_T = restore(c, d, acc_T)
    print("YES") if v_S == v_T else print("NO")
### BUGGY CODE ###

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

# process
# A[i+k+]^A[i+k+1]=B[i]^B[i+1]となるkを求める
AX = [0]*N
BX = [0]*N
for i in range(N-1):
    AX[i] = A[i]^A[i+1]
    BX[i] = B[i]^B[i+1]
AX[N-1] = (A[N-1]^A[0])
BX[N-1] = (B[N-1]^B[0])

ans = []
for k in range(N):
    i = 0
    while i < N:
        j = i+k
        if j >= N:
            j -= N

        if not BX[i] == AX[j]:
            break
        i += 1
    
    if i == N:
        # kに対応するxを求める
        x = A[k]^B[0]
        ans.append((k, x))

# output
for k, x in ans:
    print("{} {}".format(k,x))


### FIXED CODE ###

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

# process/output
# A[i+k+]^A[i+k+1]=B[i]^B[i+1]となるkを求め,kからxを求める
AX = [A[i]^A[i-1] for i in range(N)]
AX += AX
BX = [B[i]^B[i-1] for i in range(N)]

#print(AX)
#print(BX)

# BXの頭と終わりが同じ数字の並びの場合、その数mを求める
m = 0
for i in range(1, N):
    if BX[m] == BX[i]:
        m += 1
    else:
        m = 0
#print(m)

i, j, k = 0, 0, 0
while k < N:
    while True:
        #print("i,j: {},{},{}".format(i,j,k))
        if AX[i] == BX[j]:
            if j == N-1:
                print(k, A[k]^B[0])
                i += 1
                j = m
                break
            i += 1
            j += 1
        elif j != 0:
            j -= 1
        else:
            i += 1
            break
    
    k = i-j
### BUGGY CODE ###

import sys
from collections import deque
n,m = map(int,sys.stdin.readline().split())
vertices = [[] for _ in range(n+1)]
jumpValue = [[-1,-1,-1] for _ in range(n+1)]
visited = set()
queue = []
temp = []
def bfs(arr,jump):
    temp = []
    for node in arr:
        if jumpValue[node][(jump+1)%3]==-1:
            queue.append([node,jump+1])
        temp = temp+vertices[node]
    return temp
for i in range(m):
    a,b = map(int,sys.stdin.readline().split())
    vertices[a].append(b)
s,t = map(int,sys.stdin.readline().split())
visited.add(s)
queue=deque()
queue.append([s,0])
while(len(queue)>0 ):
    next=queue.popleft()
    if jumpValue[next[0]][next[1]%3] == -1:
        jumpValue[next[0]][next[1]%3] = next[1]
        bfs(vertices[next[0]], next[1])
print(max(jumpValue[t][0]//3,-1))




### FIXED CODE ###

import sys
from collections import deque
n,m = map(int,sys.stdin.readline().split())
vertices = [[] for _ in range(n+1)]
jumpValue = [[-1,-1,-1] for _ in range(n+1)]
queue = []
def bfs(arr,jump):
    for node in arr:
        if jumpValue[node][(jump+1)%3]==-1:
            queue.append([node,jump+1])
for i in range(m):
    a,b = map(int,sys.stdin.readline().split())
    vertices[a].append(b)
s,t = map(int,sys.stdin.readline().split())
queue=deque()
queue.append([s,0])
while(len(queue)>0 ):
    next=queue.popleft()
    if jumpValue[next[0]][next[1]%3] == -1:
        jumpValue[next[0]][next[1]%3] = next[1]
        bfs(vertices[next[0]], next[1])
        if jumpValue[t][0]!=-1:
            break
print(max(jumpValue[t][0]//3,-1))
### BUGGY CODE ###

N = int(input())
A = [int(a) for a in input().split()]
B = []
for n in range(N):
    B.append(A[n])
    B.reverse()
print(*B)

### FIXED CODE ###

from collections import deque

N = int(input())
A = [int(a) for a in input().split()]
B = deque([])
for n in range(N):
    if n % 2 == 0:
        B.append(A[n])
    else:
        B.appendleft(A[n])
if N % 2 == 0:
    print(*B)
else:
    print(*list(B)[::-1])
### BUGGY CODE ###

import copy

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

c = []
find = []
for i in range(N//2+1):
    new_c = copy.deepcopy(c)
    for k in c:
        v = k+S[i]
        if v in S[i+1:]:
            find.append(len(v))
        new_c.append(v)
    if S[i] not in c:
        if S[i] in S[i+1:]:
            find.append(1)
        new_c.append(S[i])
    c = new_c
if len(find)>0:
    print(max(find))
else:
    print(0)

### FIXED CODE ###

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

r=0
i=j=0
while j < N:
    t = S[i:j]
    if t in S[j:]:
        r = max(r, j-i)
        j += 1
    else:
        i += 1
print(r)
### BUGGY CODE ###

n,m=map(int,input().split())
x=[set() for _ in range(n+1)]
lift=[-1 for _ in range(n+1)]
for _ in range(m):
    a,b=map(int,input().split())
    x[a].add(b)
    x[b].add(a)

cnt=0
next={1}
while len(next)>0:
    tmp=set()
    for p in next:
        for q in x[p]:
            if lift[q]==-1: lift[q]=p
            if p in x[q]: x[q].remove(p)
            tmp.add(q)
    next=tmp

if -1 in x[2:]: print("No")
else:
    print("Yes")
    for i in range(2,n+1):
        print(lift[i])

### FIXED CODE ###

n,m=map(int,input().split())
x=[set() for _ in range(n+1)]
lift=[-1 for _ in range(n+1)]
for _ in range(m):
    a,b=map(int,input().split())
    x[a].add(b)
    x[b].add(a)

cnt=0
next={1}
while len(next)>0:
    tmp=set()
    for p in next:
        for q in x[p]:
            if lift[q]==-1:
                tmp.add(q)
                lift[q]=p
            x[q].remove(p)

    next=tmp

if -1 in x[2:]: print("No")
else:
    print("Yes")
    for i in range(2,n+1):
        print(lift[i])
### BUGGY CODE ###

N = int(input())
S = input()
data = set()

for i in range(N-2):
  x = S[i]
  for j in range(i+1,N-1):
    y = S[j]
    for k in range(j+1,N):
      z = S[k]
      data.add(x+y+z)
print(len(data))

### FIXED CODE ###

N = int(input())
S = input()
data = set()
xd,yd = set(),set()
for i in range(N-2):
  x = S[i]
  if x in xd:
    continue
  else:
    xd.add(x)
    yd = set()
  for j in range(i+1,N-1):
    y = S[j]
    if y in yd:
      continue
    else:
      yd.add(y)
    for k in range(j+1,N):
      z = S[k]
      data.add(x+y+z)
print(len(data))
### BUGGY CODE ###

import itertools
from functools import reduce
from operator import mul

N = int(input())
# a, b, x = map(lambda i: int(i), input().split(' '))

def main():
    # hen1 = a / 2
    # hen2 = b - (x / (a * a))
    # print(math.degrees(math.atan(hen2 / hen1)))
    primes = prime_factorize(N)
    if len(primes) == 1:
        print(primes[0] - 1)
        return
    elif len(primes) == 2:
        print(primes[0] + primes[1] - 2)
        return

    min = -1
    for i in range(1, len(primes) + 1):
        for v in itertools.combinations(primes, i):
            a = reduce(mul, list(v))
            b = N // a
            if min == -1 or min > (a + b - 2):
                min = a + b - 2
    print(min)

def prime_factorize(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

main()


### FIXED CODE ###

import math

N = int(input())
# a, b, x = map(lambda i: int(i), input().split(' '))

def main():
    root_n = math.sqrt(N)
    answer = -1
    for a in range(1, int(root_n) + 1):
        if N % a == 0:
            b = N // a
            v = a + b - 2
            if answer == -1 or answer > v:
                answer = v
    print(v)

main()
### BUGGY CODE ###

def main():
    def accumulate(array):
        for i in range(len(array) - 1):
            array[i + 1] += array[i]
        return array

    N = int(input())
    A = list(map(int, raw_input().split()))
    MOD = 10 ** 9 + 7

    X = [[0] * N for i in range(61)]
    for i, a in enumerate(A):
        for j in range(61):
            if (1 << j) & a:
                X[j][i] = 1

    for i in range(61):
        X[i] = accumulate(X[i])


    ans = 0
    for i, a in enumerate(A):
        for j in range(61):
            x = X[j][-1] - X[j][i]
            if (1 << j) & a:
                ans += (1 << j) * ((N - i - 1) - x)
                ans %= MOD

            else:
                ans += (1 << j) * x
                ans %= MOD


    print(ans % MOD)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    def accumulate(array):
        for i in range(len(array) - 1):
            array[i + 1] += array[i]
        return array

    N = int(input())
    A = list(map(int, raw_input().split()))
    MOD = 10 ** 9 + 7

    X = [[0] * N for i in range(61)]
    for i, a in enumerate(A):
        for j in range(61):
            if (1 << j) & a:
                X[j][i] = 1

    for i in range(61):
        X[i] = accumulate(X[i])


    ans = 0
    for i, a in enumerate(A):
        for j in range(61):
            x = X[j][-1] - X[j][i]
            if (1 << j) & a:
                ans += ((1 << j) % MOD) * ((N - i - 1) - x)
                ans %= MOD

            else:
                ans += ((1 << j) % MOD) * x
                ans %= MOD


    print(ans % MOD)


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

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

### FIXED CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
dp=[float('inf') for i in range(n)]
dp[0]=0
dp[1]=abs(h[1]-h[0])
for i in range(2,n):
	for j in range(1,k+1):
		
		if(i-j<0):
			break
		else:
			dp[i]=min(dp[i],dp[i-j]+abs(h[i]-h[i-j]))
print(dp[n-1])
### BUGGY CODE ###

import numpy as np
s = input()
num = len(s)

dp = [0]*num
temp = [0]*2019
for i in range(num):
    temp[int(s[i:]) % 2019] += 1

ans = temp[0]
for t in temp:
    if t > 1:
        ans += t*(t-1)/2

print(int(ans))

### FIXED CODE ###

S=input()
N=len(S)
M=2019

remainder=[0]*M
val=0
for i in range(N):
  val=(int(S[N-1-i])*pow(10,i,M)+val)%M
  remainder[val]+=1

ans=remainder[0]
for i in range(2019):
  ans+=remainder[i]*(remainder[i]-1)//2
print(ans)