Harryxun/stf_run huggingface dataset:
from collections import deque
def bfs(field,visited,sy,sx,gy,gx):
    queue = deque([[sy,sx]])
    visited[sy][sx] = 0
    while queue:
        y,x = queue.popleft()
        if [y,x] == [gy,gx]:
            return visited[y][x]

        for j,k in ([1,0],[-1,0],[0,1],[0,-1]):
            new_y, new_x = y+j, x+k
            if new_y < 0 or new_y > gy or new_x < 0 or new_x > gx:
              continue
            if field[new_y][new_x] == "." and visited[new_y][new_x] == -1:
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])

if __name__ == "__main__":

    h,w=map(int,input().split())
    sy=1
    sx=1
    field=[list(input()) for i in range(h)]
    visited = [[-1]*w for i in range(h)]
    sy, sx, gy, gx = sy-1, sx-1, h-1, w-1
    ans = bfs(field,visited,sy,sx,gy,gx)
    cnt=0
    for i in range(h):
      for j in range(w):
        if field[i][j]==".":
          cnt+=1
    if ans==None:
      print(-1)
    else:
      print(cnt - bfs(field,visited,sy,sx,gy,gx) -1)

### FIXED CODE ###

from collections import deque
def bfs(field,visited,sy,sx,gy,gx):
    queue = deque([[sy,sx]])
    visited[sy][sx] = 0
    while queue:
        y,x = queue.popleft()
        if [y,x] == [gy,gx]:
            return visited[y][x]
 
        for j,k in ([1,0],[-1,0],[0,1],[0,-1]):
            new_y, new_x = y+j, x+k
            if new_y < 0 or new_y > gy or new_x < 0 or new_x > gx:
              continue
            if field[new_y][new_x] == "." and visited[new_y][new_x] == -1:
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])
                
if __name__ == "__main__":
 
    h,w=map(int,input().split())
    sy=1
    sx=1
    field=[list(input()) for i in range(h)]
    visited = [[-1]*w for i in range(h)]
    sy, sx, gy, gx = sy-1, sx-1, h-1, w-1
    ans=bfs(field,visited,sy,sx,gy,gx)
    #print(ans)
    cnt=0
    for i in range(h):
      for j in range(w):
        if field[i][j]==".":
          cnt+=1
    if ans == None:
      print(-1)
    else:
      print(cnt - ans -1)
N = int(input())
A = list(map(int, input().split()))

def dfs(A, k, cnt=0):
  s1, s2 = 0, 0
  for i in range(len(A)):
    if i <= N / 2:
      if A[k] > 1:
        A[k] -= 1
        cnt += 1
      s1 += A[i]
    else:
      if A[k] > 1:
        A[k] -= 1 
      s2 += A[i]
  if s1 == s2:
    return cnt
  if A[k] > 1:
    return dfs(A, k, cnt)
  else:
    return dfs(A, k + 1, cnt)

s = 0
for i in range(len(A)):
  s += A[i]
if s % 2 == 0:
  print(0)
  exit()
else:
  ans = dfs(A, 0)
  print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
total = sum(A)
mid = total // 2
sum_left, sum_left2 = 0, 0
seperation_i = 0
for i, l in enumerate(A[:-1]):
  sum_left += l
  if sum_left >= mid:
      seperation_i = i
      sum_left2 = sum_left - l
      break
sum_right, sum_right2 = sum(A[seperation_i + 1:]), sum(A[seperation_i:])
print(min(abs(sum_right - sum_left), abs(sum_right2 - sum_left2)))
t1,t2 = map(int, input().split())
a1,a2 = map(int, input().split())
b1,b2 = map(int, input().split())

d1=(a1-b1)*t1
d2=(a2-b2)*t2


if abs(d1) == abs(d2):
    print("infinity")
    exit()

if abs(d1) > abs(d2) or d1*d2>0
    print(0)
    exit()

dif = abs(d2) - abs(d1)

ans=2*(abs(d1)//dif)
if abs(d1)%dif != 0:
    ans+=1
print(ans)

### FIXED CODE ###

t1,t2 = map(int, input().split())
a1,a2 = map(int, input().split())
b1,b2 = map(int, input().split())

d1=(a1-b1)*t1
d2=(a2-b2)*t2


if abs(d1) == abs(d2):
    print("infinity")
    exit()

if abs(d1) > abs(d2) or d1*d2>0:
    print(0)
    exit()

dif = abs(d2) - abs(d1)

ans=2*(abs(d1)//dif)
if abs(d1)%dif != 0:
    ans+=1
print(ans)
l = map(int, raw_input().split())
print (l[0] * l[1]), ((l[0] + l[1]) * 2)


### FIXED CODE ###

a, b = map(int, input().split())
print(a * b, (a + b) * 2)
n = int(input())
a = [int(i) for i in input().split()]
ans = 0
for i in range(n):
  if (i+1) % 2 == 1 and a[i] % 2 == 1:
    c += 1
else:
  print(ans)


### FIXED CODE ###

N = int(input())
A = [int(i) for i in input().split()]
c = 0
 
for i in range(N):
  if (i+1) % 2 == 1 and A[i] % 2 == 1:
    c += 1
else:
  print(c)
a = map(int, raw_input().split())
  
#a.sort()
print '%d %d %d' % (a[1], a[2], a[3])

### FIXED CODE ###

a = map(int, raw_input().split())
  
a.sort()
print '%d %d %d' % (a[0], a[1], a[2])
r = input()
pi = 3.14159265359
s = pi * decimal(r)**2
l = 2.0 * pi * decimal(r)

print s, l

### FIXED CODE ###

import math

r = float(input())

s = math.pi * r**2
l = 2.0*math.pi*r

print(s, l)
N,M=map(int,input().split())
ans=10**(N-1)
if M==0:
    print(ans)
else:
    S=[]
    C=[]
    for i in range(M):
        s,c=map(int,input().split())
        S.append(s)
        C.append(c)
    for i in range(1000):
        flag=True
        I=str(i)
        for j in range(M):
            if N<S[j]:
                flag=False
            else:
                if I[S[j]-1]!=str(C[j]):
                    flag=False
        if flag==True:
            print(i)
            exit()
    print(-1)

### FIXED CODE ###

N,M=map(int,input().split())
if M==0:
    if N==1:
        print(0)
    else:
        print(10**(N-1))
else:
    S=[]
    C=[]
    for i in range(M):
        s,c=map(int,input().split())
        S.append(s)
        C.append(c)
    if N==1:
        o=0
    else:
        o=10**(N-1)
    for i in range(o,10**N):
        flag=True
        I=str(i)
        for j in range(M):
            if N<S[j]:
                flag=False
            else:
                if I[S[j]-1]!=str(C[j]):
                    flag=False
        if flag==True:
            print(i)
            exit()
    print(-1)
# WIP
N, M = map(int, input().split())

if N == 1:
    print(max(M - 2, 0)))
elif M == 1:
    print(max(M - 2, 0)))
elif N == 1 and M == 1:
    print(1)
else:
    # Number of cards appearing "back"
    # = (N-2)*(M-2)
    print(max((N - 2) * (M - 2), 0))

"""
# An experiment
n_count_map = [[0 for _ in range(M)] for _ in range(N)]


def update(x, y):
    # Count
    n_count_map[y][x] += 1
    if y + 1 < N:
        n_count_map[y + 1][x] += 1
    if y - 1 >= 0:
        n_count_map[y - 1][x] += 1
    if x + 1 < M:
        n_count_map[y][x + 1] += 1
    if x - 1 >= 0:
        n_count_map[y][x - 1] += 1
    if y + 1 < N and x + 1 < M:
        n_count_map[y + 1][x + 1] += 1
    if y - 1 >= 0 and x - 1 >= 0:
        n_count_map[y - 1][x - 1] += 1
    if y + 1 < N and x - 1 >= 0:
        n_count_map[y + 1][x - 1] += 1
    if y - 1 >= 0 and x + 1 < M:
        n_count_map[y - 1][x + 1] += 1


for n in range(N):
    for m in range(M):
        update(m, n)

print(n_count_map)
"""


### FIXED CODE ###

# WIP
N, M = map(int, input().split())

if N == 1 and M == 1:
    print(1)
elif N == 1:
    print(M - 2 if M > 2 else 0)
elif M == 1:
    print(N - 2 if N > 2 else 0)
elif N > 2 and M > 2:
    print((N - 2) * (M - 2))
else:
    print(0)

"""
# An experiment
n_count_map = [[0 for _ in range(M)] for _ in range(N)]


def update(x, y):
    # Count
    n_count_map[y][x] += 1
    if y + 1 < N:
        n_count_map[y + 1][x] += 1
    if y - 1 >= 0:
        n_count_map[y - 1][x] += 1
    if x + 1 < M:
        n_count_map[y][x + 1] += 1
    if x - 1 >= 0:
        n_count_map[y][x - 1] += 1
    if y + 1 < N and x + 1 < M:
        n_count_map[y + 1][x + 1] += 1
    if y - 1 >= 0 and x - 1 >= 0:
        n_count_map[y - 1][x - 1] += 1
    if y + 1 < N and x - 1 >= 0:
        n_count_map[y + 1][x - 1] += 1
    if y - 1 >= 0 and x + 1 < M:
        n_count_map[y - 1][x + 1] += 1


for n in range(N):
    for m in range(M):
        update(m, n)

print(n_count_map)
"""
import string

# 1千兆 + 1
N = int(input())
n_digits = len(str(1000000000000001))
map_letters = { i:v for i,v in enumerate(string.ascii_lowercase)}

x = N - 1
ans = []
for d in range(n_digits):
    if x == 0:
        break
    mod = x % 26
    ans = [ mod ] + ans
    x = x // 26

fa = []
for i in range(len(ans)-1):
    fa.append(ans[i]-1)
fa.append(ans[-1])
print(
    ''.join(map(lambda d: map_letters[d], fa))
)

### FIXED CODE ###

import string

# 1千兆 + 1
N = int(input())
n_digits = len(str(1000000000000001))
letters = string.ascii_lowercase

x = N - 1
ans = []
# while True:
#     mod = x % 26
#     ans = [ mod ] + ans
#     x = x // 26
#     if x <= 0:
#         if ans[0] == 0:
#             ans = [0] + ans
#         break

# print(ans)
# print("".join([ letters[v] for v in ans ]))

while True:
    mod = x % 26
    div = x // 26
    
    ans.append(mod)
    if div == 0:
        break
    x = div - 1

ans = ans[::-1]
# print(ans)
print("".join([ letters[v] for v in ans ]))
import sys
from collections import deque
n = int(sys.stdin.readline())
q = deque()
for i in range(n):
    c = sys.stdin.readline()[:-1]
    if c[0] == 'i':
        q.appendleft(c[7:])
    elif c[6] == ' ':
        q.remove(c[7:])
    elif c[6] == 'F':
        q.popleft()
    else:
        q.pop()
print(*q)

### FIXED CODE ###

from collections import deque
n = int(input())
q = deque()
for i in range(n):
    c = input()
    if c[0] == 'i':
        q.appendleft(c[7:])
    elif c[6] == ' ':
        try:
            q.remove(c[7:])
        except:
            pass
    elif c[6] == 'F':
        q.popleft()
    else:
        q.pop()
print(*q)
import math
N, X, T = map(int,input().zsplit())

a = math.ceil(N / X)
b = T * a

print(b)

### FIXED CODE ###

import math
N, X, T = map(int, input().split())

a = math.ceil(N / X)
b = T * a

print(b)
def min_sufficient_load(w, k):
    return check(w, k, 0, sum(w))


def check(w, k, p1, p2):
    trunk_no = 1
    temp = 0
    m = 1+(p1 + p2)>>1
    for i in w:
        if temp + i <= m:
            temp += i
            if temp==m:
                trunk_no+=1
                temp = 0
        else:
            trunk_no += 1
            temp = i
    if trunk_no > k:
        return check(w, k, m, p2)
    else:
        if m - p2 == 0:
            return m
        return check(w, k, p1, m)
if __name__=="__main__":
    n,k = map(int,input().split(" "))
    w = []
    for i in range(n):
        w.append(int(input()))
    print(min_sufficient_load(w,k))


### FIXED CODE ###

import math
def min_sufficient_load(w, k):
    return check(w, k, 0, sum(w))

def check(w, k, p1, p2):
    if k==1:
        return p2
    if p2 - p1 == 1:
        if get_trunk_No(w, p1) == k:
            return max(p1,max(w))
        else:
            return max(p2,max(w))
    m = math.ceil((p1+p2)/2)
    trunk_no = get_trunk_No(w,m)
    if trunk_no > k:
        return check(w, k, m, p2)
    else:
        return check(w, k, p1, m)
def get_trunk_No(w,m):
    temp = 0
    trunk_no = 1
    for i in w:
        if temp + i <= m:
            temp += i
            if temp == m:
                trunk_no += 1
                temp = 0
        else:
            trunk_no += 1
            temp = i
    if temp==0:
        trunk_no-=1
    return trunk_no
if __name__=="__main__":
    n,k = map(int,input().split(" "))
    w = []
    for i in range(n):
        w.append(int(input()))
    print(min_sufficient_load(w,k))
n = int(input())
l = list(map(int, input().split()))
l.sort()
ans = 0
#a[b]の答え
at = []
def at_memo(x):
    if x==0:
        return []
    if x in at:
        return at[x]
    atx = [l[x]+l[i] for i in range(x)]  
    at[x] = at[x-1] + atx
    return at[x]

for x in range(1,n):
    for i in range(len(at_memo(x-1))):
        if l[x]-at_memo(x-1)[i]>0:
            ans += 1
        else:
            continue

### FIXED CODE ###

n = int(input())
l = list(map(int, input().split()))
l.sort(reverse=True)
ans = 0
for i in range(n-2):
    j = i+1
    k = n-1
    while j < k:
        if l[i]<l[j]+l[k]:
            ans += k-j
            j += 1
        else:
            k -= 1
print(ans)
from collections import deque
def main():
  N, M, *L = map(int, open(0).read().split())
  dic = [[] for i in range(N+1)]
  par =  [None]*N
  cnt = [0]*(N+1)
  cnt[0] = 1
  for a,b in zip(*[iter(L)]*2):
    dic[a].append(b)
    cnt[b] += 1

  for i, m in enumerate(cnt):
    if m==0:
      q = deque([i])
      par[i-1] = 0
      break
  
  while q:
    m = q.popleft()
    for c in dic[m]:
      cnt[c] -= 1
      if cnt[c]==0:
        par[c-1] = str(m)
        q.append(c)

  ans = '\n'.join(par)
  print(ans)
  
if __name__== '__main__':
  main()

### FIXED CODE ###

from collections import defaultdict, deque
N, M = map(int, input().split())
dic = defaultdict(list)
par =  [0]*(N+1)
cnt = [0]*(N+1)
for i in range(N-1+M):
  a, b = map(int, input().split())
  dic[a] += [b]
  cnt[b] += 1

for i in range(1,N+1):
  if cnt[i]==0:
    q = deque([i])
    break
  
while q:
  m = q.popleft()
  for c in dic[m]:
    cnt[c] -= 1
    if cnt[c]==0:
      par[c] = m
      q += [c]

for i in range(1,N+1):
  print(par[i])
A,B = map(int, input().split())
if A>B:
    print('GREATER')
elif A<B:
    print('LESS')
else:
    print('EQUAL')

### FIXED CODE ###

A=int(input())
B=int(input())
if A>B:
    print('GREATER')
elif A<B:
    print('LESS')
else:
    print('EQUAL')
s=sorted(list(set(input())))
flag=True
for i in range(26):
  a=i+97
  if int(ord(s[i]))-a!=0:
    flag=False
    break
print('None' if flag else chr(a))

### FIXED CODE ###

s=sorted(list(set(input())))
flag=True
for i in range(26):
  a=i+97
  if s.count(chr(a))==0:
    flag=False
    break
print('None' if flag else chr(a))
N = int(input())
for i in range(1:32):
    for j in range(1:10):
        if i**j <= N:
            ans = max(ans,i**j)
print(ans)

### FIXED CODE ###

N = int(input())
ans=1
for i in range(1,32):
    for j in range(2,10):
        if i**j <= N:
            ans = max(ans,i**j)
        else:
            break
print(ans)
n = int(input())
a = map(int, input().split())
import numpy as np
npa = np.array(a)
print(1/(sum(1/a)))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
import numpy as np
npa = np.array(a)
print(1/(sum(1/npa)))
N, L = map(int, input().split())
P = [input().split() for i in range(L)]

p = sorted(P)
print(p[0] + p[1] + p[2])

### FIXED CODE ###

N, L = map(int, input().split())
S = [input() for i in range(N)]
s = sorted(S)
print(*s, sep='')
INF = 10 ** 20
def minimum_cost(rest, init, dic):
  if rest in dic:
    return dic[rest]

  if rest == ():
    return 0

  ret = INF
  for nex in rest:
    nex_init = init + acc[nex]
    ret = min(ret, minimum_cost(tuple(i for i in rest if i != nex), nex_init, dic) +\
                   acc[nex] - (cums[nex][nex_init] - cums[nex][init]))
  dic[rest] = ret
  return ret

n, m = map(int, input().split())
acc = [0] * m
cums = [[0] for _ in range(m)]
for _ in range(n):
  acc[int(input()) - 1] += 1
  for i in range(m):
    cums[i].append(acc[i])

dic = {}
print(minimum_cost(tuple(i for i in range(m)), 0, dic))


### FIXED CODE ###

def main():
  INF = 10 ** 20
  def minimum_cost(rest, h, init, dic):
    if h in dic:
      return dic[h]
  
    if not h:
      return 0
  
    ret = INF
    for nex in rest:
      accnex = acc[nex]
      cumsnex = cums[nex]
      nex_init = init + accnex
      nex_rest = rest[:]
      nex_rest.remove(nex)
      nex_h = h - 2 ** nex
      tmp =  minimum_cost(nex_rest, nex_h, nex_init, dic) +\
                     accnex - (cumsnex[nex_init] - cumsnex[init])
      if ret > tmp:
        ret = tmp
    dic[h] = ret
    return ret
  
  n, m = map(int, input().split())
  acc = [0] * m
  cums = [[0] for _ in range(m)]
  for _ in range(n):
    acc[int(input()) - 1] += 1
    for i in range(m):
      cums[i].append(acc[i])
  
  dic = {}
  h = sum([2 ** i for i in range(m)])
  print(minimum_cost([i for i in range(m)], h, 0, dic))

main()
N = input().split()
A = input().split()
a = []

if int(N[0]) >= 2 and int(N[0]) <= 200000:
  n = int(N[0])
  for i in range(n):
    if int(A[i]) >= 1 and int(A[i]) <= 2020202020:
      a.append(int(A[i]))

right = 0
left = 0
cnt = 0
herf = 0

for i in range(n):
  cnt += a[i]
herf = int(cnt/2)
for i in range(n):
  left += a[i]
  if left > herf:
    left -= a[i]
    right = cnt - left
    break
print(abs(left-right))







### FIXED CODE ###

num = input().split()
nums = []
for i in num:
  nums.append(int(i))
#print(nums)
price = [300000, 200000, 100000]
result = []

#2 3 4 5 6
for i in nums:
  if int(i) > 3:
    result.append(0)
  else:
    result.append(price[i-1])
value = result[0] + result[1]
if value == 600000:
  print("1000000")
else:
  print(value)
N = int(input())

i=1
now=26
before = 0
while True:
    if N <= now:
        break
    i += 1
    before = now
    now += 26**i
    
#print(i)
M = N-before
alphabet = "abcdefghijklmnopqrstuvwxyz"
ans=""
for j in range(i):
    dig = int(M//26**(i-j-1))
    #print(dig)
    if j==i-1:
        ans = ans + alphabet[dig-1]
    else:
        ans = ans + alphabet[dig]
        M -= dig*26**(i-j-1)
    
print(ans)

### FIXED CODE ###

N = int(input())

i=1
now=26
before = 0
while True:
    if N <= now:
        break
    i += 1
    before = now
    now += 26**i
    
#print(i)
M = N-before
alphabet = "abcdefghijklmnopqrstuvwxyz"
ans=""
for j in range(i):
    dig = int((M-1)//26**(i-j-1))
    #print(M, dig)
    ans = ans + alphabet[dig]
    M -= dig*26**(i-j-1)
    
print(ans)
S = input()
T = input()

for i in range(len(T), 0, -1):
    for j in range(len(T)-i+1):
        subst = T[j:i+j]
#        print(subst)
        if S.find(subst, j, len(S)-(len(T)-i-j))>=0:
            print (len(T)-i)
            print(subst)
#            exit(0)


### FIXED CODE ###

S = input()
T = input()

def matchcount(x, y):
    ret = 0
    for i in range(len(x)):
        if x[i] == y[i]: ret += 1
    return ret

rec = len(T)
for i in range(len(S)-len(T)+1):
    subst = S[i:i+len(T)]
#    print(subst, matchcount(subst, T))
    rec = min(rec, len(T) - matchcount(subst, T))

print(rec)
5
2 4
1 9
1 8
4 9
3 12

### FIXED CODE ###

N=int(input())
ba=[list(map(int,input().split()))[::-1]for _ in range(N)]
ba.sort()
 
time=0
ans='Yes'
for b,a in ba:
    time+=a
    if time>b:
        ans='No'
print(ans)
w = int(raw_input())
n = int(raw_input())
a = []
for i in range(n):
  a.append(map(int, raw_input().split(',')))
  r = range(1,w + 1)
  for i in a:
    tmp = r[i[0] - 1]
    r[i[0] - 1] = r[i[1] - 1]
    r[i[1] - 1] = tmp
 for i in r:
   print i

### FIXED CODE ###

w = int(raw_input())
n = int(raw_input())
a = []
for i in range(n):
  a.append(map(int, raw_input().split(',')))
r = range(1,w + 1)
for i in a:
  tmp = r[i[0] - 1]
  r[i[0] - 1] = r[i[1] - 1]
  r[i[1] - 1] = tmp
for i in r:
  print i
import copy
n=int(input())
a=[int(input()) for i in range(n)]
maxa=max(a)
if len(a)!=1:
  maxa2=sorted(set(a))[-2]
maxs=a.count(maxa)
for i in range(n):
  if maxs==1:
    print(maxa if a[i]!=maxa else maxa2)
  else:
    print(maxa)

### FIXED CODE ###

import copy
n=int(input())
a=[int(input()) for i in range(n)]
maxa=max(a)
if len(set(a))!=1:
  maxa2=sorted(set(a))[-2]
maxs=a.count(maxa)
for i in range(n):
  if maxs==1:
    print(maxa if a[i]!=maxa else maxa2)
  else:
    print(maxa)
import math

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


n = int(input())
L = []
S = set()
count = 0
for i in range(n):
    line = "".join(sorted(list(input())))
    L.append(line)
    S.add(line)


for s in S:
    count += comb(L.count(s), 2)

print(count)

### FIXED CODE ###

n = int(input())
D = {}
count = 0
for i in range(n):
    line = "".join(sorted(list(input())))
    if line not in D:
        D[line] = 0
    else:
        D[line] += 1
        count += D[line]

print(count)
a,b,c=map(int, input.split())
max=a*c
if b >= max:
    print(c)
else:
    print(b//a)


### FIXED CODE ###

a,b,c=map(int, input().split())
if b >= a*c:
    print(c)
else:
    print(b//a)
import math
a, b = input().split()
print(math.floor(a * b))

### FIXED CODE ###

from math import floor
from decimal import Decimal
a, b = map(Decimal, input().split())
print(floor(a*b))
import sys
import os


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    W, H, x, y = list(map(int, sys.stdin.buffer.readline().split()))
    P = 0

    if W == x or H == y:
        ret = W * H
    else:
        Py = x * H
        Px = y * W
        ret = max(Py, Px)
        
    P = 1 if Py == Px else 0
    print(ret, P)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import os


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    W, H, x, y = list(map(float, sys.stdin.buffer.readline().split()))
    ret = (W * H) / 2
    p = x == W/2 and y == H/2
    print(ret, 1 if p else 0)


if __name__ == '__main__':
    main()
N, M = map(int, input().split())
x_list = list(map(int, input().split()))

x_list.sort()
ans = 0

margin = [0] * (M - 1)
f = x_list[0]
for i in range(1, M):
    margin[i - 1] = x_list[i] - f
    f = x_list[i]
margin = sorted(enumerate(margin), key=lambda x: (-x[1], x[0]))
cnt = [0]
for i, v in margin:
    cnt.append(i + 1)
    if len(cnt) == N:
        break

start = 0
prev = x_list[0]
for i, c in enumerate(cnt[1:]):
    for j in range(start, c):
        ans += x_list[j] - prev
        prev = x_list[j]
    start = c
    prev = x_list[c]
last = cnt[-1]
for i in range(last, M):
    if i == last:
        prev = x_list[i]
    else:
        ans += x_list[i] - prev
        prev = x_list[i]
print(ans)


### FIXED CODE ###

T, x = map(int, input().split())
print(T/x)
s = input()
k = int(input())
subs = []
for i in range(len(s)):
    for j in range(len(s)):
        if j > i:
            if j - i > 5:
                break
            if s[i:j] not in subs:
                subs.append(s[i:j])
            # print(i,j)
if len(s) <= 5:
    subs.append(s)
# print(sorted(subs))
print(sorted(subs)[k-1])

### FIXED CODE ###

s = input()
k = int(input())
subs = []
for i in range(len(s)):
    for j in range(5):
        if s[i:i+j+1] not in subs:
            subs.append(s[i:i+j+1])
subs = sorted(subs)
# print(subs)
print(subs[k-1])
import numpy as np
n = int(input())
ans = 0
field = [list(map(int,input().split())) for _ in range(n)]
dp = np.zeros((n + 1,3),np.int64)
for i in range(n):
  for j in range(3):
    for k in range(3):
      if j == k:
        continue
      dp[i + 1][k] = max(dp[i + 1][k],dp[i][j] + field[i][k])
for d in dp[-1]:
  ans = max(ans,d)
print(ans)

### FIXED CODE ###

import numpy as np
n = int(input())
ans = 0
field = [map(int,input().split()) for _ in range(n)]
x,y,z = 0,0,0
# 1つ前の値のみわかればよいので
# aにはa,a,aがbには
for a,b,c in field:
  #x,y,zは毎回入れ替わるので活動は連続しない
  x,y,z = max(y,z) + a,max(x,z) + b,max(x,y) + c

print(max(x,y,z))
rmap = {
  "AC": 0,
  "WA": 0,
  "TLE": 0,
  "RE": 0,
}

output_order = ["AC", "WA", "TLE", "RE"]

N - int(input())
for _ in range(N):
  rmap[input()] += 1

for k in output_order:
  print("{} x {}".format(k, rmap[k]))

### FIXED CODE ###

rmap = {
  "AC": 0,
  "WA": 0,
  "TLE": 0,
  "RE": 0,
}

output_order = ["AC", "WA", "TLE", "RE"]

N = int(input())
for _ in range(N):
  rmap[input()] += 1

for k in output_order:
  print("{} x {}".format(k, rmap[k]))
#include<iostream>
#include<vector>
#include<bitset>
#include<string>
#include<cmath>
#include<algorithm>
#include<stack>
#include<list>
#include<queue>
#include<map>
#include<numeric>
using namespace std;
#define rep(i,x) for(int i=0;i<x;i++)
#define re(i,x,y) for(int i=x;i<y;i++)
int INF=1e9;
const long long mod=1e9+7;
typedef long long ll;

int main(){
  ll A,B,C,D;
  cin>>A>>B>>C>>D;
  D=max(C,D),C=min(C,D);
  ll E=__gcd(C,D);
  ll lcm=C*D/E;
  ll F=(A-1)/C;
  ll G=B/C;
  ll H=(A-1)/D;
  ll I=B/D;
  ll J=(A-1)/lcm;
  ll K=B/lcm;
  cout<<(B-A+1)-(G-F)-(I-H)+(K-J)<<endl;
  return 0;
}

### FIXED CODE ###

from fractions import gcd
a,b,c,d=map(int,input().split())
lcm=c*d//gcd(c,d)
nc=b//c-a//c
nd=b//d-a//d
nlcm=b//lcm-a//lcm
if a%c==0:
  nc+=1
if a%d==0:
  nd+=1
if a%lcm==0:
    nlcm+=1
print(b-a+1-nc-nd+nlcm)
import sympy

n = int(input())

ans = 0
for i in range(1, n+1):
    ans += i * (len(sympy.divisors(i)))

print(ans)


### FIXED CODE ###

n = int(input())

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

print(ans)
S = int(input())
h = ??????????±????????¨????
m = ???????±????????¨????
s = ?§?????±????????¨????
print(h,m,s, sep=':')

### FIXED CODE ###

S = int(input())
h = S // 3600
m = S % 3600 // 60
s = S % 60
print(h, m, s, sep=':')