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

dhw = [(1,0),(0,-1),(0,1),(-1,0),
( 2,-2),( 2,-1),( 2, 0),( 2, 1),( 2, 2),
( 1,-2),( 1,-1),        ( 1, 1),( 1, 2),
( 0,-2),                        ( 0, 2),
(-1,-2),(-1,-1),        (-1, 1),(-1, 2),
(-2,-2),(-2,-1),(-2, 0),(-2, 1),(-2, 2)]

H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

dst = [[-1]*W for _ in range(H)]
dst[sh][sw] = 0

from collections import deque
dq = deque([(sh, sw)])
while dq:
    h, w = dq.popleft()

    for i in range(4):
        nh = h + dhw[i][0]; nw = w + dhw[i][1]
        if nh < 0 or H <= nh : continue
        if nw < 0 or W <= nw : continue
        if S[nh][nw] == '#': continue
        if dst[nh][nw] == -1:
            dst[nh][nw] = dst[h][w]
        elif dst[h][w] < dst[nh][nw]:
            dst[nh][nw] =  dst[h][w]
        else: continue
        dq.append((nh, nw))

    for i in range(4, 24):
        nh = h + dhw[i][0]; nw = w + dhw[i][1]
        if nh < 0 or H <= nh : continue
        if nw < 0 or W <= nw : continue
        if S[nh][nw] == '#': continue
        if dst[nh][nw] == -1:
            dst[nh][nw] = dst[h][w] + 1
        elif dst[h][w] + 1 < dst[nh][nw]:
            dst[nh][nw] = dst[h][w] + 1
        else: continue
        dq.append((nh, nw))

print(dst[eh][ew])


### FIXED CODE ###

dhw = [(1,0),(0,-1),(0,1),(-1,0),
( 2,-2),( 2,-1),( 2, 0),( 2, 1),( 2, 2),
( 1,-2),( 1,-1),        ( 1, 1),( 1, 2),
( 0,-2),                        ( 0, 2),
(-1,-2),(-1,-1),        (-1, 1),(-1, 2),
(-2,-2),(-2,-1),(-2, 0),(-2, 1),(-2, 2)]

H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

dst = [[-1]*W for _ in range(H)]

from collections import deque
dq = deque([(sh, sw, 0)])
while dq:
    h, w, d = dq.popleft()
    if 0 <= h < H and 0 <= w < W and dst[h][w] < 0 and S[h][w] != '#':
        dst[h][w] = d
    else:
        continue
    for i in range(4): dq.appendleft((h + dhw[i][0], w + dhw[i][1], d))
    for i in range(4, 24): dq.append((h + dhw[i][0], w + dhw[i][1], d+1))

print(dst[eh][ew])
### BUGGY CODE ###

import math
def make_prime_list_2(num):
    if num < 2:
        return []

    # 0のものは素数じゃないとする
    prime_list = [i for i in range(num + 1)]
    prime_list[1] = 0 # 1は素数ではない
    num_sqrt = math.sqrt(num)

    for prime in prime_list:
        if prime == 0:
            continue
        if prime > num_sqrt:
            break

        for non_prime in range(2 * prime, num, prime):
            prime_list[non_prime] = 0

    return [prime for prime in prime_list if prime != 0]
def search_divisor_num_1(num):
    if num < 0:
        return None
    elif num == 1:
        return 1
    else:
        num_sqrt = math.floor(math.sqrt(num))
        prime_list = make_prime_list_2(num_sqrt)

        divisor_num = 1
        for prime in prime_list:
            count = 1
            while num % prime == 0:
                num //= prime
                count += 1
            divisor_num *= count

        if num != 1:
            divisor_num *= 2

        return divisor_num

n = int(input())
ans = 0
for k in range(1,n+1):
    ans += k * search_divisor_num_1(k)

print(ans)


### FIXED CODE ###

n = int(input())
ans = 0
for i in range(1,n+1):
    ans += n//i*(i+n//i*i)//2

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

import itertools
import functools
import math
from collections import Counter
from itertools import combinations
import re

def main_chk():
    N=int(input())
    C=input()

    chk = N - 1
    cnt = 0

    for i in range(N):
        if C[i] == 'W':
            for x in reversed(range(0,chk+1)):
                if C[x] == 'R':
                    chk = x
                    break
            if chk <= i:
                break
            else:
                cnt = cnt + 1
                chk = chk - 1

    print(cnt)

main_chk()


### FIXED CODE ###

import itertools
import functools
import math
from collections import Counter
from itertools import combinations
import re

def main_chk():
    N=int(input())
    C=input()

    chk = N - 1
    cnt = 0

    for i in range(N):
        if C[i] == 'W':
            p = chk
            chk = i
            for x in range(N-i):
                if C[p-x] == 'R':
                    chk = p - x
                    break
            if chk <= i:
                break
            else:
                cnt = cnt + 1
                chk = chk - 1
                if chk <= i + 1:
                    break

    print(cnt)

main_chk()
### BUGGY CODE ###

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

LR = []
for i in range(K):
    L, R = map(int, input().split())
    LR.append([L, R])
    

S = []
for lr in sorted(LR, key=lambda x:x[0]):
    S += list(range(lr[0], lr[1]+1))

dp = [0] * N
dp[0] = 1

#S.sort()

for i in range(1, N):
    for s in S:
        if i - s < 0:break
        dp[i] += dp[i - s]

print(dp[-1] % 998244353)

### FIXED CODE ###

mod = 998244353
N, K = map(int, input().split())

S = []
for i in range(K):
    L, R = map(int, input().split())
    S.append((L, R))

dp = [0] * (N+1)
dpsum = [0] * (N+1)
dp[1] = 1
dpsum[1] = 1

for i in range(2, N+1):
    for s in S:
        l = i - s[1]
        r = i - s[0]
        if r < 1:continue
        l = max(1, l)

        dp[i] += dpsum[r] - dpsum[l-1]
        dp[i] %= mod

    dpsum[i] = (dpsum[i-1] + dp[i]) % mod

print(dp[-1])
### BUGGY CODE ###

n,k=map(int,input().split())
x,y=[[0,0] for i in range(n)],[[0,0] for i in range(n)]
xy=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    x_sub,y_sub=xy[i]
    x[i][0]=x_sub
    x[i][1]=i
    y[i][0]=y_sub
    y[i][1]=i
x.sort()
y.sort()
ans=(10**18)*5
for i1 in range(n):
    for l1 in range(n-i1,1,-1):
        for i2 in range(n):
            for l2 in range(n-i2,1,-1):
                x_sub1=x[i1][0]
                x_sub2=x[i1+l1-1][0]
                y_sub1=y[i2][0]
                y_sub2=y[i2+l2-1][0]
                z=[0]*n
                for i in range(n):
                    if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
                        z[i]=1
                if sum(z)>=k:
                    ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
                else:
                    break
print(ans)


### FIXED CODE ###

n,k=map(int,input().split())
x,y=[[0,0] for i in range(n)],[[0,0] for i in range(n)]
xy=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    x_sub,y_sub=xy[i]
    x[i][0]=x_sub
    x[i][1]=i
    y[i][0]=y_sub
    y[i][1]=i
x.sort()
y.sort()
ans=(10**18)*5
for i1 in range(n):
    for l1 in range(n-i1,1,-1):
        for i2 in range(n):
            for l2 in range(n-i2,1,-1):
                x_sub1=x[i1][0]
                x_sub2=x[i1+l1-1][0]
                y_sub1=y[i2][0]
                y_sub2=y[i2+l2-1][0]
                z=[0]*n
                for i in range(n):
                    if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
                        z[i]=1
                if sum(z)>=k:
                    ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
                else:
                    break
print(ans)
### BUGGY CODE ###

from fractions import Fraction
from collections import Counter
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

MOD = 10**9+7

def main():
    N,*ab = map(int, read().split())

    ab_zero = 0
    a_zero = 0
    b_zero = 0
    ratio = []
    for a, b in zip(*[iter(ab)]*2):
        if a == 0 and b == 0:
            ab_zero += 1
        elif a == 0:
            a_zero += 1
        elif b == 0:
            b_zero += 1
        else:
            ratio.append(Fraction(a, b))
    
    s = Counter(ratio)

    bad = pow(2, a_zero, MOD) + pow(2, b_zero, MOD) - 1
    bad %= MOD
    for k, v in s.items():
        if - 1 / k in s:
            if s[k] != 0:
                bad *= (pow(2, v, MOD) + pow(2, s[-1/k], MOD) -1) % MOD
                bad %= MOD
                s[- 1 / k] = 0
        else:
            bad *= pow(2, v, MOD)
            bad %= MOD

    ans = bad - 1 + ab_zero
    print(ans)
    

if __name__ == "__main__":
    main()


### FIXED CODE ###

from math import gcd
from collections import Counter
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

MOD = 10**9+7

def main():
    N,*ab = map(int, read().split())

    ab_zero = 0
    ratio = []
    for a, b in zip(*[iter(ab)]*2):
        if a == 0 and b == 0:
            ab_zero += 1
        else:
            g = gcd(a, b)
            a //= g
            b //= g
            ratio.append((a, b))
    ab_zero %= MOD
    
    s = Counter(ratio)

    bad = 1
    for k, v in s.items():
        if v == 0:
            continue
        
        a, b = k
        if (-a, -b) in s:
            v += s[(-a, -b)]
            s[(-a, -b)] = 0

        inv = 0
        if (-b, a) in s:
            inv += s[(-b, a)]
            s[(-b, a)] = 0
        if (b, -a) in s:
            inv += s[(b, -a)]
            s[(b, -a)] = 0

        bad *= (pow(2, v, MOD) + pow(2, inv, MOD) -1) % MOD
        bad %= MOD
        s[k] = 0

    ans = (bad + ab_zero -1) % MOD
    print(ans)
    

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

N,M = map(int,input().split())
A = list(map(int,input().split()))
A.sort(reverse=True)
for _ in range(M):
  A[0] //=2
  i = 1
  while i < N:
    if A[0] > A[i]:
      A[0:i-1],A[i-1] = A[1:i], A[0]
      break
    if i == N-1:
      A[0:N-1],A[N-1] = A[1:N],A[0]
    i +=1

print(sum(A))

### FIXED CODE ###

import heapq
N,M = map(int,input().split())
A = list(map(lambda x:int(x)*(-1),input().split()))
heapq.heapify(A)
for _ in range(M):
  heapq.heappush(A,((heapq.heappop(A)*-1)//2)*-1)

print(sum(A)*-1)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**5 + 1)

def main():
    global n, peso, dp, k

    n, k = [int(x) for x in input().split()]
    peso = [int(x) for x in input().split()]
    dp = [-1]*(10**5 + 1)
    
    peso.append(10**9)
    peso.append(10**9)
    
    print(frog(0))
    
def frog(i):
    global n, peso, dp, k
    
    if i >= n - 1:
        return 0

    if dp[i] != -1:
        return dp[i]
    
    dp[i] = 10**9
    for j in range(1, k + 1):
        if i + j < len(peso):
            dp[i] = min(dp[i], abs(peso[i + j] - peso[i]) + frog(i + j))
    
    return dp[i]

main()

### FIXED CODE ###

n, k = [int(x) for x in input().split()]
h = [int(x) for x in input().split()]

def abs(x):
    if x >= 0:
        return x
    return -x

c = [0]
c.append(abs(h[1] - h[0]))
for i in range(2, n):
    cmin = None
    for cur in range(i-1, i-1-k, -1):
        if cur < 0:
            break
        val = abs(h[i] - h[cur]) + c[cur]
        if cmin is None or val < cmin:
            cmin = val
    c.append(cmin)

print(c[-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N = int(input())
S = input()
Q = int(input())
k = list(map(int, input().split()))

for ki in k :
    ret = 0
    d, m, dm = 0, 0, 0
    for i in range(N) :
        if i >= ki :
            j = i - ki
            if S[j] == 'D' :
                d -= 1
                dm -= m
            elif S[j] == 'M' :
                m -= 1

        if S[i] == 'D' :
            d += 1
        elif S[i] == 'M' :
            m += 1
            dm += d
        elif S[i] == 'C' :
            ret += dm
            
    print(ret)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
S = input()
Q = int(input())
k = list(map(int, input().split()))

for ki in k :
    ret = 0
    dp = [0] * 3
    for i in range(N) :
        if i >= ki :
            j = i - ki
            if S[j] == 'D' :
                dp[0] -= 1
                dp[2] -= dp[1]
            elif S[j] == 'M' :
                dp[1] -= 1

        if S[i] == 'D' :
            dp[0] += 1
        elif S[i] == 'M' :
            dp[1] += 1
            dp[2] += dp[0]
        elif S[i] == 'C' :
            ret += dp[2]
            
    print(ret)
### BUGGY CODE ###

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


mod=pow(10,9)+7

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
N = n
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル
for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

from collections import Counter
cnt_a=Counter(a)
list_a=list(cnt_a.keys())
list_a.sort()
num_a=len(list_a)
sa_=0
sa=[0]
for ai in list_a:
    sa_+=cnt_a[ai]
    sa.append(sa_)

ans=0
for i in range(num_a): 
    for j in range(i,num_a):# list_a[i]をmin,list_a[j]をmaxとしてk個選べるか
        k_=sa[j+1]-sa[i]
        if k_>=k:
            mj=0 if k_-cnt_a[list_a[j]]<k else cmb(k_-cnt_a[list_a[j]],k,mod)
            mi=0 if k_-cnt_a[list_a[i]]<k else cmb(k_-cnt_a[list_a[i]],k,mod)
            mij=0 if k_-cnt_a[list_a[j]]-cnt_a[list_a[i]]<k else cmb(k_-cnt_a[list_a[j]]-cnt_a[list_a[i]],k,mod)
            ans+=(list_a[j]-list_a[i])*(cmb(k_,k,mod)-mj-mi+mij)
            #print(list_a[j],list_a[i],cmb(k_,k,mod),mj,mi)
            ans%=mod
            #f(x)の値×list_a[i]をmin,list_a[j]をmaxとしてk個選ぶ選び方
print(ans)


### FIXED CODE ###

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


mod=pow(10,9)+7

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
N = n
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル
for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

from collections import Counter
cnt_a=Counter(a)
list_a=list(cnt_a.keys())
list_a.sort()
num_a=len(list_a)
sa_=0
sa=[0]
for ai in list_a:
    sa_+=cnt_a[ai]
    sa.append(sa_)
ansmin=0
ansmax=0
for i in range(num_a):# list_a[i]がminになる場合の数
    k_=sa[num_a]-sa[i]
    if k_>=k:
        mi=0 if k_-cnt_a[list_a[i]]<k else cmb(k_-cnt_a[list_a[i]],k,mod)
        ansmin+=list_a[i]*(cmb(k_,k,mod)-mi)
        ansmin%=mod
for i in range(num_a):# list_a[i]がmaxになる場合の数
    k_=sa[i+1]
    if k_>=k:
        mi=0 if k_-cnt_a[list_a[i]]<k else cmb(k_-cnt_a[list_a[i]],k,mod)
        ansmax+=list_a[i]*(cmb(k_,k,mod)-mi)
        ansmax%=mod
print((ansmax-ansmin)%mod)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = 1
for i in a:
    ans = ans*i
if ans > 1e18:
    print("-1")
else:
    print(ans)


### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
a.sort()
if a[0]==0:
  print("0")
else:
  ans = 1
  for i in range(n):
    ans = ans*a[i]
    if ans > 1e18:
      print("-1")
      break
  else:
    print(ans)
### BUGGY CODE ###

from numpy import array
l=list(map(int,input().split()))
ans=[int(input()) for i in range(l[2])]
n=l[0]
k=l[1]
q=l[2]
p=array([k]*n)
for num in ans:
  minus=[-1]*(num-1)+[0]+[-1]*(n-num)
  v2=array(minus)
  p=p+v2
for m in p:
  if(m<=0):
    print("No")
  else:
    print("Yes")

### FIXED CODE ###

l=list(map(int,input().split()))
ans=[int(input()) for i in range(l[2])]
n=l[0]
k=l[1]
q=l[2]
p=[k-q]*n
for num in ans:
  r=p[num-1]+1
  p[num-1]=r
for a in p:
  if(a<=0):
    print("No")
  else:
    print("Yes")
### BUGGY CODE ###


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

ans = 0
r = range(N)
for i in r:
    for j in r:
        if j == i: break
        if S[i] == S[j]: continue
        dji = j - i
        for k in r:
            if k == i: break
            if k == j: break
            if S[i] == S[k]: continue
            if S[j] == S[k]: continue
            dkj = k - j
            if dji == dkj: continue
            ans += 1


print(ans)

### FIXED CODE ###


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

r = S.count("R")
g = S.count("G")
b = S.count("B")

all_case = r*g*b

excluded_case = 0
for i in range(N):
    for j in range(i+1, N):
        if S[i] == S[j]: continue
        k = j*2-i
        if k>= N or S[k] == S[i] or S[k] == S[j]: continue
        excluded_case += 1

print(all_case-excluded_case)
### BUGGY CODE ###

n, m = map(int, input().split())
tree = [-i for i in range(n+1)]

for _i in range(m):
    x, y, z = map(int, input().split())
    while tree[x]>0:
        x = tree[x]
    while tree[y]>0:
        y = tree[y]
    if x==y:
        continue
    else:
        tree[x] = y
print(sum(1 for i in tree if i<0))

### FIXED CODE ###

n, m = map(int, input().split())
tree = [-i for i in range(n+1)]
rank = [1 for _i in range(n+1)]
def search_root(num, tree=tree):
    if tree[num] < 0:
        return num
    else:
        tree[num] = search_root(tree[num])
        return tree[num]

for _i in range(m):
    x, y, z = map(int, input().split())
    x, y = sorted([search_root(x), search_root(y)])
    if x==y:
        continue
    else:
        if rank[x]<rank[y]:
            rank[y] += 1
            tree[x] = y
        else:
            rank[x] += 1
            tree[y] = x
print(sum(1 for i in tree if i<0))
### BUGGY CODE ###

S = input()[::-1]

length = len(S)
dp = [0] * (length + 2)

times = 1
for x in range(1, length + 1):
    dp[x] = (dp[x - 1] + int(S[x - 1]) * (times % 2019)) % 2019
    times *= 10


cnt = [0] * 2020
for x in range(length + 1):
    cnt[dp[x]] += 1

ans = 0
for c in cnt:
    ans += (c * (c - 1)//2)

print(ans)




### FIXED CODE ###

S = input()[::-1]

length = len(S)
dp = [0] * (length + 2)

times = 1
for x in range(1, length + 1):
    dp[x] += dp[x - 1]
    dp[x] %= 2019
    dp[x] += int(S[x - 1]) * times
    dp[x] %= 2019
    times *= 10
    times %= 2019


cnt = [0] * 2020
for x in range(length + 1):
    cnt[dp[x]] += 1

ans = 0
for c in cnt:
    ans += (c * (c - 1)//2)

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

import sys
import Queue

n = int(raw_input())

graph = [[-1 for i in range(0, n)] for j in range(0, n)]
color = [-1 for i in range(0, n)]
for i in range(0, n - 1):
    u, v, w = map(int, raw_input().split(" "))
    # print("%d %d %d" % (u, v, w))
    graph[u-1][v-1] = w
    graph[v-1][u-1] = w

# for i in range(0, n):
#     for j in range(0, n):
#         sys.stdout.write(str(graph[j][i]) + "\t")
#
#     print("")

queue = Queue.Queue()
sum = 0
next_check = 0

while True:
    if sum >= n:
        break

    for i in range(next_check, n):
        if color[i] < 0:
            queue.put(i)
            color[i] = 0
            sum += 1
            next_check = i
            break

    while True:
        if queue.empty():
            break

        current_node = queue.get()
        for end in range(0, n):
            if graph[current_node][end] > 0 and color[end] < 0:
                color[end] = (color[current_node] + graph[current_node][end] % 2) % 2
                queue.put(end)
                sum += 1

for node in range(0, n):
    print(color[node])


### FIXED CODE ###

import sys
import Queue

n = int(raw_input())

graph = dict()
color = [-1 for i in range(0, n)]
for i in range(0, n - 1):
    u, v, w = map(int, raw_input().split(" "))
    if (u - 1) in graph:
        graph[u - 1].append((v-1, w))
    else:
        graph[u - 1] = [(v-1, w)]

    if (v - 1) in graph:
        graph[v - 1].append((u - 1, w))
    else:
        graph[v - 1] = [(u - 1, w)]

# for start, value_list in graph.items():
#     for end, weight in value_list:
#         print("%s -> %d (%d)" % (start, end, weight))

queue = Queue.Queue()
sum = 0
next_check = 0

while True:
    if sum >= n:
        break

    for i in range(next_check, n):
        if color[i] < 0:
            queue.put(i)
            color[i] = 0
            sum += 1
            next_check = i
            break

    while True:
        if queue.empty():
            break

        current_node = queue.get()
        if current_node in graph:
            for end, weight in graph[current_node]:
                if color[end] < 0:
                    color[end] = (color[current_node] + weight % 2) % 2
                    queue.put(end)
                    sum += 1

for node in range(0, n):
    print(color[node])
### BUGGY CODE ###

N = int(input())

count = 0
for i in range(1, N+1):
	if set(str(i)) != {"3", "5", "7"}:
		continue
	count += 1
print(count)

### FIXED CODE ###

from bisect import bisect_right
from itertools import product, chain

N = int(input())

# product("357", repeat=len(str(N)))
l = list(chain(*[[int("".join(m)) for m in product("357", repeat=i) if set(m) == {"3", "5", "7"}] for i in range(1, len(str(N))+1)]))
# print(l)
print(bisect_right(l, N))
### BUGGY CODE ###

#!/usr/bin/env python3

from copy import copy


def min_max_try(n, dams):
    mt_min = [0] * n
    mt_max = copy(dams)

    for _ in range(1000):
        # max -> min
        update = False
        for i in range(n):
            tmp_min = dams[i] - mt_max[i]
            if tmp_min > mt_min[(i+1) % n]:
                mt_min[(i+1) % n] = tmp_min
                update = True
            tmp_min = dams[i] - mt_max[(i+1) % n]
            if tmp_min > mt_min[i]:
                mt_min[i] = tmp_min
                update = True
        if not update:
            return mt_min, mt_max

        # min -> max
        update = False
        for i in range(n):
            tmp_max = dams[i] - mt_min[i]
            if tmp_max < mt_max[(i+1) % n]:
                mt_max[(i+1) % n] = tmp_max
                update = True
            tmp_max = dams[i] - mt_min[(i+1) % n]
            if tmp_max < mt_max[i]:
                mt_max[i] = tmp_max
                update = True
        if not update:
            return mt_min, mt_max

    return mt_min, mt_max


def check_answer(pos, val, n, dams):
    mt = [val] * n
    for i in range(n-1):
        mt[(pos+i+1) % n] = dams[(pos+i) % n] - mt[(pos+i) % n]
    ok = mt[pos] + mt[(pos+n-1) % n] == dams[(pos+n-1) % n]
    return ok, mt


def solv(n, dams):
    # print(dams)
    mt_min, mt_max = min_max_try(n, dams)
    # print(mt_min, mt_max)

    idx = 0
    diff = mt_max[0] - mt_min[0]
    for i in range(1, n):
        if mt_max[i] - mt_min[i] < diff:
            diff = mt_max[i] - mt_min[i]
            idx = i

    for val in range(mt_min[idx], mt_max[idx]+1):
        ok, mt = check_answer(idx, val, n, dams)
        if ok:
            return ' '.join([str(m*2) for m in mt])

    return 'Error'


if __name__ == '__main__':

    n = int(input())

    dams = [int(a) for a in input().split()]

    ans = solv(n, dams)
    print(ans)


### FIXED CODE ###

#!/usr/bin/env python3


def solv(n, dams):
    m = (sum(dams[::2]) - sum(dams[1::2])) // 2
    ans = [m*2]
    for i in range(n-1):
        m = dams[i] - m
        ans.append(m*2)
    return ans


if __name__ == '__main__':

    n = int(input())
    dams = [int(a) for a in input().split()]

    ans = solv(n, dams)

    print(' '.join([str(a) for a in ans]))
### BUGGY CODE ###

def LCS(s,t):
    ret = ''
    ls,lt = len(s), len(t)
    
    # dp[i][j] : s_i, t_iでのLCS
    dp = [[0]*(lt+1) for _ in range(ls+1)]
    for i in range(ls):
        for j in range(lt):
            if s[i]==t[j]:
                dp[i+1][j+1] = dp[i][j]+1
            else:
                dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
    
    if dp[ls][lt]==0:
        return ret
    i,j = ls, lt
    while i>0 and j>0:
        if s[i-1] == t[j-1]:
            ret += s[i-1]
            i -= 1
            j -= 1
        else:
            if dp[i-1][j] > dp[i][j-1]:
                i -= 1
            else:
                j -= 1
    return ret[::-1]

n = int(input())
S = input()
ans = 0
for i in range(1, n):
    s = S[:i]
    t = S[i:]
    ans = max(ans, len(LCS(s,t)))
print(ans)

### FIXED CODE ###

n = int(input())
s = input()
dp = [[0]*5005 for _ in range(5005)]
for i in range(n)[::-1]:
    for j in range(n)[::-1]:
        if s[i]!=s[j]:
            dp[i][j] = 0
        else:
            dp[i][j] = dp[i+1][j+1] + 1
ans = 0
for i in range(n):
    for j in range(n):
        if i >= j:
            continue
        now = min(dp[i][j], j-i)
        ans = max(ans, now)
print(ans)