Harryxun/stf_run huggingface dataset:
import sys
sys.setrecursionlimit(2000)


class UnionFind():
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        if self.par[x] != x:
            self.par[x] = self.find(self.par[x]) # contraction
        return self.par[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if not self.same(x, y):
            self.size[y] += self.size[x]
        self.par[x] = y

    def same(self, x, y):
        return self.find(x) == self.find(y)


n, m = map(int, input().split())
edge = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(m)]

uf = UnionFind(n)
ans = n * (n-1) // 2
anss = []
for i in reversed(range(m)):
    anss.append(ans)
    # print(uf.par)
    # print(uf.size, [uf.size[uf.find(i)] for i in range(n)])
    a, b = edge[i]
    if not uf.same(a, b):
        ans -= uf.size[uf.find(a)] * uf.size[uf.find(b)]
    # print(i, a, b)

    uf.unite(a, b)

for i in reversed(range(m)):
    print(anss[i])


### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)


class UnionFind():
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        if self.par[x] != x:
            self.par[x] = self.find(self.par[x]) # contraction
        return self.par[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if not self.same(x, y):
            self.size[y] += self.size[x]
        self.par[x] = y

    def same(self, x, y):
        return self.find(x) == self.find(y)


n, m = map(int, input().split())
edge = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(m)]

uf = UnionFind(n)
ans = n * (n-1) // 2
anss = []
for i in reversed(range(m)):
    anss.append(ans)
    # print(uf.par)
    # print(uf.size, [uf.size[uf.find(i)] for i in range(n)])
    a, b = edge[i]
    if not uf.same(a, b):
        ans -= uf.size[uf.find(a)] * uf.size[uf.find(b)]
    # print(i, a, b)

    uf.unite(a, b)

for i in reversed(range(m)):
    print(anss[i])
S,T = map(input().split())

if S == T[:len(S)]:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

S = input()
T = input()

if S == T[:len(S)]:
  print('Yes')
else:
  print('No')
N,M = map(int,input().split())
S = []
for _ in range(M):
  S.append(int(input()))
S.append(-1)
S.append(N+1)
S.sort()  
P = 1

def Fib(n):    
    if n == 1:
        return 0
    elif n == 2:
        return 1
    else:
        return Fib(n-1)+Fib(n-2)
      
for i in range(M+1):
  P *= Fib(S[i+1]-S[i]) 

print(P%1000000007)

### FIXED CODE ###

def Fib(n):
    a, b = 0, 1
    if n == 1:
        return a
    elif n == 2:
        return b
    else:
        for i in range(n-2):
            a, b = b, a + b
        return b

N,M = map(int,input().split())
if M == 0:
  P = Fib(N+2)
  print(P%1000000007)
else:
  S = []
  for _ in range(M):
    S.append(int(input()))
  S.append(-1)
  S.append(N+1)
  S.sort()  
  P = 1

  for i in range(M+1):
    P *= Fib(S[i+1]-S[i]) 

  print(P%1000000007)
n,m = map(int,input().split())
ls = [[int(x) for x in input().split()] for _ in range(m)]

ans = sorted(ls,key=lambda x:(x[0],x[1]))

dic = [[] for _ in range(m+1)]

for i in range(m):
    key = ans[i][0]
    value = ans[i][1]
    dic[key+1].append(value)

for i in range(m):
    print("{:06d}{:06d}".format(ls[i][0],dic[ls[i][0]+1].index(ls[i][1])+1))

### FIXED CODE ###

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

for i in range(m):
    a,b = map(int,input().split())
    ls[a].append((b,i))
ans = [None]*m
for i,l in enumerate(ls):
    l.sort()
    for j,(a,b) in enumerate(l):
        ans[b]= "{:06d}{:06d}".format(i,j+1)
for i in range(m):
    print(ans[i])
N = int(input())
A = list(map(int, input().split()))
ans = 0
plus_lis = [A[i] + i for i in range(N)]
minus_lis = [k - A[k] for k in range(N)]
plus_lis.sort()
minus_lis.sort()

ans_lis = [0] * 10 ** 6
for x in plus_lis:
    if x < 10 ** 6:
        ans_lis[x-1] += 1
for y in minus_lis:
    if y > 0:
        ans += ans_lis[x-1]
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 0
plus_lis = [A[i] + i for i in range(N)]
minus_lis = [k - A[k] for k in range(N)]

ans_lis = [0] * 10 ** 6
for x in plus_lis:
    if x < 10 ** 6:
        ans_lis[x-1] += 1
for y in minus_lis:
    if y > 0:
        ans += ans_lis[y-1]
print(ans)
X = int(input())

e = [0 for _ in range(X+1)]
e[1] = 1
for i in range(2, X):
    v = i*i
    while v <= X:
        e[v] = 1
        v *= b
        
for i in range(X, 0, -1):
    if e[i] == 1:
        print(i)
        break

### FIXED CODE ###

X = int(input())

e = [0 for _ in range(X+1)]
e[1] = 1
for i in range(2, X):
    v = i*i
    while v <= X:
        e[v] = 1
        v *= i
        
for i in range(X, 0, -1):
    if e[i] == 1:
        print(i)
        break
import heapq
 
 
 
n, m = map(int, input().split())
t_r_list = []
for i in range(n):
    t_r_list.append(list(map(int, input().split())))


t_r_list.sort()
que = []
total = 0
l = 0
for j in range(1, m+1):
    while t_r_list[l][0] == j:
        heapq.heappush(que, -t_r_list[l][1])
        l += 1
        if l >= n:
            break
        
 
    if que:
        total -= heapq.heappop(que)
      
      
print(total)

### FIXED CODE ###

import heapq

n, m = map(int, input().split())
t_r_list = []
for i in range(n):
    t_r_list.append(list(map(int, input().split())))

t_r_list.sort()
que = []
total = 0
l = 0
for j in range(1, m + 1):
    while True:
        if l == n:
            break
        if t_r_list[l][0] != j:
            break
        heapq.heappush(que, -t_r_list[l][1])
        l += 1

    if que:
        total -= heapq.heappop(que)


print(total)
K = int(input())
a,b = list(map(int, input().split()))

for i in range(a,b+1)
    if i %  K == 0:
        print('OK')
        exit()
print('NG')

### FIXED CODE ###

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

for i in range(a,b+1):
    if i %  K == 0:
        print('OK')
        exit()
print('NG')
import collections
N=int(input())
s=[input() for i in range(N)]
M=int(input())
t=[input() for i in range(M)]

table=collections.defaultdict(int)
for x in s:
  table[x]+=1
for x in t:
  table[t]+=1
table=table.values()
table=[x for x in table if x >= 0]
print(sum(table))

### FIXED CODE ###

import collections
N=int(input())
s=[input() for i in range(N)]
M=int(input())
t=[input() for i in range(M)]

table=collections.defaultdict(int)
for x in s:
  table[x]+=1
for x in t:
  table[x]-=1
table=table.values()
table=[x for x in table if x >= 0]
table.append(0)
print(max(table))
N=int(input())
X=[int(i) for i in input().split()]
for i in range(N):
  x=X.copy()
  del x[i]
  x.sort()
  print(x[N//2-1])

### FIXED CODE ###

A, B, X=map(int,input().split())
if A<=X<=(A+B):
  print("YES")
else:
  print("NO")
Ans = "A"
while True:
    try:
        if Ans in Pos:
            Ans = Pos[((Pos.index(Ans)) + 1) % 2]
    except:
         print(Ans)
            break

### FIXED CODE ###

Ans = "A"
while True:
    try:
        Pos = list(map(str,input().split(",")))
        if Pos == ['']:
            print(Ans)
            break
        if Ans in Pos:
            Ans = Pos[((Pos.index(Ans)) + 1) % 2]
    except:
        print(Ans)
        break
import itertools
N,M,X = map(int,input().split())
A = [0,0,0,0]
C = []
Z = []
cz = []
for i in range(N) :
    C.append(list(map(int,input().split())))

for i in range(2,N+1) :
    c = list(itertools.combinations(C,i))
    for j in range(len(c)) :
        A = [0,0,0,0]
        cj = c[j]
        for k in range(i) :
            ck = cj[k]
            A[0]+= ck[0]
            A[1] += ck[1]
            A[2] += ck[2]
            A[3] += ck[3]
        Z.append(A)

for i in range(len(Z)) :
    zi = Z[i]
    if zi[1]>=X and zi[2]>=X and zi[3]>=X :
        cz.append(zi[0])        

if len(cz) == 0 :
    print(-1)
else :
    print(min(cz))

### FIXED CODE ###

import numpy
N,M,X = map(int,input().split())
A = numpy.array([[int(i) for i in input().split()] for _ in range(N)])
ans = 10**8
for i in range(2**N) :
    i = format(i,'b').zfill(N)
    check = numpy.array([0]*(M+1))
    for j in range(N) :
        if i[j] == '0' :
            continue
        check +=  A[j][0:]
    if all (check[m] >= X for m in range(1,M+1)) :
        ans = min(ans,check[0])

if ans == 10**8 :
    print(-1)
else :
    print(ans)
import heapq
 
itemCount, ticketCount = map(int, input().split(' '))
prices = map(int, input().split(' '))
 
h = []
for price in prices:
    heapq._heappush_max(h, price)
 
for i in range(ticketCount):
    price = _heappop_max(h)
    heapq._heappush_max(h, price // 2)
total = 0
for price in h:
    total += price
 
print(total)

### FIXED CODE ###

import heapq


def _heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap) - 1)


def _heappop_max(heap):
    """Maxheap version of a heappop."""
    lastelt = heap.pop()    # raises appropriate IndexError if heap is empty
    if heap:
        returnitem = heap[0]
        heap[0] = lastelt
        heapq._siftup_max(heap, 0)
        return returnitem
    return lastelt


itemCount, ticketCount = map(int, input().split(' '))
prices = map(int, input().split(' '))

h = []
for price in prices:
    _heappush_max(h, price)

for i in range(ticketCount):
    price = _heappop_max(h)
    _heappush_max(h, price // 2)
total = 0
for price in h:
    total += price

print(total)
a, b, c, d = map(int, input().split())

while a>0 and c>0:
  a -= d
  c -= b
  

if a>o:
  print("Yes")
  
else:
  print("No")
  
  

### FIXED CODE ###

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

while a>0 and c>0:
  c -= b
  a -= d
  
  
if c<=0:
  print("Yes")
  
else:
  print("No")
print(180*(int(input())−2))

### FIXED CODE ###

print(180*(int(input())-2))
from collections import Counter
N = int(input())
A = list(map(int,input().split()))
count = Counter(A)
L = []
for v in count.values():
    if v > 1:
        L.append(v-1)
L.sort(reverse = True)
M = len(L)
cnt = L[0]
for i in range(1, M):
    if abs(cnt + L[i]) - abs(cnt - L[i]) < 0:
        cnt += L[i]
    else:
        cnt -= L[i]

ans = len(count) - cnt
print(ans)

### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int,input().split()))
count = Counter(A)
ans = len(count)
if ans % 2 == 0:
    ans -= 1
print(ans)
from collections import deque

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

b = deque()

for i in range(n):
    if (i+1) %2 == n % 2:
        b.insert(0, a[i])
    else:
        b.append(a[i])
print(*b)

### FIXED CODE ###

from collections import deque

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

b = deque()

for i in range(n):
    if (i+1) %2 == n % 2:
        b.appendleft(a[i])
    else:
        b.append(a[i])
ans = list(b)
print(*ans)
a,b = map(int,input().split()))
print('%d %d %.5f\n'%(a//b,a%b,a/b))

### FIXED CODE ###

a,b = map(int,input().split())
print("%d %d %.5f\n" % (a//b,a%b,a/b))
n=list(input())
for i in range(3):
  if n[i]==1:
    n[i]=9
  else:
    n[i]=1
s=""
for i in range(3):
  s+=n[i]
print(s)

### FIXED CODE ###

n=input()
ans=""
for i in range(3):
  if n[i]=="1":
    ans+="9"
  else:
    ans+="1"
print(ans)
print(A*B)

### FIXED CODE ###

a,b=(int(x) for x in input().split())
print(a*b)
import numpy as np

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

f=np.full((n, n), 1,dtype=int)
f=f-np.eye(n,dtype=int)


for i in range(m):
    a,b = map(int, input().split())
    f[a-1][b-1]=0
    f[b-1][a-1]=0
    
for i in range(k):
    c,d = map(int, input().split())
    f[c-1][d-1]=0
    f[d-1][c-1]=0
    
print(*f.sum(axis=0))

### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n,m,k=map(int,input().split())
uf = UnionFind(n)
friend=[0]*n
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    friend[a]+=1
    friend[b]+=1
    uf.union(a,b)

block=[0]*n
for i in range(k):
    c,d=map(int,input().split())
    c-=1
    d-=1
    if uf.same(c,d):
        block[c]+=1
        block[d]+=1

ans=[0]*n
for i in range(n):
    ans[i]=uf.size(i)-friend[i]-block[i]-1

print(*ans)
import functools
n = int(input())
t = [int(input()) for _ in range(n)]

def lcm(x, y):
    return (x * y) // functools.gcd(x, y)
    
ans = functools.reduce(lcm, t)
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline().rstrip
n = input()
print('Yes' if n == n[::-1] else 'No')
N=int(input())
import fractions 
print(2*N//fractions.gcd(2,N))

### FIXED CODE ###

L=[int(i) for i in input().split()]
A=abs(L[0]-L[1])
B=abs(L[1]-L[2])
C=abs(L[2]-L[0])
S=[A+B,A+C,B+C]
print(min(S))
a = int(input())
b
c
d
e

### FIXED CODE ###

a=int(input())
b=int(input())
c=int(input())
d=int(input())
e=int(input())
k=int(input())
if e-d<=k and e-c<=k and e-b<=k and e-a<=k and d-c<=k and d-b<=k and d-a<=k and c-b<=k and c-a<=k and b-a<=k:
  print('Yay!')
else:
  print(':(')
X, A = map(int, input().split)

if X < A:
  print(0)
else:
  print(10)

### FIXED CODE ###

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

if X < A:
  print(0)
else:
  print(10)
a, b = map(int,input().split())
if (a*b)%2 == 0:
  print("Odd")
 else:
  print("Even")

### FIXED CODE ###

a, b = map(int,input().split())
if (a*b)%2 == 0:
    print("Even")
else:
    print("Odd")
import fractions
A,B=map(int,input().split())
gcd=fractions.gcd(A, B)
ans=1
setgcd=gcd
for i in range(2,setgcd+1):
  if gcd%i==0:
    ans=ans+1
    while gcd%i==0:
      gcd=round(gcd/i)
  if i*i>setgcd:
    break
print(ans)


### FIXED CODE ###

N=int(input())
if N%2==0:
  print(0.5)
else:
  print((N+1)/(2*N))
a,b,k=map(int,input().split())
li =list(range(a,b+1))
li2=[]
for l in li[:k]:
  li2.append(l)
for l in li[-k:]:
  li2.append(l)
for ll in li2:
  print(set(li2))

### FIXED CODE ###

A,B,K=map(int,input().split())
li=[]  
for i in range(A,A+K):
  li.append(i)
for j in range(B-K+1,B+1):
  li.append(j)
ans=sorted(set(li))
for l in ans:
  if A<=l<=B:
    print(l)
S = str(input())
if(S[3]==S[4] and S[5]==S[6])
	print('Yes')
else
	print('No')
	

### FIXED CODE ###

S = str(input())
print('Yes' if S[2]==S[3] and S[4]==S[5] else 'No')
def gcd(a,b):
    if b==0:
        return a
    return gcd(b, a%b)

def lcm(a,b,g):
    return (a*b)/g

N = input()
Ti = []

for i in range(int(N)):
    tmp = input()
    Ti.append(int(tmp))
Ti.sort()

ans_gcd = gcd(Ti[0],Ti[1])
ans_lcm = lcm(Ti[0],Ti[1],ans_gcd)
for i in range(2,len(Ti)):
    ans_gcd = gcd(ans_gcd,Ti[i])
    ans_lcm = lcm(ans_lcm,Ti[i],ans_gcd)

print(int(ans_lcm))

### FIXED CODE ###

def gcd(a,b):
    m = max(a,b)
    n = min(a,b)
    if n==0:
        return m
    return gcd(n, m%n)

def lcm(a,b):
    return (a*b)//gcd(a,b)

N = input()
Ti = []

for i in range(int(N)):
    tmp = input()
    Ti.append(int(tmp))

ans_lcm = 1
for i in range(len(Ti)):
    ans_lcm = lcm(ans_lcm,Ti[i])
print(ans_lcm)
from heapq import heappush, heappop
N, *L = map(int, open('0').read().split())
dic = [[] for i in range(N)]
ans = [-1]*N
cnt = [0]*N
hq = []
for a,b in zip(*[iter(L[:2*(N-1)])]*2):
  a -= 1
  b -= 1
  dic[a] += [b]
  dic[b] += [a]
  cnt[a] += 1
  cnt[b] += 1
C = L[2*(N-1):]
C.sort()
for i in range(N):
  heappush(hq,(cnt[i],i))
arg = 0
m = sum(C)-C[-1]
while True:
  c, i = heappop(hq)
  if ans[i]!=-1:
    continue
  ans[i] = C[arg]
  arg += 1
  if arg==N:
    break
  for v in dic[i]:
    cnt[v] -= 1
    heappush(hq,(cnt[v],v))
print(m)
print(*ans)

### FIXED CODE ###

from heapq import heappush, heappop
N, *L = map(int, open(0).read().split())
dic = [[] for i in range(N)]
ans = [-1]*N
cnt = [0]*N
hq = []
for a,b in zip(*[iter(L[:2*(N-1)])]*2):
  a -= 1
  b -= 1
  dic[a] += [b]
  dic[b] += [a]
  cnt[a] += 1
  cnt[b] += 1
C = L[2*(N-1):]
C.sort()
for i in range(N):
  heappush(hq,(cnt[i],i))
arg = 0
m = 0
while True:
  c, i = heappop(hq)
  if ans[i]!=-1:
    continue
  m += C[arg]*cnt[i]
  ans[i] = C[arg]
  arg += 1
  if arg==N:
    break
  for v in dic[i]:
    cnt[v] -= 1
    heappush(hq,(cnt[v],v))
print(m)
print(*ans)
from sys import stdin
import math
import fractions
from collections import deque

WHITE = 0
BLACK = 1

N = int(stdin.readline().rstrip())
data = [list(map(int, stdin.readline().rstrip().split())) for _ in range(N-1)]

# 根から頂点までの距離
# 根は適当な頂点を選べば良いので、u_0とする
dist = [None] * (N+1)
dist[data[0][0]] = 0

# 根からの距離を算出
for u, v, w in data:
    # 木構造なので、どちらか一方はすでに求まっているはず
    if dist[u] != None:
        dist[v] = dist[u] + w
    else:
        dist[u] = dist[v] + w

# distが偶数の頂点には白で、奇数の頂点には黒で塗ることとする
for i in range(1, N+1):
    if dist[i] % 2 == 0:
        print(WHITE)
    else:
        print(BLACK)


### FIXED CODE ###

from sys import stdin
import math
import fractions
from collections import deque

WHITE = 0
BLACK = 1

N = int(stdin.readline().rstrip())
data = [list(map(int, stdin.readline().rstrip().split())) for _ in range(N-1)]

# 木の繋がりと長さ
connect = [[] for _ in range(N+1)]
for u, v, w in data:
    connect[u].append([v,w])
    connect[v].append([u,w])

# 根から頂点までの距離
# 根は適当な頂点を選べば良いので、u_0とする
dist = [None] * (N+1)
dist[data[0][0]] = 0

que = deque([])
que.append(data[0][0])
is_visited = [False] * (N+1)

# BFSで根からの距離を求めていく
while len(que) != 0:
    u = que.popleft()

    if is_visited[u] == True:
        continue

    is_visited[u] = True

    for v, w in connect[u]:
        que.append(v)
        if dist[v] == None:
            dist[v] = dist[u] + w

# distが偶数の頂点には白で、奇数の頂点には黒で塗ることとする
for i in range(1, N+1):
    if dist[i] % 2 == 0:
        print(WHITE)
    else:
        print(BLACK)
if S[0] != S[1] and S[0] != S[2]:
    print("Yes")
elif S[0] != S[1] and S[1] != S[2]:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

S = input()
if S == "AAA" or S == "BBB":
    print("No")
else:
    print("Yes")
S=input()

p=True
q=True
for i in S:
  if p:
    if not i=='L':
      p=False
	else:
      q=False
      break
  else:
    if not i=='R':
      p=True
    else:
      q=False
      break
      
print ("Yes" if q else "No")

### FIXED CODE ###

S=input()

p=True
q=True
for i in S:
  if p:
    if not i=='L':
      p=False
    else:
      q=False
      break
  else:
    if not i=='R':
      p=True
    else:
      q=False
      break

print ("Yes" if q else "No")
def divisor(n):
  ass=[]
  for i in range(1,int(n**0.5)+1):
    if n%i==0:
      ass.append(i)
      if i!=n//i:ass.append(n//i)
  return ass
n,m=map(int,input().split())
d=divisor(m)
d.sort(reverse=1)
for i in d:
  if m//i>=n:print(i):exit()

### FIXED CODE ###

def divisor(n):
  ass=[]
  for i in range(1,int(n**0.5)+1):
    if n%i==0:
      ass.append(i)
      if i!=n//i:ass.append(n//i)
  return ass
n,m=map(int,input().split())
d=sorted(divisor(m))
for i in d[::-1]:
  if m//i>=n:print(i);break
#coding:utf-8
d=[int(i) for i in input().split()]
print(int(answer=(d[0]*3+d[1])/2))


### FIXED CODE ###

#coding:utf-8
d=[int(i) for i in input().split()]
print(int((d[0]*3+d[1])/2))
import math
A, B, C, D = (map(int, input().split()))


s = C * D / math.gcd(C, D)

p  = B - A + 1 - int((B // C - (A - 1) // C) + (B // D - (A - 1) // D) - (B // s - (A - 1) // s))
print(p)


### FIXED CODE ###

from fractions import gcd
A, B, C, D = (map(int, input().split()))


s = int(C * D // gcd(C, D))

p  = B - A + 1 - int((B // C - (A - 1) // C) + (B // D - (A - 1) // D) - (B // s - (A - 1) // s))
print(p)
# (d1+d2)/2 == n1, (d2+d3)/2 == n2... が矛盾なくなるようにする
# にぶたんを使う

n = int(input())
dum = list(map(int, input().split()))
count = 0
l, r = 0, (10 ** 9 + 1000000) // 2

while True:
    mid = (l + r) // 2
    # print(l, r, mid)
    rain = [0 for _ in range(n)]
    rain[0] += mid * 2
    for i in range(1, n):
        next_amount = (dum[i - 1] - (rain[i - 1] // 2)) * 2
        rain[i] += next_amount
    # print(rain)

    if dum[-1] == (rain[-1] + rain[0]) // 2:
        rain = list(map(str, rain))
        print(" ".join(rain))
        exit()
    if (rain[0] + rain[-1]) // 2 < dum[-1]:
        # 最初に決めたやつが小さすぎた
        # print("{} は小さすぎた".format(rain[0]))
        l = mid + 1
    else:
        # 最初に決めたやつが大きすぎた
        # print("{} は大きすぎた".format(rain[0]))
        r = mid

    # セーフティネット 必要ないけど
    if count > 50:
        t = 5 / 0
        break
    count += 1

"""
7
110 50 53 50 11 36 88

11
38 7 15 15 9 31 23 1 5 55 81
"""


### FIXED CODE ###

# (d1+d2)/2 == n1, (d2+d3)/2 == n2... が矛盾なくなるようにする
# にぶたんを使う
# なんかしらんけど3問駄目だな...

n = int(input())
dum = list(map(int, input().split()))
count = 0
l, r = 0, (10 ** 10) // 2

while l < r:
    mid = (l + r) // 2
    # print(l, r, mid)
    rain = [0 for _ in range(n)]
    rain[0] += mid * 2
    for i in range(1, n):
        next_amount = (dum[i - 1] - (rain[i - 1] // 2)) * 2
        rain[i] += next_amount
    # print(rain)

    if dum[-1] == (rain[-1] + rain[0]) // 2:
        rain = list(map(str, rain))
        print(" ".join(rain))
        exit()
    if (rain[0] + rain[-1]) // 2 < dum[-1]:
        # 最初に決めたやつが小さすぎた
        # print("{} は小さすぎた".format(rain[0]))
        l = mid + 1
    else:
        # 最初に決めたやつが大きすぎた
        # print("{} は大きすぎた".format(rain[0]))
        r = mid

    # セーフティネット 必要ないけど
    if count > 50:
        t = 5 / 0
        break
    count += 1

"""
7
110 50 53 50 11 36 88

11
38 7 15 15 9 31 23 1 5 55 81
"""
A,B=input().split()
print(math.floor(int(A)*float(B)))


### FIXED CODE ###


import math
from decimal import *

A,B=input().split()
print(math.floor(Decimal(A)*Decimal(B)))
s = 0
now = As[0]
for a in As:
    if a<now:
        s += now - a
    else:
        now = a
        
print(s)

### FIXED CODE ###

N = input()
As = list(map(int, input().split()))

s = 0
now = As[0]
for a in As:
    if a<now:
        s += now - a
    else:
        now = a
        
print(s)
N = int(input())
A = list(map(int, input().split()))
if 0 in A:
    print(0)
    return
B = 1
for i in A:
    B = B * i
    if B >= 10 ** 18:
        print(-1)
        return
print(B)

### FIXED CODE ###

import sys
N = int(input())
A = list(map(int, input().split()))
if 0 in A:
    print(0)
    sys.exit()
B = 1
for i in A:
    B = B * i
    if B > 10 ** 18:
        print(-1)
        sys.exit()
print(B)
from calendar import isleap
f = lambda x: map(str, x) if x else ["NA"]
ans = []
while True:
    a, b = map(int, input().split())
    if b == 0:
        break
    ans += f(filter(isleap, range(a, b+1))) + [""]
print("\n".join(ans).strip())

### FIXED CODE ###

ans=[]
while True:
    a,b=map(int,raw_input().split())
    if (a,b)==(0,0):
        break
    t=[y for y in xrange(a,b+1) if (y%4==0 and not y%100==0) or y%400==0]
    if not t:
        ans.append("NA")
    else:
        ans.append("\n".join(map(str,t)))
print "\n\n".join(ans).strip()