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

import sys


class Square:
    def __init__(self, num, x, y):
        self.num = num
        self.x = x
        self.y = y
        self.adj = {self.num: 0}

    def merge(self, other):
        dist = abs(self.x - other.x) + abs(self.y - other.y)
        for k, m in other.adj.items():
            self.adj[k] = dist + m


def main():
    h, w, d = [int(x) for x in input().split()]
    dic = {}
    for i in range(h):
        line = [int(x) for x in input().split()]
        for j, a in enumerate(line):
            dic[a] = Square(a, i, j)
    for a in range(h*w, 0, -1):
        if a + d <= h*w:
            dic[a].merge(dic[a+d])
    q = int(input())
    for k in range(q):
        l, r = [int(x) for x in input().split()]
        print(dic[l].adj[r])


main()


### FIXED CODE ###

import sys
import numpy as np


def main():
    h, w, d = [int(x) for x in input().split()]
    dic = {}
    for i in range(h):
        line = [int(x) for x in input().split()]
        for j, a in enumerate(line):
            dic[a] = (a, i, j)
    magic = [[0] for _ in range(d + 1)]
    for k in range(1, d + 1):
        for m in range(1, h * w):
            if k + (m * d) > h * w:
                break
            magic[k].append(magic[k][m - 1] +
                            abs(dic[k + (m * d)][1] - dic[k + ((m - 1) * d)][1]) +
                            abs(dic[k + (m * d)][2] - dic[k + ((m - 1) * d)][2]))
    q = int(input())
    for _ in range(q):
        l, r = [int(e) for e in input().split()]
        k = d if l % d == 0 else l % d
        print(magic[k][(r - 1) // d] - magic[k][(l - 1) // d])


main()
### BUGGY CODE ###

def main():
    n = int(input())
    
    queue = [i for i in range(1,10)]
    while True:
        if n == 1:
            print(queue[0])
            return
        tmp = queue.pop(0)
        n -= 1
        if tmp%10 == 0:
            queue += [tmp*10 + tmp%10, tmp*10 + tmp%10 + 1]
        elif tmp%10 == 9:
            queue += [tmp*10 + tmp%10 - 1, tmp*10 + tmp%10]
        else:
            queue += [tmp*10 + tmp%10 - 1, tmp*10 + tmp%10, tmp*10 + tmp%10 + 1]
            
main()

### FIXED CODE ###

"""1, 2, 3, 4, 5, 6, 7, 8, 9, 
10, 11, 12, 21, 22, 23, 32, 33, 34, 43, 44, 45, 54, 55, 56, 65, 66, 67, 76, 77, 78, 87, 88, 89, 98, 99, 
100, 101, 110, 111, 112, 121, 122, 123, 210, 211, 212, 221, 222, 223, 232, 233, 234, 321, 322, 323, 33

1 -> 10,11,12 -> 100,101 ,110,111,112, 121,122,123

2 -> 21,22,23 -> 210,211,212, 221,222,223, 232,233,234"""
def main():
    n = int(input())
    
    queue = [i for i in range(1,10)]
    if n < 10:
        print(queue[n-1])
        return
    n -= 9
    while True:
        if n <= 0:
            print(queue[n-1])
            return
        tmp = queue.pop(0)
        if tmp%10 == 0:
            queue += [tmp*10 + tmp%10, tmp*10 + tmp%10 + 1]
            n -= 2
        elif tmp%10 == 9:
            queue += [tmp*10 + tmp%10 - 1, tmp*10 + tmp%10]
            n -= 2
        else:
            queue += [tmp*10 + tmp%10 - 1, tmp*10 + tmp%10, tmp*10 + tmp%10 + 1]
            n -= 3

main()
### BUGGY CODE ###

n = int(input())
a = []
ans = []

for i in range(n):
    a.append(int(input()))
    if a[i] in ans:
        ans.remove(a[i])
    else:
        ans.append(a[i])
print(len(ans))

### FIXED CODE ###

n = int(input())
ans = set() 

for i in range(n):
    a = int(input())
    if a in ans:
        ans.remove(a)
    else:
        ans.add(a)
print(len(ans))
### BUGGY CODE ###

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

ans = 0
for a in set(A):
    count = A.count(a)
    if count > a:
        ans += count - a
    elif count < a:
        ans += count

print(ans)



### FIXED CODE ###

import collections

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

c = collections.Counter(a)

ans = 0
for i, m in c.items():
    if m < i:
        ans += m
    else:
        ans += m - i
print(ans)
### BUGGY CODE ###

k,s=map(int,input().split())
ans=0
for i in range(k+1):
    for j in range(k+1):
        for l in range(k+1):
            if (i+j+l)==s:
                ans+=1
print(ans)

### FIXED CODE ###

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

t = 0

for i in range(K + 1):
    for j in range(K + 1):
        if 0 <= S - i - j <= K:
            t += 1

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

N, K = map(int, input().split())
*h, = map(int, input().split())
dp = [float("inf")] * N
dp[0] = 0
for i in range(1, N):
    for j in range(max(0, i-K), i):
        a = dp[j] + abs(h[i] - h[j])
        dp[i] = min(dp[i], a)
print(dp[-1])

### FIXED CODE ###

import sys
input = sys.stdin.readline
N, K = map(int, input().rstrip().split())
*h, = map(int, input().rstrip().split())
dp = [0] + [float('inf')]*(N-1)
for j in range(1,N):
    for i in range(max(0,j-K),j):
        dp[j] = min(dp[j],dp[i] + abs(h[j]-h[i]))
        # print("j -> {} || i -> {} || dp -> {} || h[j] -> {} || h[i] -> {}".format(j, i, dp, h[j], h[i]))
print(dp[-1])
### BUGGY CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))
inf = 10**9
dp = [inf] * N
dp[0] = 0


def chmin(num: int, sbn: int):
    dp[num + sbn] = min((dp[num + sbn], dp[num] + abs(h[i + sbn] - h[num])))


for i in range(N):
    for sbn in range(K):
        try:
            chmin(i, sbn + 1)
        except IndexError:
            break
print(dp[-1])


### FIXED CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))
inf = 10**9
dp = [inf] * N
dp[0] = 0


def chmin(num: int, sbn: int):
    dp[num + sbn] = min((dp[num + sbn], dp[num] + abs(h[i + sbn] - h[num])))


for i in range(N):
    for sbn in range(K):
        try:
            chmin(i, sbn + 1)
        except IndexError:
            break
print(dp[-1])
### BUGGY CODE ###

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

### FIXED CODE ###

N = int(input())
sum = 1
keta = 0

numbers = input().split()
if not ("0" in numbers):
    for num in numbers:
        keta += len(num) - 1
        if keta > 19:
            print(-1)
            exit()
        sum *= int(num)
        if len(str(sum)) > 19:
            print(-1)
            exit()
        
    if len(str(sum)) == 19:
        if str(sum).count("1") == 1 and str(sum).count("0") == 18:
            pass
        else:
            print(-1)
            exit()
else:
    print(0)
    exit()
print(sum)
### BUGGY CODE ###

from scipy.sparse.csgraph import floyd_warshall

n=int(input())
arr=[list(map(int,input().split())) for _ in range(n)]
edge=[]
for i in range(n):
  for j in range(n):
    if i>=j:
      continue
    edge.append((arr[i][j],(i,j)))
edge=sorted(edge,key=lambda x:x[0])
g=[[float('inf')]*n for _ in range(n)]
for i in range(n):
  for j in range(n):
    g[i][j]=arr[i][j]
d=floyd_warshall(g)
ans=0
for w,(a,b) in edge:
  if d[a][b]<w:
    print(-1)
    break
  else:
    tmp=10**10
    for k in range(n):
      if k==a or k==b:
        continue
      tmp=min(tmp,d[a][k]+d[k][b])
    if w==tmp:
      continue
    else:
      ans+=w
else:
  print(ans)

### FIXED CODE ###

def Warshall_Floyd(edges,N):
  for k in range(N):
    for i in range(N):
      for j in range(N):
        edges[i][j]=min(edges[i][j],edges[i][k]+edges[k][j])
  return edges

n=int(input())
arr=[list(map(int,input().split())) for _ in range(n)]
edge=[]
for i in range(n):
  for j in range(n):
    if i>=j:
      continue
    edge.append((arr[i][j],(i,j)))
edge=sorted(edge,key=lambda x:x[0])
g=[[float('inf')]*n for _ in range(n)]
for i in range(n):
  for j in range(n):
    g[i][j]=arr[i][j]
d=Warshall_Floyd(g,n)
ans=0
for w,(a,b) in edge:
  if d[a][b]<w:
    print(-1)
    break
  else:
    tmp=10**10
    for k in range(n):
      if k==a or k==b:
        continue
      tmp=min(tmp,d[a][k]+d[k][b])
    if w==tmp:
      continue
    else:
      ans+=w
else:
  print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
p_list = list(map(int, input().split()))

max_scope_list = []
for p_i in range(len(p_list)):

    now_scope_list = []
    for i in range(k):
        if len(p_list) <= (p_i + i):
            break
        now_scope_list.append(p_list[p_i + i])

    if sum(max_scope_list) < sum(now_scope_list):
        max_scope_list = now_scope_list

sum_expected_value = 0
for scope in max_scope_list:
    expected_value = 0
    for num in range(1, scope+1):
        expected_value += num*1/scope
    sum_expected_value += expected_value
print(sum_expected_value)


### FIXED CODE ###

n, k = map(int, input().split())
p_list = list(map(int, input().split()))

scope_index = 0
max_sum = 0
for i in range(k):
    max_sum += p_list[i]

now_sum = max_sum
for p_i in range(k, len(p_list)):
    now_sum -= p_list[p_i - k]
    now_sum += p_list[p_i]

    if max_sum < now_sum:
        scope_index = p_i
        max_sum = now_sum

ex = (max_sum+k)/2
print(ex)
### BUGGY CODE ###

from collections import deque
N,M = list(map(int, input().split()))
ab = deque([])
for _ in range(M):
  A= list(map(int, input().split()))
  ab.append(A)

ans = [0]*(N+1)
done = [0]*(N+1)
done[0]=1
done[1]=1

stack = deque([1])

while stack:
  x = stack.pop()
  temp = deque([])
  for i in range(len(ab)):
    c = ab.pop()
    if x in c:
      if c[0] == x:
        if done[c[1]] == 0:
          done[c[1]]+=1
          stack.appendleft(c[1])
          ans[c[1]] = x
      else:
        if done[c[0]] == 0:
          done[c[0]] +=1
          stack.appendleft(c[0])
          ans[c[0]] = x
    else:
      temp.append(c)  
  ab = temp

print('Yes')
for i in range(2,len(ans)):
  print(ans[i])




### FIXED CODE ###

from collections import deque
N,M = list(map(int, input().split()))
ab = deque([[] for i in range(N+1)])
for _ in range(M):
  A= list(map(int, input().split()))
  ab[A[0]].append(A[1])
  ab[A[1]].append(A[0])

ans = [0]*(N+1)
done = [0]*(N+1)
done[0]=1
done[1]=1

stack = deque([1])

while stack:
  x = stack.pop()
  temp = deque([])
  for i in ab[x]:
    if done[i] == 0:
      done[i] += 1
      ans[i] = x
      stack.appendleft(i)

print('Yes')
for i in range(2,len(ans)):
  print(ans[i])
### BUGGY CODE ###

N, K = map(int, input().split())
people = list(input())
lst = []
count = 0
flag = people[0]
for i in range(len(people)):
	if i == len(people) - 1:
		lst.append(count + 1) if flag == '1' else lst.append(count * -1 - 1)
	elif people[i] == flag and people[i+1] != flag:
		lst.append(count + 1) if flag == '1' else lst.append(count * -1 - 1)
		count = 0
		flag = people[i + 1]
	else:
		count += 1

maximum = 0
l = len(lst)
for i in range(l):
	if lst[i] < 0:
		end = i+2*K
		if i != 0:
			temp = list(map(abs, lst[i-1:end]))
		else:
			temp = list(map(abs, lst[i:end]))
		maximum = max(maximum, sum(temp))
		if end > l:
			break
	else:
		end = 2*K+1
		temp = list(map(abs, lst[i:end]))
		maximum = max(maximum, sum(temp))
		if end > l:
			break
print(maximum)


### FIXED CODE ###

N, K = map(int, input().split())
people = list(input())
lst = []
count = 0
flag = people[0]
if flag == '1':
	lst.append(0)
for i in range(len(people)):
	if i == len(people) - 1:
		lst.append(count + 1)
	elif people[i] == flag and people[i+1] != flag:
		lst.append(count + 1)
		count = 0
		flag = people[i + 1]
	else:
		count += 1

maximum = 0
l = len(lst)
temp = sum(lst[0:2*K])
maximum = max(maximum, temp)
for i in range(2, l, 2):
	end = i+2*K
	temp = temp - lst[i-2] + sum(lst[end-2:end])
	if i != 2:
		temp -= lst[i-3]
	maximum = max(maximum, temp)

print(maximum)
### BUGGY CODE ###

X = int(input())
for A in range(-5000, 5000):
    for B in range(-5000, 5000):
        if A**5 - B**5 == X:
            print(A, B)
            break
    else:
        continue
    break

### FIXED CODE ###

X = int(input())
for A in range(-200, 200):
    for B in range(-200, 200):
        if A**5 - B**5 == X:
            print(A, B)
            break
    else:
        continue
    break
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
result = 1
for i in range(N):
	result = result*A[i]

if result>10**18:
	result = -1
print(result)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
result = 1
if 0 in A:
	result = 0
else:
	for i in range(N):
		result = result*A[i]

		if result>10**18:
			result = -1
			break
print(result)
### BUGGY CODE ###

import numpy as np

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

result=0
dic={}

for i in range(1,a[-1]+1):
  dic[i]=np.count_nonzero(a<=i)

#print(dic)
  
for i in range(n-2):
  for j in range(i+1,n-1):
    if a[i]+a[j]>a[j+1]:
      temp=a[i]+a[j]
      result+=max(0,dic[min(a[-1],temp-1)]-dic[a[j]])
      #print(a[i],a[j],a[j+1:],result)

print(result)

### FIXED CODE ###

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

l.sort()
l.append(10**9)
cnt=0
i=0
#print(l)

while i<n-2:
    j=i+1
    while j<n-1:
        LL=j+1
        RR=n-1
        #print("#",l[i],l[j],l[LL],l[RR])
        while LL<=RR:
            k=(LL+RR)//2
            if k==n:
                break
            #print(l)
            #print(i,j,LL,RR,k)
            #print(l[i]+l[j],l[k],l[k+1])
            if l[i]+l[j]>l[k] and l[i]+l[j]<=l[k+1]:
                cnt+=k-j
                break
            elif LL==RR:
                break
            elif l[i]+l[j]<=l[k]:
                RR=k
            elif l[i]+l[j]>l[k]:
                LL=k+1
            elif l[i]+l[j]<l[k] and k==j+1:
                break
        j+=1
    i+=1

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

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

f = 1
while True:
    if a == 0:
        print("No")
        break
    elif c == 0:
        print("Yes")
        break
    if f:
        c -= b
        f = 0
    else:
        a -= d
        f = 1
    


### FIXED CODE ###

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

ans_1 = math.ceil(c / b)
ans_2 = math.ceil(a / d)

#print(ans_1,ans_2)
if ans_1 > ans_2:
    print("No")
else:
    print("Yes")
### BUGGY CODE ###

n = int(input())
al = []
count = 0
for i in range(n):
  a = input()
  if a in al:
      pass
  else:
    count += 1
    al.append(a)
print(count)

### FIXED CODE ###

s = set(open(0))
print(len(s)-1)
### BUGGY CODE ###

import numpy as np

N = int(input())
D = list(map(int, input().split()))
if N > 24:
    print(0)
    exit()

# 深さ優先探索で全通りを探索できるのでは curは０からスタート
def dfs(cur, times):
    global answer
    if cur == N:
        times.sort()
        arr = np.array(times)
        result = (arr[1:] - arr[:-1]).min()
        if result > answer:
            answer = result
    else:
        x = D[cur]
        dfs(cur+1, times + [x])
        dfs(cur+1, times + [24-x])

answer = 0
dfs(0, [0, 24])
print(answer)

### FIXED CODE ###

import numpy as np

N = int(input())
D = list(map(int, input().split()))
if N > 23:
    print(0)
    exit()
for i in range(13):
    if D.count(i) >= 3:
        print(0)
        exit()
    elif D.count(i) == 2 and D.count(i+1) == 2:
        print(1)
        exit()

# 深さ優先探索で全通りを探索できるのでは curは０からスタート
def dfs(cur, times):
    global answer
    if cur == N:
        times.sort()
        arr = np.array(times)
        result = (arr[1:] - arr[:-1]).min()
        if result > answer:
            answer = result
    else:
        x = D[cur]
        dfs(cur+1, times + [x])
        dfs(cur+1, times + [24-x])

answer = 0
dfs(0, [0, 24])
print(answer)
### BUGGY CODE ###

H,W = map(int,input().split())
S = []
for i in range(H):
    s = input()
    S.append([x for x in s])
 
S_h = [[] for i in range(H)]
S_w = [[] for i in range(W)]
S_hh = [[0]*(W+1) for i in range(H)]
S_ww = [[0]*(H+1) for i in range(W)]
 
for x in range(W):
    for y in range(H):
        if S[y][x] == '#':
            S_h[y].append(x)
            S_w[x].append(y)
            S_hh[y][x] = 1
            S_ww[x][y] = 1
        S_hh[y][x] += S_hh[y][x-1]
        S_ww[x][y] += S_ww[x][y-1]
 
ans = 0
for x in range(W):
    for y in range(H):
        if S[y][x] == '.':
            c = 1
            if len(S_w[x]) == 0:
                c += H-1
            else:
                i = S_ww[x][y]
                if i == 0:
                    c += S_w[x][0]-1
                elif i == len(S_w[x]):
                    c += H-S_w[x][-1]-2
                else:
                    c += S_w[x][i]-S_w[x][i-1]-2
            if len(S_h[y]) == 0:
                c += W-1
            else:
                i = S_hh[y][x]
                if i == 0:
                    c += S_h[y][0]-1
                elif i == len(S_h[y]):
                    c += W-S_h[y][-1]-2
                else:
                    c += S_h[y][i]-S_h[y][i-1]-2
            ans = max(ans,c)
 
print(ans)

### FIXED CODE ###

H,W = map(int,input().split())
S = [input() for i in range(H)]

S_h1 = [[0]*(W+1) for i in range(H)]
S_w1 = [[0]*(H+1) for i in range(W)]
S_h2 = [[0]*(W+1) for i in range(H)]
S_w2 = [[0]*(H+1) for i in range(W)]

for x in range(W):
    for y in range(H):
        if S[y][x] == '#':
            S_h1[y][x] = 0
            S_w1[x][y] = 0
        else:
            S_h1[y][x] += S_h1[y][x-1]+1
            S_w1[x][y] += S_w1[x][y-1]+1

for x in range(W-1,-1,-1):
    for y in range(H-1,-1,-1):
        if S[y][x] == '#':
            S_h2[y][x] = 0
            S_w2[x][y] = 0
        else:
            S_h2[y][x] += S_h2[y][x+1]+1
            S_w2[x][y] += S_w2[x][y+1]+1

ans = 0
for x in range(W):
    for y in range(H):
        if S[y][x] == '.':
            ans = max(ans,S_h1[y][x]+S_h2[y][x]+S_w1[x][y]+S_w2[x][y]-3)
 
print(ans)
### BUGGY CODE ###



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

nums = {}
for a in arr:
    if a not in nums:
        nums[a] = 1
    else:
        nums[a] += 1

# def factorize(N):
#     up = int(np.sqrt(N))+2
#     out = {}
#
#     for i in range(2,up):
#         if N%i == 0:
#             temp = N
#             count = 0
#             while(True):
#                 N = N//i
#                 count += 1
#                 if N%i != 0:
#                     break
#             out[i] = count
#         else:
#             continue
#     if N != 1:
#         out[N] = 1
#     return out

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)

    # divisors.sort()
    return divisors

# print(nums)
ans = 0
for i in range(n):
    f = make_divisors(arr[i])
    # print(f)
    cnt = 0
    for key in f:
        if key == arr[i]:
            if key in nums and nums[key] > 1:
                cnt += 1
        else:
            if key in nums:
                cnt += 1

    if cnt == 0:
        ans += 1

print(ans)


### FIXED CODE ###

n = int(input())
arr = list(map(int,input().split()))
arr.sort()

cnt = {}
kouho = []
erat = [True for i in range(10**6+1)]

for i in range(n):
    if arr[i] not in cnt:
        cnt[arr[i]] = 1
    else:
        cnt[arr[i]] += 1
    if erat[arr[i]]:
        kouho.append(arr[i])
        tp = arr[i]
        while True:
            erat[tp] = False
            tp += arr[i]
            if tp > 10**6:
                break
# print(kouho)
ans = 0
for k in kouho:
    if cnt[k] == 1:
        ans += 1


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

import itertools
n = int(input())
s = input()
S = list(itertools.combinations(s, 3))
ss = set(S)
ls = len(ss)

print(ls)

### FIXED CODE ###

n=int(input())
s=list(input())
cnt=0
for i in range (10):
  i=str(i)
  for j in range (10):
    j=str(j)
    for k in range (10):
      k=str(k)
      if s.count(i)!=0:
        a=s.index(i)
        x=s[(a+1):]
        if x.count(j)!=0:
          b=x.index(j)
          y=x[(b+1):]
          if y.count(k)!=0:
            cnt+=1
 
print(cnt)
### BUGGY CODE ###

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

sys.setrecursionlimit(10**7)
inf = 10**20
gosa = 1.0 / 10**10
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 main():
    a = [ord(c) - 97 for c in S()]
    l = len(a)
    r = []
    t = [0] * l
    s = set()
    u = [[] for _ in range(26)]
    k = 1
    for i in range(l-1,-1,-1):
        c = a[i]
        u[c].append(i)
        s.add(c)
        t[i] = k
        if len(s) == 26:
            k += 1
            s = set()
    t.append(1)
    for i in range(26):
        u[i].reverse()

    def bs(i,c):
        t = u[c]
        if not t or t[-1] <= i:
            return -1
        ma = len(t) - 1
        mi = 0
        mm = (ma+mi) // 2
        while ma > mi:
            mm = (ma+mi) // 2
            if t[mm] > i:
                ma = mm
            else:
                mi = mm + 1
        return t[mm]

    j = -1
    while j < l:
        for c in range(26):
            bi = bs(j,c)
            if bi < 0:
                r.append(c)
                j = l
                break
            if t[bi] < k:
                r.append(c)
                k = t[bi]
                j = bi
                break

    return ''.join([chr(c+97) for c in r])

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
gosa = 1.0 / 10**10
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 main():
    a = S()
    l = len(a)
    t = {}
    for c in string.ascii_lowercase:
        t[c] = l
    b = [(1,0,0) for _ in range(l)]
    b.append((1,'a',l))
    b.append((0,'',l+1))

    for c,i in reversed(list(zip(a,range(l)))):
        t[c] = i
        b[i] = min([(b[t[d]+1][0] + 1,d,t[d]+1) for d in string.ascii_lowercase])

    r = ''
    i = 0
    while i < l:
        r += b[i][1]
        i = b[i][2]
    return r

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

X, K, D = map(int, input().split())

for i in range(K):
    if abs(X + D) < abs(X - D):
        X = X + D
    else:
        X = X - D

print(abs(X))


### FIXED CODE ###

from sys import setrecursionlimit

setrecursionlimit(10 ** 8)


def main(x, k, d):
    for i in range(k):
        if abs(x + d) < abs(x - d):
            x = x + d
        else:
            x = x - d

        if abs(x - d) > abs(x) and abs(x + d) > abs(x):
            if (k - i - 1) % 2 == 1:
                if abs(x - d) < abs(x + d):
                    x = x - d
                else:
                    x = x + d
            break

    print(abs(x))


def sub(x, k, d):
    print(abs(x) - d * k)


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

if abs(a) - b * c >= 0:
    sub(a, b, c)
else:
    main(a, b, c)
### BUGGY CODE ###

S = input()

ls =[0 for i in range(2019)]
ls[0] += 1
p_amari = 0
kake = 1
for i in range(len(S)) :
	p_amari = ( int(S[len(S)-1-i]) * kake + p_amari ) % 2019
	ls[p_amari] += 1
	kake *= 10
ret = 0
for i in range(2019) :
	n = ls[i]
	if n == 0 :
		continue
	ret += n * (n -1 ) / 2
print(int(ret))

### FIXED CODE ###

S = input()

ls =[0 for i in range(2019)]
ls[0] += 1
p_amari = 0
ret = 0
len_s = len(S)
for i in range(len_s) :
	p_amari = ( int(S[len_s-1-i]) * pow(10, i, 2019) + p_amari ) % 2019
	ret += ls[p_amari]
	ls[p_amari] += 1
print(int(ret))
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))
min_abs = 1000000000000000000000000
for i in range(1, n):
  abs_val = abs(sum(A[:i]) - sum(A[i:]))
  min_abs = min(min_abs, abs_val)
print(min_abs)

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
min_abs = 1000000000000000000000000
for i in range(1, n):
  A[i] += A[i-1]

for i in range(0, n-1):
  abs_val = abs(A[-1] - (A[i] * 2))
  min_abs = min(min_abs, abs_val)
print(min_abs)