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

N, M, Q = map(int, input().split())
li = []
for q in range(Q):
    a, b, c, d = map(int, input().split())
    li.append([[a,b], c, d])
ok_list = []
def dfs(num_li, depth):
    if len(num_li) == N:
        ok_list.append(num_li)
        return
    if depth == M:
        return
    dfs(num_li, depth+1)
    while len(num_li) <N:
        num_li += str(depth)
        dfs(num_li, depth+1)
dfs("", 0)
maxpoint = 0
for ok in ok_list:
    point = 0
    for q in range(Q):
        if int(ok[li[q][0][1]-1])- int(ok[li[q][0][0]-1]) == li[q][1]:
            point += li[q][2]
    if point > maxpoint:
        maxpoint = point
print(maxpoint)


### FIXED CODE ###

N, M, Q = map(int, input().split())
li = []
for q in range(Q):
    a, b, c, d = map(int, input().split())
    li.append([[a,b], c, d])
ok_list = []
def dfs(num_li, depth):
    if len(num_li) == N:
        ok_list.append(num_li)
        return
    if depth == M:
        return
    dfs(num_li, depth+1)
    while len(num_li) <N:
        num_li += str(depth)
        dfs(num_li, depth+1)
dfs("", 0)
maxpoint = 0
for ok in ok_list:
    point = 0
    for q in range(Q):
        if int(ok[li[q][0][1]-1])- int(ok[li[q][0][0]-1]) == li[q][1]:
            point += li[q][2]
    if point > maxpoint:
        maxpoint = point
print(maxpoint)
### BUGGY CODE ###

import fractions
from functools import reduce

def gcd_list(n):
    return reduce(fractions.gcd, n)


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

ans = max(gcd_list(a[1:]), gcd_list(a[:n - 1]))
for i in range(1, n - 1):
    ans = max(ans, fractions.gcd(gcd_list(a[:i]), gcd_list(a[i + 1:])))

print(ans)

### FIXED CODE ###

import fractions

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

l = [a[0]]
for i in range(n - 1):
    l.append(fractions.gcd(l[i], a[i + 1]))

r = [a[-1]]
for i in range(2, n + 1):
    r.append(fractions.gcd(r[i - 2], a[-i]))
r.reverse()

ans = r[1]
for i in range(n - 2):
    ans = max(ans, fractions.gcd(l[i], r[i + 2]))
ans = max(ans, l[-2])
print(ans)
### BUGGY CODE ###

R,G,B,N=map(int,input().split())

ans=0
for r in range(N//R+1):
  for g in range(N//G+1):
    if 0<=N-r*R-g*G and (N-r*R-g*G)%B==0:
      #print(r,g,(N-r*R+g*G)//B)
      ans += 1
      
print(ans)

### FIXED CODE ###

R,G,B,N=map(int,input().split())

ans=0
for r in range(N//R+1):
  for g in range(N//G+1):
    if 0<=N-r*R-g*G and (N-r*R-g*G)%B==0:
      #print(r,g,(N-r*R+g*G)//B)
      ans += 1
      
print(ans)
### BUGGY CODE ###

n = int(input())
s = str(input())
count = 0

for i in range(n):
    for j in range(i + 1, n):
        if (s[i] != s[j]):
            for k in range(j + 1, n):
                if (s[i] != s[k]) & (s[j] != s[k]) & (j - i != k - j):
                    count += 1
print(count)

### FIXED CODE ###

n = int(input())
s = str(input())
ans = s.count('R') * s.count('G') * s.count('B')

for i in range(n - 1):
    for j in range(i + 1, n):
        k = j + j - i

        if k >= n:
            break

        if (s[i] != s[j]) & (s[i] != s[k]) & (s[j] != s[k]):
            ans -= 1
            
print(ans)
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
f=list(map(int,input().split()))
a.sort()
if sum(a)<=k:
    print(0)
    exit()
f.sort(reverse=True)
l=0
r=10**12
x=(r+l)//2
def check(x):
    p=0
    for i in range(n):
        if x//f[i]<a[i]:
            p+=a[i]-x//f[i]
            if p>k:
                return False
    if p>k:
        return False
    else:
        return True
while l+1<r:
    if check(x):
        r=x
        x=(r+l)//2
    else:
        l=x
        x=(r+l)//2
print(r)


### FIXED CODE ###

import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)

a = []
f = []
n = 0

def rec(l, r, k):
    if l+1 < r:
        mid = (l + r) // 2
        s = 0
        for i in range(n):
            s += max(a[i] - mid // f[i], 0)
        if s <= k:
            return rec(l, mid, k)
        else:
            return rec(mid, r, k)
    else:
        return r

def main():
    global a, f, n
    n, k = map(int, input().strip().split())
    a = list(map(int, input().strip().split()))
    f = list(map(int, input().strip().split()))
    a = sorted(a)
    f = sorted(f, reverse=True)
    print(rec(-1, 10**12, k))

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

N = int(input())
A_list = []
A_count_list = []
for i in range(N):
    A = int(input())
    A_count_list.append(A)
    for j in range(len(A_list)):
        if A_list[j] < A:
            A_list.insert(j, A)
            A = 0
    if A != 0:
        A_list.append(A)
max_index = A_count_list.index(max(A_count_list))
for i in range(N):
    if i == max_index:
        print(A_list[1])
    else:
        print(A_list[0])

### FIXED CODE ###

N = int(input())
A_list = []
for i in range(N):
    A = int(input())
    A_list.append(A)
sort_A = sorted(A_list, reverse = True)
max_f = sort_A[0]
max_s = sort_A[1]
for i in range(N):
    print(max_s) if A_list[i] == max_f else print(max_f)
### BUGGY CODE ###

n=int(input())
a = list(map(int, input().split()))
an=0
for i in range(n-1):
    s=a[i]
    for j in range(s+i+1,n):
        if j-i==a[j]+s:
            an+=1
print(an)

### FIXED CODE ###

import collections
n=int(input())
a = list(map(int, input().split()))
an=0
ii=[]
jj=[]
for i in range(n):
    ii.append(i+a[i])
    jj.append(i-a[i])
jjj=collections.Counter(jj)
for i in range(n):
    an+=jjj[ii[i]]
print(an)
### BUGGY CODE ###

N,M = map(int,input().split())
A = list(map(int,input().split()))
L = [0]*M

for i in A:
    cnt = 0
    while i!=0 or cnt<M:
        d = i-i//2
        if min(L)<d: 
            L[L.index(min(L))] = d
            i//=2
            cnt+=1
        else:
            break

print(sum(A)-sum(L))

### FIXED CODE ###

import heapq
from math import ceil
n,m = map(int,input().split())
a = [-int(i) for i in input().split()]
heapq.heapify(a)

for i in range(m):
    heapq.heappush(a,ceil(heapq.heappop(a)/2))

print(-sum(a))
### BUGGY CODE ###

#!/usr/bin/env python
# coding: utf-8

# In[1]:


N, Q = map(int, input().split())
abs_ = [list(map(int, input().split())) for _ in range(N-1)]
pxs_ = [list(map(int, input().split())) for _ in range(Q)]


# In[13]:


class Node:
    def __init__(self, nb, data): #コンストラクタ
        self.nb = nb
        self.data = data #ノードがもつ数値
        self.parent = -1 # nodeがrootのとき-1、それ以外番号
        self.childs = [] # childになるnode classが入る
        
    def connect_childs(self, child_class_):
        self.childs.append(child_class_)
        
    def get_childs(self):
        return self.childs
    
    def sum_data(self, data):
        self.data += data


# In[21]:


nodes = [Node(_+1, 0) for _ in range(N)]


# In[22]:


for i in range(N-1):
    a, b = abs_[i]
    nodes[a-1].connect_childs(nodes[b-1])
    nodes[b-1].parent = a-1


# In[25]:


def sum_x(node, x):
    node.data += x
    for child in node.childs:
        sum_x(child, x)


# In[28]:


for i in range(Q):
    p, x = pxs_[i]
    sum_x(nodes[p-1], x)


# In[32]:


datas = [str(nodes[_].data) for _ in range(N)]
print(' '.join(datas))


# In[ ]:






### FIXED CODE ###

#!/usr/bin/env python
# coding: utf-8

# In[17]:


from sys import stdin
input = stdin.readline

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


# In[18]:


class Node:
    def __init__(self, nb, data): #コンストラクタ
        self.nb = nb
        self.data = data #ノードがもつ数値
        self.parent = -1 # nodeがrootのとき-1、それ以外番号
        #self.childs = [] # childになるnode classが入る
        
    #def connect_childs(self, child_class_):
    #    self.childs.append(child_class_)


# In[19]:


nodes = [Node(_+1, 0) for _ in range(N)]


# In[12]:


for i in range(N-1):
    a, b = map(int, input().split())
    #nodes[a-1].connect_childs(nodes[b-1])
    nodes[b-1].parent = a-1


# In[13]:


for i in range(Q):
    p, x = map(int, input().split())
    nodes[p-1].data += x


# In[14]:


def sum_data_to_childs(nodes):
    datas = [0]*N
    
    datas[0] = nodes[0].data
    
    for i in range(1, N):
        nodes[i].data += nodes[nodes[i].parent].data
        #print(nodes[i].data)
        datas[i] = nodes[i].data
        
    return datas


# In[15]:


datas = sum_data_to_childs(nodes)


# In[16]:


print(' '.join(map(str, datas)))


# In[20]:


#datas = [0] * N


# In[21]:


#child = [[]] * N


# In[22]:


#print(child)


# In[ ]:
### BUGGY CODE ###

def main():
    S = input()
    s = list(S)
    n = len(s)
    ans = [[0 for i in range(13)]for i in range(n)]
    if s[0] == '?':
        for i in range(10):
            ans[0][i] += 1
    else:
        ans[0][int(s[0])] += 1
    for i in range(n-1):
        if s[i+1] == '?':
            for j in range(10):
                for k in range(13):
                    ans[i+1][(10*k+j)%13] += ans[i][k]
        else:
            for k in range(13):
                ans[i+1][(10*k+int(s[i+1]))%13] += ans[i][k]
    print((ans[n-1][5])%(10**9+7))
if __name__ == '__main__':
    main()

### FIXED CODE ###

S = input()
s = list(S)
n = len(s)
ans = [[0 for i in range(13)]for i in range(n)]
mod = 10**9+7
if s[0] == '?':
    for i in range(10):
        ans[0][i] += 1
else:
    ans[0][int(s[0])] += 1
for i in range(n-1):
    if s[i+1] == '?':
        for j in range(10):
            for k in range(13):
                ans[i+1][(10*k+j)%13] += ans[i][k]%mod
    else:
        for k in range(13):
            ans[i+1][(10*k+int(s[i+1]))%13] += ans[i][k]%mod
print((ans[n-1][5])%(10**9+7))
### BUGGY CODE ###

N, M = map(int, input().split())
al = []
for i in range(M):
  al.append(tuple(input().split()))
al_a = [i[0] for i in al if i[1] == 'AC']
al_a = list(set(al_a))
r1 = len(al_a)
r2 = 0
for j in al:
  if j[0] in al_a and j[1] == 'AC':
    al_a.remove(j[0])
  elif j[1] == 'WA' and j[0] in al_a:
    r2 += 1
    
print(r1 ,r2)

### FIXED CODE ###

def main():
    n, m = map(int, input().split())
    ac = [0] * n
    wanum = [0] * n
    for _ in range(m):
        p, s = input().split()
        p = int(p) - 1
        if ac[p]:
            continue
        else:
            if s == 'AC':
                ac[p] = 1
                wanum[p] *= -1
            else:
                wanum[p] -= 1
    wanum2 = [i for i in wanum if i > 0]
    print(sum(ac), sum(wanum2))

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

def solve():
    A, B, K = map(int, input().split())
    for i in range(A, B+1):
        if A <= i <= A+K-1 or B-K+1 <= i <= B:
            print(i)
if __name__ == '__main__':
    solve()

### FIXED CODE ###

A, B, K = map(int, input().split())

if K<(B-A)/2+1:
    for i in range(A, A+K):
        print(i)
    for i in range(B-K+1, B+1):
        print(i)
else:
    for i in range(A, B+1):
        print(i)
### BUGGY CODE ###

n = int(input())
s = [''.join(sorted(list(input()))) for i in range(n)]


cnt = 0
for i in range(len(s)):
    tmp = s[i+1:].count(s[i])
    cnt += tmp

print(cnt)


### FIXED CODE ###

n = int(input())
s = [''.join(sorted(input())) for i in range(n)]

cnt = 0
dic = {}
for i in s:
    dic.setdefault(i, 0)
    cnt += dic[i]
    dic[i] += 1

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

N, M = map(int, input().split())
PY = [list(map(int,input().split())) for i in range(M)]
ken = {p[0] for p in PY}
ken_d = {k:[]  for k in ken}

for p in PY:
    ken_d[p[0]].append(p[1])

for k in ken_d.keys():
    ken_d[k].sort()

for p in PY:
    x = ken_d[p[0]].index(p[1]) + 1
    print(str(p[0]).zfill(6) + str(x).zfill(6))

### FIXED CODE ###

N, M = map(int, input().split())
import sys
PY = [list(map(int,sys.stdin.readline().rstrip().split())) for _ in range(M)]

# ken = {p[0] for p in PY}
# ken_d = {k:[] for k in ken}
ken_d = [[] for _ in range(N+1)]

rankdic = {} # 通し番号：県における順位

for i, p in enumerate(PY):
    # print(p)
    ken_d[p[0]].append([i, p[1]])

for k in range(N+1):
    ken_d[k].sort(key=lambda x:x[1])
    for i, v in enumerate(ken_d[k]):
        rankdic[v[0]] = i # 通し番号辞書に入れる

for i, p in enumerate(PY):
    x = rankdic[i] + 1
    print(str(p[0]).zfill(6) + str(x).zfill(6))
### BUGGY CODE ###

N = int(input())
S = input()
ans=0

for i in range(N-2):
    for j in range(i+1,N-1):
        if S[i]==S[j]:
            continue
        for k in range(j+1,N):
            if S[i]!=S[k] and S[j]!=S[k] and j-i!=k-j:
                ans+=1
print(ans)


### FIXED CODE ###

N = int(input())
S = input()
ans=0

r=0
g=0
b=0

for i in range(N):
    if S[i]=="R":
        r+=1
    elif S[i]=="G":
        g+=1
    else:
        b+=1

ans=r*g*b

for j in range(1,N-1):
    for d in range(1,min(j,N-j-1)+1):
        if S[j-d]!= S[j] and S[j]!= S[j+d] and S[j-d]!= S[j+d]:
            ans-=1
print(ans)
### BUGGY CODE ###

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

b = [0]

for i in range(n):
    b.append(b[i]+a[i])

ans = 0

for i in range(min(b),max(b)+1):
    n = b.count(i)
    
    ans += int((n*(n-1))/2)

print(ans)

### FIXED CODE ###

from itertools import accumulate
from collections import Counter

n = int(input())
l = list(map(int,input().split()))
l.insert(0,0)
a = list(accumulate(l))

count_a = Counter(a)

ans = 0

for i in count_a.values():
    if i < 2:
        continue
    ans += i*(i-1)/2
        

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

def main():
    import sys
    from fractions import gcd
    input = sys.stdin.readline

    def init(init_val):
        #set_val
        for i in range(n):
            seg[i+num-1]=init_val[i]    
        #built
        for i in range(num-2,-1,-1) :
            seg[i]=gcd(seg[2*i+1],seg[2*i+2]) 
        
    def update(k,x):
        k += num-1
        seg[k] = x
        while k:
            k = (k-1)//2
            seg[k] = gcd(seg[k*2+1],seg[k*2+2])
        
    def query(p,q):
        if q<=p:
            return ide_ele
        p += num-1
        q += num-2
        res=ide_ele
        while q-p>1:
            if p&1 == 0:
                res = gcd(res,seg[p])
            if q&1 == 1:
                res = gcd(res,seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = gcd(res,seg[p])
        else:
            res = gcd(gcd(res,seg[p]),seg[q])
        return res



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

    #####単位元######
    ide_ele = 0

    #num:n以上の最小の2のべき乗
    num =2**(n-1).bit_length()
    seg=[ide_ele]*2*num
    init(a)

    ans = -1
    for i in range(n):
        ans = max(ans,gcd(query(0,i),query(i+1,n)))
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

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

import fractions
if N==2:
  print(max(A))
else:
  L=[0]*(N)
  R=[0]*(N)
  L[0]=A[0]
  R[N-1]=A[N-1]
  for i in range(1,N):
    L[i]=fractions.gcd(L[i-1],A[i])
  for i in range(N-1,0,-1):
    R[i-1]=fractions.gcd(R[i],A[i-1])
  ans=0
  for i in range(1,N-1):
    x=fractions.gcd(L[i-1],R[i+1])
    ans=max(ans,x)

  print(max(ans,L[N-2],R[1]))
### BUGGY CODE ###

def rec(n, w, ws, vs, dp):
    if w == 0 or n < 0:
        return 0
    if dp[n][w] > -1:
        return dp[n][w]
    if ws[n] <= w:
        dp[n][w] = max(dp[n][w], rec(n-1, w-ws[n], ws, vs, dp) + vs[n])
    dp[n][w] = max(dp[n][w], rec(n-1, w, ws, vs, dp))
    return dp[n][w]

def resolve():
    n, w = map(int, input().split())
    ws, vs = [0]*n, [0]*n
    for i in range(n):
        ws[i], vs[i] = map(int, input().split())
    dp = [[-1] * (w + 1) for _ in range(n + 1)]
    print(rec(n-1, w, ws, vs, dp))
resolve()

### FIXED CODE ###

def resolve():
    n, w = map(int, input().split())
    ws, vs = [0]*n, [0]*n
    for i in range(n):
        ws[i], vs[i] = map(int, input().split())
    dp = [[0]*(w+1) for _ in range(n+1)]
    for i in range(n):
        for j in range(w+1):
            if j >= ws[i]:
                dp[i][j] = max(dp[i][j], dp[i-1][j - ws[i]] + vs[i])
            dp[i][j] = max(dp[i][j], dp[i-1][j] if i - 1 >= 0 else 0)
    print(dp[n-1][w])
resolve()
### BUGGY CODE ###

from sys import stdin
f_i = stdin

N = int(f_i.readline())

adj = [[] for i in range(N)]
for i in range(N - 1):
    A, B = map(int, f_i.readline().split())
    A -= 1
    B -= 1
    adj[A].append(B)
    adj[B].append(A)

from sys import setrecursionlimit
setrecursionlimit(10 ** 6)

subtree_size = []
def dfs(node, parent):
    cnt = 1
    for child in adj[node]:
        if child != parent:
            cnt += dfs(child, node)
    
    subtree_size.append(cnt)
    return cnt

dfs(0, None)

mod = 10 ** 9 + 7
pow2 = [(2 ** i) % mod for i in range(N + 1)]

ans = 0
for s in subtree_size:
    ans += (pow2[s] - 1) * (pow2[N-s] - 1)

ans = ans - N * pow2[N-1] + pow2[N] - 1
ans = ans * pow(pow2[N], mod - 2, mod) % mod

print(ans)

### FIXED CODE ###

from sys import stdin
f_i = stdin

N = int(f_i.readline())

adj = [[] for i in range(N)]
for i in range(N - 1):
    A, B = map(int, f_i.readline().split())
    A -= 1
    B -= 1
    adj[A].append(B)
    adj[B].append(A)

mod = 10 ** 9 + 7

pow2 = [1] * (N + 1)
for i, j in zip(range(N), range(1, N + 1)):
    pow2[j] = pow2[i] * 2 % mod

from sys import setrecursionlimit
setrecursionlimit(10 ** 6)

ans = 0

def dfs(node, parent):
    global ans
    cnt = 1
    
    for child in adj[node]:
        if child != parent:
            cnt += dfs(child, node)
    
    ans += (pow2[cnt] - 1) * (pow2[N-cnt] - 1)
    ans %= mod
    
    return cnt

dfs(0, None)

ans = (ans - N * pow2[N-1] + pow2[N] - 1) % mod
ans = ans * pow(pow2[N], mod - 2, mod) % mod

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

N = int(input())
line = [int(i) for i in input().split()]
sum = 1
for num in line:
  if num == 0:
    print(0)
    exit()
  sum = sum * num
if sum > 10 ** 18:
  print(-1)
else:
  print(sum)

### FIXED CODE ###

N = int(input())
line = [int(i) for i in input().split()]
sum = 1
line.sort(reverse=True)
if line[len(line) -1]== 0:
  print(0)
  exit()
for num in line:
  sum = sum * num
  if sum > 10 ** 18:
    print(-1)
    exit()
print(sum)
### BUGGY CODE ###

N, M = map(int, input().split())
flag = True
for i in range(N, M//3 + 1):
    if M%i == 0:
        print(M//i)
        flag = False
        break
if flag:
    if M%2 == 0 and M//2 >= N:
        print(2)
    else:
        print(1)

### FIXED CODE ###

N, M = map(int, input().split())
# また答えが見つかってなければTrue
flag = True
for i in range(N, M//10 + 1):
    if M%i == 0:
        print(M//i)
        flag = False
        break
for i in range(9):
    if flag and M%(10 - i) == 0 and M//(10 - i) >= N:
        print(10 - i)
        flag = False
if flag:
    print(1)
### BUGGY CODE ###

import math
from functools import reduce

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

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0 :
            if i!=1:
                divisors.append(i)
            if i != n // i:

                divisors.append(n//i)

    divisors.sort()
    return divisors

    


def gcd(*numbers):
    return reduce(math.gcd, numbers)

def gcd_list(numbers):
    return reduce(math.gcd, numbers)
S=[]
tmp=gcd_list(T)
if tmp!=1:
    print("not coprime")
else:
    T.sort()

    n=10**6+1
    isprime=[True]*(n+1)
    isprime[0]=False
    isprime[1]=False
    for i in range(len(T)):
        S=make_divisors(T[i])
        #print(S)
        while len(S)!=0: 
            tmp=S.pop()
            if isprime[tmp]==True:
                j=tmp+tmp
                while j<=n:
                     
                    isprime[j] =False
                    j=j+tmp
                    
                        
            else:
                print("setwise coprime")
                exit()
    print("pairwise coprime")
    

### FIXED CODE ###

import math
from functools import reduce

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

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0 :
            if i!=1:
                divisors.append(i)
            if i != n // i:

                divisors.append(n//i)

    divisors.sort()
    return divisors

    


def gcd(*numbers):
    return reduce(math.gcd, numbers)

def gcd_list(numbers):
    return reduce(math.gcd, numbers)
S=[]
tmp=gcd_list(T)
if tmp!=1:
    print("not coprime")
else:
    T.sort()

    n=10**6+1
    isprime=[True]*(n+1)
    isprime[0]=False
    isprime[1]=False
    for i in range(len(T)):
        S=make_divisors(T[i])
        #print(S)
        while len(S)!=0: 
            tmp=S.pop()
            if isprime[tmp]==True:
                j=tmp+tmp
                while j<=n:
                     
                    isprime[j] =False
                    j=j+tmp
                    
                        
            else:
                print("setwise coprime")
                exit()
    print("pairwise coprime")
### BUGGY CODE ###

# どちらか必ずa_Nのカードを持つ
import sys
from functools import lru_cache

sys.setrecursionlimit(4000)

N,Z,W = map(int,input().split())
A = list(map(int,input().split()))
A.reverse()

# turn: true->X, false->Y
BOTTOM = A[0]

@lru_cache(maxsize=2000000)
def rec_X(i,y):
  return max(abs(BOTTOM-y),max((rec_Y(j,A[j]) for j in range(1,i)), default=0))

@lru_cache(maxsize=2000000)
def rec_Y(i,x):
  return min(abs(BOTTOM-x),min((rec_X(j,A[j]) for j in range(1,i)), default=float('inf')))

print(rec_X(N,W))

### FIXED CODE ###

# どちらか必ずa_Nのカードを持つ

N,Z,W = map(int,input().split())
A = list(map(int,input().split()))
A.reverse()
A.append(W)

BOTTOM = A[0]

M = float('inf')
m = 0

for a in A[1:]:
  x = abs(BOTTOM-a)
  t = max(x,m)
  s = min(x,M)
  M = min(M,t)
  m = max(m,s)

print(t)
### BUGGY CODE ###

from functools import reduce
N, K = map(int, input().split())
A = list(map(int, input().split()))

for k in range(N-K):
    score1 = reduce(lambda x,y: x*y, A[k:K+k])
    score2 = reduce(lambda x, y: x*y, A[k+1:K+k+1])
    if score1 < score2:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

from functools import reduce
N, K = map(int, input().split())
A = list(map(int, input().split()))

for k in range(N-K):
    score1 = A[k]
    score2 = A[K+k]
    if score1 < score2:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

n=int(input())
mini = (10** 12)+1
X=0
Y=0
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    return divisors
ans = make_divisors(n)
for i in range(len(ans)):
  for j in range(len(ans)):
    if mini>ans[i]-ans[j] and n==ans[i]*ans[j] and ans[i]>=ans[j]:
      mini =ans[i]-ans[j]
      X=ans[i]
      Y=ans[j]
print(X-1+Y-1)

### FIXED CODE ###

n=int(input())
mini = (10** 12)+1
X=0
Y=0
t=0
K=0
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    return divisors
ans = make_divisors(n)
ans.sort()
K+=len(ans)
if K%2:
  for i in range(int((K+1)/2)):
    t=-(i+1)
    if mini>ans[t]-ans[i] and n==ans[t]*ans[i] and ans[t]>=ans[i]:
      mini =ans[t]-ans[i]
      X=ans[t]
      Y=ans[i]
else:
  for i in range(int(K/2)):
    t=-(i+1)
    if mini>ans[t]-ans[i] and n==ans[t]*ans[i] and ans[t]>=ans[i]:
      mini =ans[t]-ans[i]
      X=ans[t]
      Y=ans[i]
print(X-1+Y-1)
### BUGGY CODE ###

import sys
import os
import itertools

n = int(input())

def is_prime(n):
    for p in range(2, n):
        if n % p == 0:
            return 0
    return 1

a = is_prime(n)
if a == 1:
    print(n-1)
    sys.exit()


def make_divisors(n):
    divisors = {}
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors[i] = n//i
            if i != n // i:
                divisors[i] = n//i

    return divisors

ans = make_divisors(n)
m = max(ans)
print( (m-1) + ans[m]-1)

### FIXED CODE ###

import sys
import os
import itertools

n = int(input())

def make_divisors(n):
    divisors = {}
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors[i] = n//i
            if i != n // i:
                divisors[i] = n//i

    return divisors

ans = make_divisors(n)
m = max(ans)
print( (m-1) + ans[m]-1)