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

import sys
input = sys.stdin.readline
n=int(input())
E=[]
for i in range(n-1):
  u,v,w=map(int,input().split())
  E.append([u,v,w])
def BFS(edges,N):
  roots=[[] for i in range(N)]
  for a,b,c in edges:
    roots[a-1]+=[(b-1,c)]
    roots[b-1]+=[(a-1,c)]
  dist=[-1]*N
  stack=[]
  stack.append(0)
  dist[0]=0
  while stack:
    label=stack.pop(-1)
    for i,c in roots[label]:
      if dist[i]==-1:
        dist[i]=dist[label]+c
        stack+=[i]
  return dist
for i in range(n):
  print(0 if BFS(E,n)[i]%2==0 else 1)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n=int(input())
E=[]
for i in range(n-1):
  u,v,w=map(int,input().split())
  E.append([u,v,w])
def BFS(edges,N):
  roots=[[] for i in range(N)]
  for a,b,c in edges:
    roots[a-1]+=[(b-1,c)]
    roots[b-1]+=[(a-1,c)]
  dist=[-1]*N
  stack=[]
  stack.append(0)
  dist[0]=0
  while stack:
    label=stack.pop(-1)
    for i,c in roots[label]:
      if dist[i]==-1:
        dist[i]=dist[label]+c
        stack+=[i]
  return dist
D=BFS(E,n)
for i in range(n):
  print(0 if D[i]%2==0 else 1)
### BUGGY CODE ###

import re

N, Q = [int(item) for item in re.split(r"\s", input())]
S = input()

l = []
r = []
for i in range(Q):
    l_i, r_i = [int(item) for item in re.split(r"\s", input())]
    l.append(l_i)
    r.append(r_i)

# ACの場所を探す
p_list = []
for i in range(N - 1):
    if S[i:i + 2] == "AC":
        p_list.append(1)
    else:
        p_list.append(0)

for q in range(Q):
    # qに答える
    l_i = l[q] - 1
    r_i = r[q] - 1
    print(sum(p_list[l_i:r_i]))


### FIXED CODE ###

import re
import numpy as np

N, Q = [int(item) for item in re.split(r"\s", input())]
S = input()

l = [0] * Q
r = [0] * Q
for i in range(Q):
    l[i], r[i] = [int(item) for item in re.split(r"\s", input())]

# ACの場所を探す
p_list = [0] * (N + 1)
i = 0
while i < N - 1:
    if S[i:i + 2] == "AC":
        p_list[i + 1] = 1
        i += 2
    else:
        i += 1


cumsum = np.cumsum(p_list)

out_list = []
for q in range(Q):
    # qに答える
    l_i = l[q] - 1
    r_i = r[q] - 1

    if l_i >= 0:
        c_l = cumsum[l_i]
    else:
        c_l = 0
    c_r = cumsum[r_i]
    out_list.append(str(c_r - c_l))

print("\n".join(out_list))
### BUGGY CODE ###

N, M = map(int, input().split())
ans = 1
for i in range(1, M//N+1):
    if M % i == 0 and N * i <= M:
        ans = i
print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
ans = 1
x = 1
while x * x <= M:
    if M % x == 0:
        if x >= N:
            ans = max(ans, M//x)
        if M//x >= N:
            ans = max(ans, x)
    x += 1
print(ans)
### BUGGY CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
dp=[0]*n

for i in range(1,n):
    cost=float("inf")
    for j in range(max(0,i-k), i):
        cost = min(cost, dp[j] + abs(h[i]-h[j]))
    dp[i] = cost
print(dp[n-1])


### FIXED CODE ###

def main():
    n,k=map(int,input().split())
    h=list(map(int,input().split()))
    dp=[0]*n

    for i in range(1,n):
        dp[i] = min([dp[j] + abs(h[i]-h[j]) for j in range(max(0,i-k),i)])
    print(dp[n-1])

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

l,r = map(int,input().split())
number_list=[i for i in range(l,r+1)]
c=2019
for i in number_list:
  if i%2019==0:
    print(0)
    break
else:
  for j in number_list:
    for k in number_list[(number_list.index(j)+1):]:
      if c>(((j%2019)*(k%2019))%2019):
        c=(((j%2019)*(k%2019))%2019)
  print(c)
        

### FIXED CODE ###

l,r = map(int,input().split())
c=2019
for i in range(l,r+1):
  if i%2019==0:
    print(0)
    break
else:
  for j in range(l,r+1):
    for k in range(j+1,r+1):
      if c>(j*k%2019):
        c=(j*k%2019)
  print(c)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
L = []
R = []
ans = []
for _ in range(Q):
	l, r = map(int, input().split())
	L.append(l)
	R.append(r)

for i in range(Q):
	cnt = 0
	for j in range(L[i]-1, R[i]-1):
		if S[j] == 'A' and S[j+1] == 'C':
			cnt += 1
		else:
			j += 1
	ans.append(cnt)

for i in range(Q):
	print(ans[i])

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
L = []
R = []
# ans = []
for _ in range(Q):
	l, r = map(int, input().split())
	L.append(l)
	R.append(r)
sum = [0] * (N+1)
for i in range(1, N):
	if S[i-1] == 'A' and S[i] == 'C':
		sum[i+1] = sum[i] + 1
	else:
		sum[i+1] = sum[i]
# print(sum)


for i in range(Q):
	print(sum[R[i]] - sum[L[i]])
### BUGGY CODE ###

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

d = int(pow(P, 1/N))
for i in range(int(pow(P, 1/N))+1, 0, -1):
  if P % i**N == 0:
    d = i
    break
print(d)

### FIXED CODE ###

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

if N == 1:
  d = P
else:
  d = 1
  i = 2
  while i <= round(pow(P, 1/N)):
    if P % i**N == 0:
      P //= i**N
      d *= i
    else:
      i += 1
print(d)
### BUGGY CODE ###

import networkx as nx
from networkx.algorithms.flow import dinitz

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

def inside(x, y):
	if 0 <= x < n and 0 <= y < m:
		return True
	else:
		return False

DI = [1, 0, -1, 0]
DJ = [0, 1, 0, -1]

a = [list(input()) for _ in range(n)]
S, T = n*m, n*m+1
g = nx.DiGraph()
g.add_nodes_from(range(n*m+2))
for i in range(n):
	for j in range(m):
		if a[i][j] == "#":
			continue
		if (i+j)%2:
			g.add_edge(i*m+j, T, capacity=1)
		else:
			g.add_edge(S, i*m+j, capacity=1)
			for k in range(4):
				di, dj = i+DI[k], j+DJ[k]
				if inside(di, dj) and a[di][dj] == ".":
					g.add_edge(i*m+j, di*m+dj, capacity=1)
r = dinitz(g, S, T)
print(r.graph["flow_value"])
#print(*r.edges)
for e in r.edges:
	fr, to = e
	#print(fr, to)
	if fr == S or to == T or r[fr][to]["flow"] < 1:
		continue
	i0, j0 = fr//m, fr%m
	i1, j1 = to//m, to%m
	if i1 == i0+1:
		a[i0][j0] = "v"
		a[i1][j1] = "^"
	elif i1 == i0-1:
		a[i0][j0] = "^"
		a[i1][j1] = "v"
	elif j1 == j0+1:
		a[i0][j0] = ">"
		a[i1][j1] = "<"
	else:
		a[i0][j0] = "<"
		a[i1][j1] = ">"
print(*["".join(x) for x in a], sep="\n")

### FIXED CODE ###

import networkx as nx
from networkx.algorithms.bipartite import hopcroft_karp_matching

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

def inside(x, y):
	if 0 <= x < n and 0 <= y < m:
		return True
	else:
		return False

DI = [1, 0, -1, 0]
DJ = [0, 1, 0, -1]

a = [list(input()) for _ in range(n)]
g = nx.Graph()
g.add_nodes_from(range(n*m))
zero = True
top = set()
for i in range(n):
	for j in range(m):
		if a[i][j] == "#":
			continue
		if (i+j)%2 == 0:
			for k in range(4):
				di, dj = i+DI[k], j+DJ[k]
				if inside(di, dj) and a[di][dj] == ".":
					zero = False
					g.add_edge(i*m+j, di*m+dj)
					top.add(i*m+j)
if zero:
	print(0)
else:
	h = hopcroft_karp_matching(g, top_nodes=top)
	print(len(h)//2)
	for fr, to in h.items():
		i0, j0 = fr//m, fr%m
		i1, j1 = to//m, to%m
		if a[i0][j0] != ".":
			continue
		if i1 == i0+1:
			a[i0][j0] = "v"
			a[i1][j1] = "^"
		elif i1 == i0-1:
			a[i0][j0] = "^"
			a[i1][j1] = "v"
		elif j1 == j0+1:
			a[i0][j0] = ">"
			a[i1][j1] = "<"
		else:
			a[i0][j0] = "<"
			a[i1][j1] = ">"
print(*["".join(x) for x in a], sep="\n")
### BUGGY CODE ###

import operator
import numpy as np
n = int(input())
xy = np.array([list(map(int, input().split())) for _ in range(n)])

sa1 = np.argsort(xy[:,0])
sa2 = np.argsort(xy[:,1])

s1 = xy[sa1,0]
s2 = xy[sa2,1]
c1 = s1[1:] - s1[:-1]
c2 = s2[1:] - s2[:-1]

c = [(c, (sa1[i], sa1[i+1])) for i, c in enumerate(c1)] + [(c, (sa2[i], sa2[i+1])) for i, c in enumerate(c2)]
c = sorted(c, key=operator.itemgetter(0))

total_cost = 0
sg = []
for cost, verts in c:
    vf1, vf2 = None, None
    for g in sg:
        if verts[0] in g: vf1 = g
        if verts[1] in g: vf2 = g
        if vf1 and vf2:
            if vf1 == vf2: break
            total_cost += cost
            vf1.update(vf2)
            sg.remove(vf2)
            break
    else:
        total_cost += cost
        if vf1:
            vf1.add(verts[1])
        elif vf2:
            vf2.add(verts[0])
        else:
            sg.append(set(verts))
print(total_cost)

### FIXED CODE ###

import operator
import numpy as np
n = int(input())
xy = np.array([list(map(int, input().split())) for _ in range(n)])

sa1 = np.argsort(xy[:,0])
sa2 = np.argsort(xy[:,1])

s1 = xy[sa1,0]
s2 = xy[sa2,1]
c1 = s1[1:] - s1[:-1]
c2 = s2[1:] - s2[:-1]

c = [(c, (sa1[i], sa1[i+1])) for i, c in enumerate(c1)] + [(c, (sa2[i], sa2[i+1])) for i, c in enumerate(c2)]
c = sorted(c, key=operator.itemgetter(0))

total_cost = 0
sg = {}
for cost, verts in c:
    vf1 = sg.get(verts[0])
    vf2 = sg.get(verts[1])
    if vf1 and vf2:
        if vf1 is vf2: continue
        if len(vf1) < len(vf2): vf1, vf2 = vf2, vf1
        total_cost += cost
        vf1.update(vf2)
        for v in vf2: sg[v] = vf1
    else:
        total_cost += cost
        if vf1:
            vf1.add(verts[1])
            sg[verts[1]] = vf1
        elif vf2:
            vf2.add(verts[0])
            sg[verts[0]] = vf2
        else:
            sg[verts[0]] = sg[verts[1]] = set(verts)
print(total_cost)
### BUGGY CODE ###

x = int(input())

for a in range(-10**3, 10**3):
    for b in range(-10**3, 10**3):
        if a**5 - b**5 == x:
            k = [a, b]

for i in range(2):
    print(k[i], end=" ")

### FIXED CODE ###

x = int(input())

def func():
    for a in range(-10**2 - 200, 10**2 + 200):
        for b in range(-10**2 - 200, 10**2 + 200):
            if a**5 - b**5 == x:
                k = [a, b]
                return k
    

k = func()
for i in range(2):
    print(k[i], end=" ")
### BUGGY CODE ###

s = list(input())
n = int(input())

for i in range(n):
  q = input().split()
  if q.pop(0)=='1':
    s.reverse()
  else:
    if q.pop(0)=='1':
      s.insert(0,q.pop(0))
    else:
      s.append(q.pop(0))

print(''.join(s))

### FIXED CODE ###

from collections import deque

s = deque(input())
n = int(input())

point = 0
for i in range(n):
  q = input().split()
  if q.pop(0)=='1':
    point = (point+1)%2
  else:
    _q = int(q.pop(0))-1
    if (point+_q)%2 == 0:
      s.appendleft(q.pop(0))
    else:
      s.append(q.pop(0))

if point == 1:
  s.reverse()

print(''.join(s))
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
As = list(mapint())

memo = {}
s = set()

ans = 0
def dfs(idx, money, stocks):
    global ans
    if idx==N:
        ans = max(ans, money)
        return
    a = As[idx]
    if (idx, stocks) in s:
        if money<=memo[(idx, stocks)]:
            return
    s.add((idx, stocks))
    memo[(idx, stocks)] = money
    for num in range(1, stocks+1):
        dfs(idx+1, money+a*num, stocks-num)
    cnt = 0
    while money>=0:
        dfs(idx+1, money, stocks+cnt)
        cnt += 1
        money -= a

dfs(0, 1000, 0)
print(ans)

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
As = list(mapint())

memo = {}
s = set()

ans = 0
def dfs(idx, money, stocks):
    global ans
    if idx==N:
        ans = max(ans, money)
        return
    a = As[idx]
    if (idx, stocks) in s:
        if money<=memo[(idx, stocks)]:
            return
    s.add((idx, stocks))
    memo[(idx, stocks)] = money
    dfs(idx+1, money+stocks*a, 0)
    dfs(idx+1, money, stocks)
    cnt = money//a
    dfs(idx+1, money-cnt*a, stocks+cnt)

dfs(0, 1000, 0)
print(ans)
### BUGGY CODE ###

N = int(input())
S = list(input())
ans = 0
snumber = [str(i) for i in range(10)]
for i in snumber:
    for j in snumber:
        for k in snumber:
            n = 0
            while i != S[n] and n < N-3:
                n += 1
            if S[n] != i:
                break
            n += 1
            while j != S[n] and n < N-2:
                n += 1
            if S[n] != j:
                break
            n += 1
            while k != S[n] and n < N-1:
                n += 1
            if S[n] == k:
                ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
S = list(input())
ans = 0
snumber = [str(i) for i in range(10)]
for i in snumber:
    for j in snumber:
        for k in snumber:
            n = 0
            code = []
            while i != S[n] and n < N-3:
                n += 1
            if S[n] != i:
                break
            n += 1
            while j != S[n] and n < N-2:
                n += 1
            if S[n] != j:
                break
            n += 1
            while k != S[n] and n < N-1:
                n += 1
            if S[n] == k:
                ans += 1
print(ans)
### BUGGY CODE ###

def main():
    import fractions
    import sys
    input = sys.stdin.readline
    N = int(input())
    a = list(map(int,input().split()))
    MOD = 10**9+7
    g1 = 1
    for t in a[:N//2]:
        g1 = divmod(g1*t,fractions.gcd(g1,t))[0]

    g2 = 1
    for t in a[N//2:]:
        g2 = divmod(g2*t,fractions.gcd(g2,t))[0]
    res = 0
    g = fractions.gcd(g1,g2)

    r1 = (g2//g)%MOD
    for t in a[:N//2]:
        res += divmod(g1,t)[0]
    res = res*r1%MOD

    res2 = 0
    r2 = (g1//g)%MOD
    for t in a[N//2:]:
        res2 += divmod(g2,t)[0]
    res2 = res2*r2%MOD
    print((res+res2)%MOD)
if __name__ == '__main__':
    main()


### FIXED CODE ###

import fractions
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int,input().split()))
g = 1
res = 0
MOD = 10**9+7
for elem in a:
    tmp = g*elem//fractions.gcd(g,elem)
    res *= tmp//g
    g = tmp
    res += g//elem
print(res%MOD)
### BUGGY CODE ###

N = int(input())
a,b = map(int,input().split())
for i in range(N-1):
    aa,bb = map(int,input().split())
    taa,tbb = aa,bb
    while True:
        if aa >= a and bb >=b:
            break
        aa += taa
        bb += tbb
    a,b = aa,bb
print(a+b)


### FIXED CODE ###

N = int(input())
a,b = 1,1
for i in range(N):
    aa,bb = map(int,input().split())
    k = max((a+aa-1)//aa,(b+bb-1)//bb)
    aa *= k
    bb *= k
    a,b = aa,bb

print(a+b)
### BUGGY CODE ###

from fractions import gcd
k=int(input())
sum=0
for l in range(1,k+1):
    for m in range(1,k+1):
        for n in range(1,k+1):
            sum += gcd(gcd(l,m),n)

print(sum)

### FIXED CODE ###

from fractions import gcd
k=int(input())
l=[]
dp=[[0]*(k+1) for i in range(k+1)]

for i in range(1,k+1):
    for j in range(1,k+1):
        dp[i][j]=gcd(i,j)
        l.append(gcd(i,j))
sum=0
for x in range(1,k+1):
    for y in range(len(l)):
        sum += int(dp[l[y]][x])
print(sum)
### BUGGY CODE ###

n,k=map(int,input().split())
p=[int(i) for i in input().split()]


Msum=0
for i in range(n-k+1):
    tmp=sum(p[i:i+k])
    Msum = max(tmp,Msum)

print((Msum+k)/2)

### FIXED CODE ###

n,k=map(int,input().split())
p=[int(i) for i in input().split()]


tmp=sum(p[0:k])
Msum=tmp

for i in range(1,n-k+1):
    a=p[i-1]
    b=p[i+k-1]
    tmp=tmp-a+b
    Msum = max(tmp,Msum)

print((Msum+k)/2)
### BUGGY CODE ###

N,K=map(int,input().split())
List = list(map(int, input().split()))
 
def imosu(x,k):
  data = [0]*k
  for i in range(k):
    first = i-x[i]
    last = i+x[i]
    if first < 0:
      first = 0
    data[first] += 1
    if last+1 < k:
      data[last+1] +=-1
  ruiseki = [0]*k
  ruiseki[0] = data[0]
  for i in range(k-1):
    ruiseki[i+1] = ruiseki[i] + data[i+1]
  return ruiseki
 
for i in range(K):
  List = imosu(List,N)
  if List.count(N) == N:
    break
print(*List)

### FIXED CODE ###

N,K=map(int,input().split())
List = list(map(int, input().split()))
 
def imosu(x,k):
  data = [0]*k
  for i in range(k):
    first = i-x[i]
    last = i+x[i]
    if first < 0:
      first = 0
    data[first] += 1
    if last+1 < k:
      data[last+1] +=-1
  ruiseki = [0]*k
  ruiseki[0] = data[0]
  for i in range(k-1):
    ruiseki[i+1] = ruiseki[i] + data[i+1]
  return ruiseki
 
for i in range(K):
  List = imosu(List,N)
  if List.count(N) == N:
    break
print(*List)
### BUGGY CODE ###

#
import sys
import math
import numpy as np
import itertools

n = int(input())
a=1
ll = [int(i) for i in input().split()] 

for i in range(n):
    a *= ll[i]
if a > 10**18:
    print(-1)
else:
    print(a)




### FIXED CODE ###

#
import sys
import math
import numpy as np
import itertools

n = int(input())
a=1
ll = [int(i) for i in input().split()] 
ll.sort()

for i in range(n):
    a *= ll[i]
    if a == 0:
        print(0)
        exit()
    if a > 10**18:
        print(-1)
        exit()
else:
    print(a)
### BUGGY CODE ###

from collections import Counter
N = int(input())

C = []
sum_ana = 0
for _ in range(N):
  s = list(input())
  c = Counter(s)
  sum_ana += C.count(c)
  C.append(c)
  
print(sum_ana)



### FIXED CODE ###

from collections import Counter
N = int(input())

S = []
sum_ana = 0
for _ in range(N):
  s = sorted(input())
  S.append("".join(s))

S.sort()
ana = 0
for i in range(N-1):
  if S[i] == S[i+1]:
    ana+= 1
    continue
  sum_ana += (ana*(ana+1))//2
  ana = 0
sum_ana += (ana*(ana+1))//2
print(sum_ana)
### BUGGY CODE ###

N,M = map(int,input().split())
A = [int(i) for i in input().split()]
A.sort()
BC = [[0]*2 for i in range(M)]

for m in range(M):
    BC[m][0],BC[m][1] = map(int,input().split())

BC.sort(reverse=True,key=lambda x:x[1])


for m in range(M):
    B,C = BC[m][0],BC[m][1]
    for i in range(B):
        if A[i] > C:
            break
        A[i] = C
    A.sort()
 
print(sum(A))

### FIXED CODE ###

N,M = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
BC = [list(map(int, input().split())) for _ in range(M)]
BC.sort(key=lambda x:x[1], reverse=True)
 
ans = 0
b,c = BC.pop(0)
for i,a in enumerate(A):
    if b>=1:
        if c > a:
            ans += c
            b -= 1
        else:
            ans += a
    if b<=0:
        if len(BC)==0:
            ans += sum(A[i+1:])
            break
        else:
            b,c = BC.pop(0)
 
print(ans)
### BUGGY CODE ###

n,q = (int(i) for i in input().split())
s = input()
td = [[i for i in input().split()] for i in range(q)]

dic = {"A":[],"B":[],"C":[],"D":[],"E":[],"F":[],"G":[],"H":[],"I":[],"J":[],"K":[],"L":[],"M":[],"N":[],"O":[],"P":[],"Q":[],"R":[],"S":[],"T":[],"U":[],"V":[],"W":[],"X":[],"Y":[],"Z":[]}

for i,x in enumerate(s):
    dic[x].append(i)

glm = [1]*n

for t,d in td:
    if d =="L":
        for i in sorted(dic[t]):
            if i != 0:
                glm[i-1] += glm[i]
            glm[i] = 0
    else:
        for i in sorted(dic[t],reverse=True):
            if i != n-1:
                glm[i+1] += glm[i]
            glm[i] = 0

print(sum(glm))

### FIXED CODE ###

import sys
input = sys.stdin.readline
n,q = (int(i) for i in input().split())
s = input()
td = [[i for i in input().split()] for i in range(q)][::-1]

now = s[0]
pre = ""
idx = 0
for t,d in td:
    if t==now and d=="L":
        idx += 1
        now = s[idx]
        pre = s[idx-1]
    elif t==pre and d=="R" and idx != 0:
        idx -= 1
        now = s[idx]
        pre = s[max(0,idx-1)]
        
res = n-idx
now = s[n-1]
pre = ""
idx = n-1
for t,d in td:
    if t==now and d=="R":
        idx -= 1
        now = s[idx]
        pre = s[idx+1]
    elif t==pre and d=="L" and idx != n-1:
        idx += 1
        now = s[idx]
        pre = s[min(n-1,idx+1)]

print(max(0,res-(n-1-idx)))
### BUGGY CODE ###

N,M=map(int,input().split())
*A,=map(int,input().split())
BC=[list(map(int,input().split()))[::-1]for _ in range(M)]

L=[0]
for c,b in BC:
    L+=[c]*b

ans=sorted(A+L)[::-1]
print(sum(ans[:N]))

### FIXED CODE ###

N,M=map(int,input().split())
*A,=map(int,input().split())
BC=[list(map(int,input().split()))[::-1]for _ in range(M)]
BC=sorted(BC)[::-1]

L=[0]
for c,b in BC:
    L+=[c]*b
    if len(L)-1>N:
        break

ans=sorted(A+L)[::-1]
print(sum(ans[:N]))
### BUGGY CODE ###

N=int(input())
a=list(map(int,input().split()))
for i in range(0,sum(a)+1,2):
    s=[i/2]
    answer=[]        
    for n in range(N):
        s.append(a[n]-s[n])
        answer.append(int(2*s[n]))
    if s[N-1]+i/2==a[N-1]:
        print(*answer)
        exit(0)

### FIXED CODE ###

N=int(input())
a=list(map(int,input().split()))
x_1=sum(a)
for i in range(1,N,2):
    x_1-=2*(a[i])
x=[x_1]
for j in range(1,N):
    x.append(2*a[j-1]-x[j-1])
print(*x)
### BUGGY CODE ###

import sys

def max_heapify(A, i):
  H = len(A) - 1
  l, r, m = i*2, i*2+1, i
  if l <= H and A[l] > A[i]: m = l
  if r <= H and A[r] > A[m]: m = r

  if m != i:
    A[i], A[m] = A[m], A[i]
    max_heapify(A, m)

def build_max_heap(A):
  H = len(A) - 1
  for i in range(H // 2, 0, -1):
    max_heapify(A, i)

A = [0]

for line in sys.stdin.readlines():
  if line[0] == 'i':
    A.append(int(line[7:]))
    build_max_heap(A)
  elif line[1] == 'x':
    if len(A) <= 2:
      print(A.pop())
    else:
      print(A[1])
      A[1] = A.pop()
      max_heapify(A, 1)
  else:
    exit()

### FIXED CODE ###

import sys

def max_heapify(A, H, i):
  target = A[i]

  m = i
  l = i * 2
  while l <= H:
    largest = target
    if A[l] > target:
      m = l
      largest = A[m]

    r = l + 1
    if r <= H and A[r] > largest:
      m = r
      largest = A[m]

    if m != i:
      A[i] = largest
      i = m
      l = i * 2
    else:
      break

  A[m] = target

def build_max_heap(A, i):
  if i < 2: return
  last = A[i]
  p = i // 2
  while p > 0 and A[p] < last:
    A[i] = A[p]
    i = p
    p = i // 2
  A[i] = last

A = [0]

for line in sys.stdin.readlines():
  if line[0] == 'i':
    A.append(int(line[7:]))
    build_max_heap(A, len(A) - 1)
  elif line[1] == 'x':
    if len(A) <= 1:
      pass
    elif len(A) <= 2:
      print(A.pop())
    else:
      print(A[1])
      A[1] = A.pop()
      max_heapify(A, len(A) -1, 1)
  else:
    exit()
### BUGGY CODE ###

N, K = map(int, input().split())
H = [int(input()) for _ in range(N)]
H = sorted(H)
cand = [H[i:i+K][-1] - H[i:i+K][0] for i in range(N - K + 1)]
print(min(cand))

### FIXED CODE ###

N, K = map(int, input().split())
H = [int(input()) for _ in range(N)]
H = sorted(H)
ans = 10**10
for i in range(N - K + 1):
    ans = min(ans, H[i+K-1] - H[i])
print(ans)
### BUGGY CODE ###

N,W = list(map(int, input().split()))
m = []
v = []
for i in range(N):
    a,b = map(int, input().split())
    m.append(a)
    v.append(b)
sum_v = sum(v)
dp = [[float('inf') for i in range(sum_v+1)]for j in range(N+1)]
for i in range(N):
    for j in range(sum(v)+1):
        if j == 0:
            dp[i][j] = 0
        if j != float('inf') and sum_v >= j+v[i]:
            dp[i+1][j+v[i]] = min(dp[i][j+v[i]],dp[i][j] + m[i])
            dp[i+1][j] = min(dp[i+1][j],dp[i][j])

for i in range(sum(v)+1):
    if  dp[-1][sum(v)-i] <= W:
        print(sum(v)-i)
        break

### FIXED CODE ###

N,W = list(map(int, input().split()))
m = []
v = []
for i in range(N):
    a,b = map(int, input().split())
    m.append(a)
    v.append(b)

sum_v = sum(v)
dp = [[10**15 for i in range(sum_v+1001)]for j in range(N+1)]
for i in range(N):
    dp[i][0] = 0
    for j in range(sum_v+1):
        if j != 10**15:
            dp[i+1][j+v[i]] = min(dp[i][j+v[i]],dp[i][j] + m[i])
            dp[i+1][j] = min(dp[i+1][j],dp[i][j])

for i in range(sum(v)+1):
    if  dp[-1][sum(v)-i] <= W:
        print(sum(v)-i)
        break
### BUGGY CODE ###

import itertools,copy
T = list(input())
N = [i for i, x in enumerate(T) if x == '?']
B = list(itertools.product(['P','D'], repeat=len(N)))
point = [0]*len(B)
strs = ['']*len(B)
for b,i in zip(B,range(len(B))):
    TC = copy.deepcopy(T)
    for n,j in zip(N,range(len(N))):
        TC[n] = b[j]
    TC = ''.join(TC)
    strs[i] = TC
    point[i] = TC.count('PD') + TC.count('D')
maxin = max(point)

print(strs[point.index(maxin)])


### FIXED CODE ###

#BBBBBBBBBBB

import sys
import math
import itertools
import collections
import heapq
import numpy as np

rl = sys.stdin.readline

t = rl()
li = []
for i in range(len(t)):
    if t[i] == '?':
        li.append('D')
    else:
        li.append(t[i])
print(''.join(li))
### BUGGY CODE ###

from collections import Counter

S = input()
N = len(S)

l = [0]*(N+1)
for i in range(N-1, -1, -1):
    l[i] = (l[i+1] + 10**(N-i) * int(S[i])) % 2019

r = sum(m*(m-1)//2 for m in Counter(l).values())
print(r)

### FIXED CODE ###

from collections import Counter

S = input()
# S = "12345"*40000
N = len(S)

l = [0]*(N+1)
for i in range(N-1, -1, -1):
    l[i] = (l[i+1] + pow(10, N-i, 2019) * int(S[i])) % 2019
    # if i%10000 == 0:
    #     print(i)

# print(list(Counter(l).values()))

r = sum(m*(m-1)//2 for m in Counter(l).values())
print(r)