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

def gcd(x, y):
    if x < y:
        x, y = y, x
    while x % y != 0:
        x, y = y, x % y
    return y


def gcd_3(x, y, z):
    x_y = gcd(x, y)
    return gcd(x_y, z)


K = int(input())
ans = 0

sum_list = []


for i in range(1, K + 1):
    for j in range(1, K + 1):
        for k in range(1, K + 1):
            ans += gcd_3(i, j, k)

print(ans)

### FIXED CODE ###


import math
k = int(input())
s = 0
box = [0]*(k+1)
for l in range (1,k+1):
     for m in range (1, k+1):
          box[math.gcd(l,m)] += 1
for l in range (1,k+1):
     for n in range (1, k+1):
          s += math.gcd(l,n)*box[l]
print(s)
### BUGGY CODE ###

N,*E=map(int,open(0).read().split())
E=sorted((e,2*(i<N)-1)for i,e in enumerate(E))
a,c=1,0
for _,d in E:
	if c*d<0:a*=abs(c)
	c+=d
print(a%(10**9+7))

### FIXED CODE ###

mod = 10 ** 9 + 7
INF = 10 ** 10

N = int(input())
A = [int(input()) for _ in range(N)] + [INF]
B = [int(input()) for _ in range(N)] + [INF]

A.sort()
B.sort()

ans = 1
a = b = 0
i = j = 0
while i < N or j < N:
    if A[i] < B[j]:
        if b > 0:
            ans *= b
            b -= 1
        else:
            a += 1
        i += 1
    else:
        if a > 0:
            ans *= a
            a -= 1
        else:
            b += 1
        j += 1

    ans %= mod

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

from collections import Counter

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

MAX = 10 ** 6
is_divisible = [True] * (MAX + 1)
is_divisible[0] = False
for i in A:
    if not is_divisible[i]:
        continue
    for j in range(i * 2, MAX + 1, i):
        is_divisible[j] = False

for k, v in Counter(A).items():
    if v > 1:
        is_divisible[k] = False

st = {i for i in range(MAX + 1) if is_divisible[i]}
print(len(st & set(A)))


### FIXED CODE ###

from collections import Counter

N = int(input())
A = list(map(int, input().split()))
S = sorted(list(set(A)))

MAX = 10 ** 6
is_divisible = [True] * (MAX + 1)
is_divisible[0] = False
for i in S:
    if not is_divisible[i]:
        continue
    for j in range(i * 2, MAX + 1, i):
        is_divisible[j] = False

for k, v in Counter(A).items():
    if v > 1:
        is_divisible[k] = False

ans = len([a for a in A if is_divisible[a]])
print(ans)
### BUGGY CODE ###

import sys
K=int(sys.stdin.readline().strip())
a=0
for i in range(10**7):
    a+=7*pow(10,i,K)
    a%=K
    if a==0:
        print i+1
        quit()
else:
    print -1

### FIXED CODE ###

import sys
N=int(sys.stdin.readline().strip())

a=0
for i in range(10**6):
    a+=7*pow(10,i,N)
    if a%N==0:
        print i+1
        quit()
else:
    print -1
### BUGGY CODE ###

import numpy as np


def solve(s):
    MOD = 10 ** 9 + 7
    dp = np.zeros(13, dtype=np.int64)
    idx = [0] * 13
    for i in range(13):
        idx[i * 10 % 13] = i
    window = np.ones(10, dtype=np.int64)
    dp[0] = 1
    for c in s:
        if c == '?':
            tdp = dp[idx]
            ndp = np.concatenate([tdp[4:], tdp])
            dp = np.convolve(ndp, window, mode='valid') % MOD
        else:
            dp = np.roll(dp[idx], int(c))
    return dp[5]


s = input()
print(solve(s))


### FIXED CODE ###

import numpy as np


def solve(s):
    MOD = 10 ** 9 + 7
    dp = np.zeros(13, dtype=np.int64)
    dp[0] = 1
    idx = np.zeros(13, dtype=np.int8)
    for i in range(13):
        idx[i * 10 % 13] = i
    window = np.ones(10, dtype=np.int8)
    for c in s:
        if c == '?':
            tdp = dp[idx]
            ndp = np.concatenate([tdp[4:], tdp])
            dp = np.convolve(ndp, window, mode='valid') % MOD
        else:
            dp = np.roll(dp[idx], int(c))
    return dp[5]


s = input()
print(solve(s))
### BUGGY CODE ###

from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    X = int(input())
    import math
    for i in range(0,10**5,2):
        for j in range(-1,-10**5,-2):
            if i == j:
                 continue
            if X % (i - j) == 0:
                if (i-j) * (pow(i,4) + pow(i,3)*j + pow(i,2)*pow(j,2) + i*pow(j,3) + pow(j,4)) == X:
                    print(i,j)
                    exit()
if __name__ == '__main__':
  main()


### FIXED CODE ###

from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    X = int(input())
    import math
    for i in range(-119,119):
        for j in range(-119,119):
            if i == j:
                continue
            if X % (i - j) == 0:
                if (i-j) * (pow(i,4) + pow(i,3)*j + pow(i,2)*pow(j,2) + i*pow(j,3) + pow(j,4)) == X:
                    print(i,j)
                    exit()
if __name__ == '__main__':
  main()
### BUGGY CODE ###

N = int(input())

if N%2 == 0:
  print(N, N, N//2)
else:
  for h in range(3500, -1, -1):
    for n in range(3500, -1, -1):
      num = N*h*n
      dem = 4*h*n - N*(h+n)
      if dem <= 0:
        break
      if dem > 0 and num%dem == 0:
        print(h, n, num//dem)
        quit()

### FIXED CODE ###

N = int(input())

if N%2 == 0:
  print(N, N, N//2)
else:
  for h in range(1, 3501):
    for n in range(1, 3501):
      num = N*h*n
      dem = 4*h*n - N*(h+n)
      if dem > 0 and num%dem == 0:
        print(h, n, num//dem)
        quit()
### BUGGY CODE ###

import sys
H, N = map(int, sys.stdin.readline().split())
m = map(int, sys.stdin.read().split())
AB = zip(m, m)
INF = 10**20
dp = [INF]*(H+10**4)
dp[0] = 0
for a, b in AB:
    for j in range(H+10**4):
        dp[j] = min(dp[j], dp[j-a] + b if j-a >= 0 else INF)
print(min(dp[H:]))


### FIXED CODE ###

import sys
H, N = map(int, sys.stdin.readline().split())
m = map(int, sys.stdin.read().split())
AB = zip(m, m)
INF = 10**20
dp = [INF]*(H+10**4)
dp[0] = 0
for a, b in AB:
    for j in range(H+10**4):
        dp[j] = min(dp[j], dp[j-a] + b if j-a >= 0 else INF)
print(min(dp[H:]))
### BUGGY CODE ###


K,S = map(int, input().split())
cnt = 0
K += 1
for X in range(K):
    if X > S:
        break
    for Y in range(K):
        if X + Y > S:
            break
        for Z in range(K):
            if X + Y + Z == S:
                cnt += 1
            if X + Y + Z > S:
                break

print(cnt)


### FIXED CODE ###


K,S = map(int, input().split())
cnt = 0

for X in range(K + 1):
    if S - X < 0:
        break
    for Y in range(K + 1):
        if S - X - Y < 0:
            break
        if S - X - Y <= K:
            cnt += 1

print(cnt)
### BUGGY CODE ###

n = int(input())
x = input()

num_of_1 = x.count("1")

first = int(x, 2)

def f(x):
    if x==0:
        return 0
    return 1+f(x%bin(x).count('1'))

for i in range(n):
    temp_num_of_1 = num_of_1 + 1 if x[i] == "0" else num_of_1 - 1

    ans = 0

    if temp_num_of_1 > 0:
        a = first + 2 ** (n - i - 1) if x[i] == "0" else first - 2 ** (n - i - 1)

        a = a % temp_num_of_1

        temp = bin(a)[2:]

        ans += 1 + f(a)

    print(ans)

### FIXED CODE ###

n = int(input())
x = input()

num_of_1 = x.count("1")

first = int(x, 2)

def f(x):
    if x == 0:
        return 0
    return 1 + f(x % bin(x).count('1'))

if num_of_1 == 1:
    for i in range(n):
        if x[i] == '1':
            print(0)
        elif i == n-1:
            print(2)
        else:
            print(1)
    exit()

first_one, first_zero = first % (num_of_1 - 1), first % (num_of_1 + 1)

for i in range(n):
    if x[i] == "0":
        print(1 + f((first_zero + pow(2, n-i-1, num_of_1 + 1)) % (num_of_1 + 1)))
    else:
        print(1 + f((first_one - pow(2, n-i-1, num_of_1 - 1)) % (num_of_1 - 1)))
### BUGGY CODE ###

N = int(input())
L = list(map(int,input().split()))
L.sort()

def b_search(L,key,left,right):
    #L[i] < keyを満たす最大のi
    #L[i] < key <= L[i+1]
    if key <= L[left]:
        return 0
    elif key > L[len(L)-1]:
        return len(L)
    else:
        mid = (left+right)//2
        if L[mid] < key and key <= L[mid+1]:
            return mid + 1
        elif L[mid] >= key:
            return b_search(L,key,left,mid)
        else:
            return b_search(L,key,mid,right)

ans = 0
for i in range(N-2):
    for j in range(i+1,N-1):
        L_ = L[j+1:]
        ans += b_search(L_,L[i]+L[j],0,len(L_))
print(ans)


### FIXED CODE ###

from bisect import bisect_left

N = int(input())
L = list(map(int,input().split()))
L.sort()

ans = 0
for i in range(N-2):
    for j in range(i+1,N-1):
        ans += bisect_left(L,L[i]+L[j])-(j+1)
print(ans)
### BUGGY CODE ###

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

x=0
ans = (math.floor(a * x / b) - a * math.floor(x / b))
while(True):
    if x>=n:break
    x+=1
    ans_tmp = (math.floor(a * x / b) - a * math.floor(x / b))
    if ans>0 and ans_tmp==0: break
    else: ans=ans_tmp

print(ans)

### FIXED CODE ###

import math
a,b,n = list(map(int,input().split()))
if b-1>=n:
    x=n
else:x=b-1
print(math.floor(a*x/b)-a*math.floor(x/b))
### BUGGY CODE ###

import queue

N = int(input())
stack = queue.Queue()
stack.put([1,1,0])
count = 0
while True:
    point = stack.get()
    point0,point1,point2 = point[0],point[1],point[2]+1
    point_x = [point0+1,point1,point2]
    point_y = [point0,point1+1,point2]
    if point_x[0] * point_x[1] == N:
        print(point_x[2])
        break
    if point_y[0] * point_y[1] == N:
        print(point_y[2])
        break
    stack.put(point_x)
    stack.put(point_y)


### FIXED CODE ###

import math
N = int(input())

for i in range(int(math.sqrt(N))+1,0,-1):
    if N%i == 0:
        j = N//i
        print(j+i-2)
        break
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,m = LI()
    a = [LI() for _ in range(m)]
    e = [[] for _ in range(n)]
    for l,r,d in a:
        e[l-1].append((r-1,d))
        e[r-1].append((l-1,-d))

    b = [False] * n
    def g(i,c):
        if c == False:
            c = 0
        b[i] = c
        for r,d in e[i]:
            if b[r] != False:
                if b[r] != c+d:
                    return False
            else:
                if not g(r,c+d):
                    return False
        return True

    for i in range(n):
        if b[i] != False:
            continue
        if not g(i,False):
            return 'No'
    return 'Yes'


print(main())





### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,m = LI()
    e = [[] for _ in range(n)]
    if m > 0:
        for _ in range(m):
            l,r,d = LI()
            e[l-1].append((r-1,d))
            e[r-1].append((l-1,-d))

    b = [None] * n

    for i in range(n):
        if not b[i] is None:
            continue
        b[i] = 0
        q = [i]
        qi = 0
        nq = []
        while True:
            if len(q) == qi:
                if not nq:
                    break
                q = nq
                qi = 0
                nq = []
            j = q[qi]
            qi += 1
            c = b[j]
            for r,d in e[j]:
                if b[r] is None:
                    b[r] = c+d
                    nq.append(r)
                else:
                    if b[r] != c+d:
                        return 'No'

    return 'Yes'


print(main())
### BUGGY CODE ###

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

lists = []
for i in range(b-a+1):
    lists.append(a)
    a += 1
an = 0

for j in lists:
    if j % (c*d) == 0:
        an += 1
    elif j % c == 0:
        an += 1
    elif j % d == 0:
        an += 1
print(len(lists)-an)

### FIXED CODE ###

from fractions import gcd
import math
a,b,c,d = map(int,input().split())

if c == 1 or d == 1:
    print(0)
elif a == b:
    if a%c == 0 or a%d == 0:
        print(0)
    else:
        print(1)
else:
    an1 = (b//c)
    an2 = ((a-1)//c)
    an3 = (b//d)
    an4 = ((a-1)//d) 
    gcd = round(c * d / gcd(c, d))
    an5 = (b//gcd)
    an6 = ((a-1)//gcd)
    if c == d:
        an = an1-an2
    else:
        an = an1-an2 + an3-an4 -(an5-an6)
    print((b-a+1)-an)
### BUGGY CODE ###

N,M=map(int,input().split())
L=list(tuple(map(int,input().split())) for _ in range(N))
L.sort(key=lambda x: x[1]*10**6-x[0], reverse=True)
ans=0
for i in range(1,M+1):
    for j,[a,b] in enumerate(L):
        if a<=i:
            ans+=b
            L.pop(j)
            break
print(ans)

### FIXED CODE ###

import sys, heapq
input=sys.stdin.readline
N,M=map(int,input().split())
L=sorted([tuple(map(int,input().split())) for _ in range(N)])
Llen=len(L)
k=0
ans=0
heap=[]
for i in range(1,M+1):
    while k<Llen:
        a,b=L[k]
        if a<=i: heapq.heappush(heap,-b)
        else: break
        k+=1
    if len(heap)>0:
        ans+=-heapq.heappop(heap)
print(ans)
### BUGGY CODE ###

while 1:
    n,p = map(int,input().split())
    if n==0:break
    man = [i for i in [0]*n]
    ball,a = p,0
    while p not in man:
        if ball == 0:ball,man[a%n] = man[a%n],ball
        if ball >0:
            ball,man[a%n] =ball-1, man[a%n]+1
        a+=1
    print(man.index(max(man)))        

### FIXED CODE ###

while 1:
    n,p = map(int,input().split())
    if n==0:break
    man =  [0]*n
    ball,a = p,0
    while 1:
        a%=n
        if ball >0:
            ball-=1
            man[a]+=1
        elif ball == 0:ball,man[a] = man[a],ball
        if man[a]==p:break
        a+=1
    print(a)
### BUGGY CODE ###

import collections
import math


def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


N = int(input())
A = list(map(int, input().split()))
c = collections.Counter(A)
cnt = 0
for i in A:
    for x, y in c.items():
        if i == x and y >= 3:
            cnt += combinations_count(y - 1, 2)
        elif i != x and y >= 2:
            cnt += combinations_count(y, 2)
    print(cnt)
    cnt = 0


### FIXED CODE ###

import collections
import math

N = int(input())
A = list(map(int, input().split()))
c = collections.Counter(A)
cnt = 0


sumall = 0
for x, y in c.items():
    sumall += (y*(y-1)//2)

for i in range(N):
    print(sumall - c[A[i]] + 1)
### BUGGY CODE ###

n = int(input())
L6 = []
L9 = []
for i in range(1, 100):
  num = 6 ** i
  if num <= n:
    L6.append(num)
  else:
    break
for i in range(1, 100):
  num = 9 ** i
  if num <= n:
    L9.append(num)
  else:
    break

from itertools import product
iter6 = product(range(0, 6), repeat=len(L6))
Res6 = []
for iter in iter6:
  total = 0
  counter = 0
  for num, l in zip(iter, L6):
    total += num * l
    counter += num
  if n - total >= 0:
    Res6.append([n - total, counter])
#print(Res6)

iter9 = product(range(0, 9), repeat=len(L9))
Res9 = []
for iter in iter9:
  total = 0
  counter = 0
  for num, l in zip(iter, L9):
    total += num * l
    counter += num
  Res9.append([total, counter])

#print(list(product(Res6, Res9)))

min_x = n
for pairs in product(Res6, Res9):
  if pairs[0][0] - pairs[1][0] >= 0:
    x = pairs[0][0] - pairs[1][0] + pairs[0][1] + pairs[1][1]
    min_x = min(min_x, x)
print(min_x)


### FIXED CODE ###

n = int(input())

L6 = []
for i in range(1, 100):
  if 6**i <= n:
    L6.append(6**i)
  else:
    break

L9 = []
for i in range(1, 100):
  if 9**i <= n:
    L9.append(9**i)
  else:
    break

dp = [0] * (n+1)
    
for i in range(1, n+1):
  dp[i] = dp[i-1] + 1
  for l6 in L6:
    if i - l6 >= 0:
      dp[i] = min(dp[i], dp[i - l6] + 1)
  for l9 in L9:
    if i - l9 >= 0:
      dp[i] = min(dp[i], dp[i - l9] + 1)
print(dp[n])
### BUGGY CODE ###

import sys
from collections import deque
n, m = [int(i) for i in sys.stdin.readline().split()]
graph = {j:[] for j in range(3 * n)}
for i in range(m):
    u, v = [int(i) for i in sys.stdin.readline().split()]
    u -= 1
    v -= 1
    graph[u].append(n+v)
    graph[u+n].append(2*n+v)
    graph[u + 2 * n].append(v)
s, t = [int(i) for i in sys.stdin.readline().split()]
s -= 1
t -= 1

que = [(0, s)]
flg = False
parent = [-1 for i in range(3 * n)]
while que:
    cost, cur = que[0]
    que.pop(0)
    if cur == t:
        flg = True
        break
    for i in graph[cur]:
        if parent[cur] != i:
            que.append((cost + 1, i))
            parent[i] = cur
if not flg:
    cost = -1
else:
    cost //= 3

print(cost)

### FIXED CODE ###

import sys
INF = 10 ** 9
n, m = [int(i) for i in sys.stdin.readline().split()]
graph = {j:[] for j in range(3 * n)}
for i in range(m):
    u, v = [int(i) for i in sys.stdin.readline().split()]
    u -= 1
    v -= 1
    graph[u].append(n+v)
    graph[u+n].append(2*n+v)
    graph[u + 2 * n].append(v)
s, t = [int(i) for i in sys.stdin.readline().split()]
s -= 1
t -= 1

que = [s]
flg = False
already = set()
dist = [INF for i in range(3 * n)]
dist[s] = 0
while que:
    cur= que[0]
    que.pop(0)
    for i in graph[cur]:
        if i not in already:
            if i == t:
                res = dist[cur] + 1
                que.clear()
                flg = True
                break
            que.append(i)
            dist[i] = dist[cur] + 1
            already.add(i)
if not flg:
    res = -1
else:
    res //= 3

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

n = int(input())
s_lis =[]
for _ in range(n):
    s = sorted(input())
    s_lis.append("".join(s))


ans = 0
for i in range(n):
    for j in range(i+1,n):
        if s_lis[i] == s_lis[j]:
            ans += 1

print(ans)


### FIXED CODE ###

n = int(input())
ans = 0
dic = {}
for i in range(n):
    s = input()
    s = str(sorted(s))
    tmp = dic.get(s,0)
    ans += tmp
    dic[s] = tmp + 1

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

from collections import deque

h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]

cnt_white = 0
for row in s:
    cnt_white += row.count('.')

d = deque([[0, 0]])
dist = [[0] * w for _ in range(h)]
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
goal_flag = False
while d:
    x, y = d.popleft()
    if x == h - 1 and y == w - 1:
        goal_flag = True
        break
    for i in range(4):
        pos_x, pos_y = x + dx[i], y + dy[i]
        if 0 <= pos_x < h and 0 <= pos_y < w and s[pos_x][pos_y] == '.':
            d.append([pos_x, pos_y])
            dist[pos_x][pos_y] = dist[x][y] + 1
    s[x][y] = '#'

if goal_flag:
    print(cnt_white - dist[h-1][w-1] - 1)
else:
    print(-1)

### FIXED CODE ###

from collections import deque

h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]

cnt_white = 0
for row in s:
    cnt_white += row.count('.')

d = deque([[0, 0]])
dist = [[-1] * w for _ in range(h)]
dist[0][0] = 0
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
goal_flag = False
while d:
    x, y = d.popleft()
    if x == h - 1 and y == w - 1:
        goal_flag = True
        break
    for i in range(4):
        pos_x, pos_y = x + dx[i], y + dy[i]
        if 0 <= pos_x < h and 0 <= pos_y < w and s[pos_x][pos_y] == '.' and dist[pos_x][pos_y] == -1:
            d.append([pos_x, pos_y])
            dist[pos_x][pos_y] = dist[x][y] + 1

if goal_flag:
    print(cnt_white - dist[h-1][w-1] - 1)
else:
    print(-1)
### BUGGY CODE ###

import collections
n = int(input())
s = [input() for i in range(n)]
c = collections.Counter(s)
num = c.most_common()[0][1]
list=[]
for i in range(len(c)):
	if num == c.most_common()[i][1]:
		list.append(c.most_common()[i][0])
list = sorted(list)
for i in list:
	print(i)

### FIXED CODE ###

n = int(input())
d = dict()

for i in range(n):
    s = input()
    if s in d:
        d[s] += 1
    else:
        d[s] = 1

M = max(d.values())

ans_list = []
for k,v in d.items():
    if v == M:
        ans_list.append(k)

ans_list.sort()
for i in ans_list:
    print(i)
### BUGGY CODE ###

N=int(input())
p=0
for i in range(1,N):
  if i**2<=N:
    p=p+1
  else:
    break
    
q=p   
for i in range(p,N):
  if N%i!=0:
    q=q+1
  else:
    break
    
print((q+(N//q))-2)

### FIXED CODE ###

N=int(input())
p=0
for i in range(1,N):
  if i**2<=N:
    p=p+1
  else:
    break
    
q=p   
for i in reversed(range(p+1)):
  if N%i!=0:
    q=q-1
  else:
    break
    
print((q+(N//q))-2)
### BUGGY CODE ###

n,k = map(int, input().split())
res = []
for _ in range(n):
    a,b = map(int, input().split())
    res += [a]*b
res.sort()
print(res[k-1])

### FIXED CODE ###

n,k = map(int, input().split())
res = [0]*(10**5+1)
for _ in range(n):
    a,b = map(int, input().split())
    res[a] += b

for i, x in enumerate(res):
    if k>x:
        k -= x
    else:
        print(i)
        exit()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)

debug = True
debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)



def solve():
    N = int(input())
    A = list(map(int, input().split()))


    def check(A, x):
        ans = [x]
        for i in range(1, N):
            tmp = A[i-1] - ans[i-1]
            if tmp < 0:
                if i % 2 == 1:
                    return 1, ans
                else:
                    return -1, ans
            else:
                ans.append(tmp)

        tmp = A[N-1] - (ans[N-1])
        if x > tmp:
            return 1, ans
        elif x < tmp:
            return -1, ans
        else:
            return 0, ans

    x = min(A[0], A[N - 1])
    jump = N // 2

    # i = 0
    while True:
        # i += 1
        # if i > 10:
        #     break
        ret, ans = check(A, x)
        if ret == 1:
            x = x - jump
        elif ret == -1:
            x = x + jump
        else:
            dprint(x, ret, ans, jump)
            break
        jump = max(jump // 2, 1)
        dprint(x, ret, ans, jump)

    print(" ".join([str(i*2) for i in ans]))

solve()

### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 7)

debug = True
debug = False


def dprint(*objects):
    if debug == True:
        print(*objects)


def solve():
    N = int(input())
    A = list(map(int, input().split()))

    def check(A, x):
        ans = [x]
        for i in range(1, N):
            tmp = A[i - 1] - ans[i - 1]
            if tmp < 0:
                if i % 2 == 1:
                    return 1, ans
                else:
                    return -1, ans
            else:
                ans.append(tmp)

        tmp = A[N - 1] - (ans[N - 1])
        if x > tmp:
            return 1, ans
        elif x < tmp:
            return -1, ans
        else:
            return 0, ans

    x = min(A[0], A[N - 1])
    jump = min(A[0], A[N - 1]) // 2

    # i = 0
    while True:
        # i += 1
        # if i > 10:
        #     break
        ret, ans = check(A, x)
        if ret == 1:
            x = x - jump
        elif ret == -1:
            x = x + jump
        else:
            dprint(x, ret, ans, jump)
            break
        jump = max(jump // 2, 1)
        dprint(x, ret, ans, jump)

    print(" ".join([str(i * 2) for i in ans]))


solve()