Harryxun/stf_run huggingface dataset:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    N = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    res = 0
    n = 0
    for i in range(N):
        if a[i]<b[i]+n:
            res += a[i]
        else:
            res += b[i]+n
        if a[i]-n>0:
            c = a[i]-n
        else:
            c = 0
        if b[i]-c>0:
            n = b[i]-c
        else:
            b = 0
    res += min(n, a[-1])
    print(res)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    N = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    res = 0
    n = 0
    for i in range(N):
        res += min(a[i], b[i]+n)
        c = max(a[i]-n, 0)
        n = max(b[i]-c, 0)
    res += min(n, a[-1])
    print(res)

if __name__ == '__main__':
    main()
s = input()
k = int(input())
ans = set()
r = len(s)
if r <= 50:
    for i in range(r):
        for j in range(r):
            ans.add(s[i:r-j])
    print(sorted(list(ans))[k])
else:
    print('Pass')

### FIXED CODE ###

s = input()
k = int(input())
ans = set()
r = len(s)

if r == 1:
    print(s)
else:
    for i in range(r):
        for j in range(k):
            ans.add(s[i:i+j+1])
    print(sorted(list(ans))[k-1])
import sys
from functools import reduce
def a():
    p = [[int(t) for t in r.split(' ')] for r in sys.stdin.read().split('\n') if r != '']
    A, P = p[0]
    print(int((A*3+P)/2)
a()


### FIXED CODE ###

import sys
def a():
    p = [[int(t) for t in r.split(' ')] for r in sys.stdin.read().split('\n') if r != '']
    A, P = p[0]
    print(int((A*3+P)/2))
a()
n = int(input())
s = []
ans = []
for i in range(n):
  s.append(input())
s = sorted(s)
max_count = 1
count = 1
for i in range(n):
  if s[i] == s[i+1]:
    count += 1
    if count == max_count:
      ans.append(s[i])
    if count > max_count:
      max_count = count
      ans = [s[i]]
  else:
    count = 1
ans = sorted(ans)
for i in range(len(ans)):
  print(ans[i]) 

### FIXED CODE ###

n = int(input())
s = []
for i in range(n):
  s.append(input())
s = sorted(s)
max_count = 1
count = 1
ans = []
for i in range(n-1):
  if s[i] == s[i+1]:
    count += 1
    if count == max_count:
      ans.append(s[i])
    if count > max_count:
      max_count = count
      ans = [s[i]]
  else:
    count = 1
    if max_count == 1:
      ans.append(s[i])
if max_count == 1:
  ans.append(s[n-1])
ans = sorted(ans)
for i in range(len(ans)):
  print(ans[i])
# -*- coding: utf-8 -*-
p,q,r=map(int,input().split())
ptint(min(p+q,q+r,r+p)

### FIXED CODE ###

# -*- coding: utf-8 -*-
p,q,r=map(int,input().split())
print(min(p+q,q+r,r+p))
def gcd(a,b):
    if b > a:
        a, b = b, a
    while b:
        a, b = b, a%b
    return a

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

for i in range(N-1):
    A = gcd(T[i],T[i+1])
    LIS.append(A)
F = LIS.index(min(LIS))
if F == 0:
    T.pop(F)
else:
    T.pop(F+1)
LIS = []
for i in range(N-2):
    A = gcd(T[i],T[i+1])
    LIS.append(A)
print(min(LIS))

### FIXED CODE ###

import copy 

def gcd(a,b):
    if b > a:
        a, b = b, a
    while b:
        a, b = b, a%b
    return a

N = int(input())
T = list(map(int,input().split()))
T.sort()
LIS = [0]*N
LIS[0] += T[0]
for i in range(N-1):
    LIS[i+1] += gcd(LIS[i],T[i+1])
F = LIS.index(min(LIS))
if len(T) == 2:
    ANS = max(T[0],T[1])
elif F == 0:
    U = copy.copy(T)
    V = copy.copy(T)
    U.pop(1)
    V.pop(0)
    LU = [0]*(N-1)
    LU[0] = U[0]
    LV = [0]*(N-1)
    LV[0] = V[0]
    for i in range(N-2):
        LU[i+1] += gcd(LU[i],U[i+1])
    ANSU = LU[N-2]
    for i in range(N-2):
        LV[i+1] += gcd(LV[i],V[i+1])
    ANSV = LV[N-2]
    ANS = max(ANSU,ANSV)
    
else:
    U = copy.copy(T)
    V = copy.copy(T)
    U.pop(F)
    V.pop(0)
    LU = [0]*(N-1)
    LU[0] = U[0]
    LV = [0]*(N-1)
    LV[0] = V[0]
    ANSU = 0
    ANSV = 0
    for i in range(N-2):
        LU[i+1] += gcd(LU[i],U[i+1])
    ANSU = LU[N-2]
    for i in range(N-2):
        LV[i+1] += gcd(LV[i],V[i+1])
    ANSV = LV[N-2]
    ANSP = max(ANSU,ANSV)
    ANS = max(ANSP,LIS[N-1])
        
print(ANS)
a,b,c,d = map(int,input().split())

if a*c > b*d:
    print(a*c)
elif b > 0 and d > 0:
    print(b*d)
elif a < 0 and c < 0:
    print(a*c)
else:
    x = min(abs(a),abs(b))
    y = min(abs(c),abs(d))
    print(-x*y)

### FIXED CODE ###

x = int(input())

if x == 0:
    print(1)
else:
    print(0)
n = int(input())
r = 1
w = 10**9 + 7
for i in range(n):
  r = (r * i) % x
  
print(r)

### FIXED CODE ###

n = int(input())
r = 1
w = 10**9 + 7
for i in range(1, n+1):    
  r *= i
  r = (r % w)
  
  
  
print(r)
n=int(input)
s=input()
d=list(s)
cnt=0
for i in range(n-1):
  if s[i] == s[i+1]:
    cnt+=1
  else:
    continue
    
print(n-cnt)


### FIXED CODE ###

n=int(input())
s=input()
d=list(s)
cnt=0
for i in range(n-1):
  if s[i] != s[i+1]:
    cnt+=1
print(1+cnt)
n=input()
if 9 in n:
    print("Yes")
elif:
    print("No")

### FIXED CODE ###

n=input()
if "9" in n:
    print("Yes")
else:
    print("No")
import heapq
L,R = map(int, input().split())
if R - L >= 672:
    print(0)
    exit()
else:
    hq3 = []
    hq673 = []
    hq2019 = []
    for i in range(L, R+1):
        heapq.heappush(hq2019, i%2019)
        heapq.heappush(hq673, i%673)
        heapq.heappush(hq3, i%3)
    a = heapq.heappop(hq2019)
    b = heapq.heappop(hq673)
    c = heapq.heappop(hq3)
    if a == 0:
        print(0)
        exit()
    elif b == 0 and c == 0:
        print(0)
        exit()
    else:
        print(heapq.heappop(hq) * a % 2019)

### FIXED CODE ###

L,R = map(int, input().split())
if R - L >= 2018:
    print(0)
    exit()
else:
    ans = 2019**2
    for i in range(L, R):
        for j in range(i+1, R+1):
            #i %= 2019
            #j %= 2019
            k = (i*j) % 2019
            ans = min(ans, k)
    print(ans)
A,B = map(int, input())
if A <= 5:
  print(0)
elif A <= 12:
  print(B/2)
else:
  print(B)

### FIXED CODE ###

A,B = map(int, input().split())
if A <= 5:
  print(0)
elif A <= 12:
  print(B//2)
else:
  print(B)
l=list(map(int,input().split()))
l="".join([int(n) for n in l])

if l % 4 == 0:
  print("YES")
else:
  print("NO")

### FIXED CODE ###

r,g,b=map(int,input().split())
ans=100*r+10*g+b

if ans % 4 == 0:
  print("YES")
else:
  print("NO")
n, k = map(int, input().split())
a = list(map(int, input().split()))

d = [float("inf")] * n
d[0] = 0

for i in range(1, len(a)):
    s = max(i-k, 0)
    now = a[i]
    d[i] = min(y + abs(now-x) for x, y in zip(a[s:i], d[s:i]))
print(d[-1])  

### FIXED CODE ###

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

d = [0] * n
d[1] = abs(a[0]-a[1])

for i in range(2, len(a)):
    d[i] = min(d[i-1]+abs(a[i]-a[i-1]), d[i-2]+abs(a[i]-a[i-2]))
print(d[-1])
n,x = list(map(int,input().split()))

l = [int(s) for s in input().split()]
d = 0
i = 1
d = [0] * (n+1)
count = 0
if n == 1 and x >= l[0]:
    print(1)
elif n == 1 and x < l[0] :
    print(0)
else:

    while True:
        
        
        d[i] = d[i-1] + l[i-1]
        count += 1
        
        if d[i] > x:
            break
        
        i += 1
        if i > n:
            print(count)

    print(count)


### FIXED CODE ###

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

l = [int(s) for s in input().split()]
d = 0
i = 1
d = [0] * (n+1)
count = 0
if n == 1 and x >= l[0]:
    print(1)
elif n == 1 and x < l[0] :
    print(0)
else:

    while True:
        
        
        d[i] = d[i-1] + l[i-1]
        count += 1
        
        if d[i] > x:
            break
        
        i += 1
        if i > n:
            print(count+1)
            exit()

    print(count)
n, m = map(int, input().split())
a = sorted(list(map(int, input().split())))
bc = [list(map(int, input().split())) for i in range(m)]
sort_bc = sorted(bc, key = lambda x:x[1], reverse = True)
cnt_a = 0
cnt_m = 0
while (cnt_a <= (len(a) - 1)) and (cnt_m <= (m - 1)):
    i = sort_bc[cnt_m]
    cnt_m += 1
    for j in range(i[0]):
        if i[1] > a[cnt_a]:
            a[cnt_a] = i[1]
            cnt_a += 1
        else:
            break
print(sum(a))

### FIXED CODE ###

n, m = map(int, input().split())
a = sorted(list(map(int, input().split())))
bc = [list(map(int, input().split())) for i in range(m)]
sort_bc = sorted(bc, key = lambda x:x[1], reverse = True)
cnt_a = 0
cnt_m = 0
for i in sort_bc:
    if cnt_a <= n - 1:
        for j in range(i[0]):
            if cnt_a <= n - 1:
                if i[1] > a[cnt_a]:
                    a[cnt_a] = i[1]
                    cnt_a += 1
                else:
                    break
    else:
        break
print(sum(a))
import sys

# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
import heapq
import decimal
# import statistics
import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n, x = ns()
    lim = 51
    total = [int(0) for _ in range(lim)]
    P_total = [int(0) for _ in range(lim)]

    total[0] = 1
    for i in range(1, lim):
        total[i] = total[i - 1] * 2 + 3

    P_total[0] = 1
    for i in range(1, lim):
        P_total[i] = P_total[i - 1] * 2 + 1

    ans = 0
    base = 1
    L = n
    while base != x:
        if base + total[L] // 2 <= x:
            base += total[L] // 2 + 1
            ans += P_total[L - 1] + 1
            L -= 1
        else:
            base += 1
            L -= 1
            if L == 0:
                ans += 1

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
import heapq
import decimal
# import statistics
import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n, x = ns()
    lim = 51
    total = [int(0) for _ in range(lim)]
    P_total = [int(0) for _ in range(lim)]

    total[0] = 1
    for i in range(1, lim):
        total[i] = total[i - 1] * 2 + 3

    P_total[0] = 1
    for i in range(1, lim):
        P_total[i] = P_total[i - 1] * 2 + 1

    ans = 0
    base = 1
    L = n
    flg = True
    while base != x and L != 0:
        if base + total[L] // 2 <= x and flg:
            base += total[L] // 2
            ans += P_total[L - 1] + 1
            flg = False
        else:
            flg = True
            base += 1
            L -= 1
            if L == 0:
                ans += 1

    print(ans)


if __name__ == '__main__':
    main()
N, K = map(int, input().split())
h = [0] * (2*N)
h[:N] = list(map(int, input().split()))
INF = 10**9
dp = [INF] * (2*N)
dp[0] = 0
for i in range(N):
    for k in range(1, K+1):
        dp[i+k] = min(dp[i+k], dp[i]+abs(h[i] - h[i+k]))
print(dp[N-1])

### FIXED CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))
INF = 10**9
dp = [INF] * N
dp[0] = 0
for i in range(N):
    for k in range(1, K+1):
        if i + k < N:
            dp[i+k] = min(dp[i+k], dp[i]+abs(h[i] - h[i+k]))
print(dp[N-1])
v=list(map(int, input().split()))
c=list(map(int, input().split()))
n=int(input())
s=0
for i in range(n):
  if v[i]-c[i]>0:
    s=s+v[i]-c[i]
  else:
    continue
print(s)

### FIXED CODE ###

n = int(input())
v = list(map(int, input().split()))
c = list(map(int, input().split()))

s = 0
for i in range(n):
  if v[i] - c[i] >= 0:
    s += v[i] - c[i]
  else:
    continue
print(s)
n,k,c=map(int, input().split())
s=input()
L=[]
R=[]
m=0
for i in range(k):
    while s[m]=="x":
        m+=1
    if s[m]=="o":
        L.append(m)
        m+=c
    m+=1
m=0
for i in range(k):
    while s[m]=="x":
        m+=1
    if s[n-m-1]=="o":
        R.insert(0,n-m-1)
        m+=c
    m+=1
for i in range(k):
    if R[i]==L[i]:
        print(R[i]+1)

### FIXED CODE ###

n,k,c=map(int, input().split())
s=input()
L=[0]*k
R=[0]*k
m=0
l=0
for i in range(k):
    while s[m]=="x":
        m+=1
    L[i]=m
    m+=c+1
    while s[n-l-1]=="x":
        l+=1
    R[i]=n-l-1
    l+=c+1
for i in range(k):
    if R[k-i-1]==L[i]:
        print(L[i]+1)
def main():
    n = int(input())
    abc = 'abcdefghijklmnopqrstuvwxyz'

    length = 1
    accumulation = 0
    while True:
        if n <= 26 ** length + accumulation:
            break
        else:
            accumulation += 26 ** length
            length += 1


    if length == 1:
        answer = abc[n - 1]

    else:
        lst = []
        for _ in range(length - 1):
             tmp = n // (26 ** (length - 1))
             lst.append(tmp)
             n -= (26 ** (length - 1) * tmp)
             length -= 1

        lst.append(n)

        answer = ''
        for i in range(len(lst)):
            number = lst[i]
            answer += abc[number - 1]


    print(answer)



if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n = int(input())
    alp = 'abcdefghijklmnopqrstuvwxyz'
    answer = ''

    while n >= 1:
        n -= 1
        answer += alp[n % 26]
        n //= 26

    real_answer = ''
    for i in range(1, len(answer) + 1):
        real_answer += answer[-i]

    print(real_answer)


if __name__ == '__main__':
    main()
k = int(input())
i = 1
a = 7
if k % 2 == 0:
  print("-1")
  return
while a % k != 0:
  i += 1
  a = 10*a + 7
  if i == 10**9+7:
    i = -1
    break

print(i)
  


### FIXED CODE ###

k = int(input())
i = 1
a = 7
a = a % k
while a != 0:
  i += 1
  a = (10*a + 7) % k
  if i == 10**6:
    i = -1
    break

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

if A == 0:
  print(0, max(0, B - K))
elif B == 0:
  print(max(0, A - K), 0)
elif K == 0:
  print(A, B)

A_from_0 = A
B_from_0 = B

if (A_from_0 - K) >= 0:
  A -= K
  K = 0
else:
  A = 0
  K -= A_from_0
  
if (B_from_0 - K) > 0:
  B -= K
  K = 0
else:
  B = 0
  K -= B_from_0

if K == 0:
  print(A, B)
if K == 1:
  print(0, 1)
elif K > 1:
  print(0, 0)


### FIXED CODE ###

a, b = input().split()

print(b+a)
for _ in [0]*input():
  n = input()
  A = [list(' '*n) for _ in [0]*n]
  for i in range((n+3)/4):
    i2 = i*2
    if i2>0: A[n-i2][i2]='@'
    for j in range(i2, n-i2):
      A[j][i2]='@' #左下→左上
      A[i2][j]='@' #左上→右上
      if j<n-i2-1: A[j][n-i2-1]='@' #右上→右下
      if j>i2+1: A[n-i2-1][j]='@' #右下→左下下
  for e in A: print "".join(e)
  print

### FIXED CODE ###

s="#"
for c in range(input()):
  n = input()
  A = [list(' '*n) for _ in [0]*n]
  for i in range((n+3)/4):
    i2 = i*2
    if i2>0: A[n-i2][i2]=s
    for j in range(i2, n-i2):
      A[j][i2]=s
      A[i2][j]=s
      if j<n-i2-1: A[j][n-i2-1]=s
      if j>i2+1: A[n-i2-1][j]=s
  if c: print
  for e in A: print "".join(e)
N = int(input())
T = []

for _ in range(N):
	T.append(int(input()))
	
def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)

ans = 1
	
for i in range(N):
	ret = ret * T[i] // gcd(ret, T[i])
	
print(ans)

### FIXED CODE ###

N = int(input())
T = []

for _ in range(N):
	T.append(int(input()))
	
def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)

ans = 1
	
for i in range(N):
	ans = ans * T[i] // gcd(ans, T[i])
	
print(ans)
N = int(input())
L = list(map(int, input().split()))

count = 0
for a in itertools.combinations(L, 3):
    if len(set(a)) != 3:
        continue
    a = sorted(a)
    if a[2] < a[0] + a[1]:
        count += 1
print(count)

### FIXED CODE ###

import itertools

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

count = 0
for a in itertools.combinations(L, 3):
    if len(set(a)) != 3:
        continue
    a = sorted(a)
    if a[2] < a[0] + a[1]:
        count += 1
print(count)
K, X = list(map(int, input().split()))
    minimum = max(-1000000, X - (K - 1))
    maximum = min(X + (K - 1), 1000000)
    print(' '.join(map(str, range(minimum, maximum + 1))))


### FIXED CODE ###

K, X = list(map(int, input().split()))
minimum = max(-1000000, X - (K - 1))
maximum = min(X + (K - 1), 1000000)
print(' '.join(map(str, range(minimum, maximum + 1))))
A, B = map(int, input().split())
x = A+B
y = A-B
z = A*B

if(x>y and x>z):
    print(x)

elif(y>x and y>z):
    print(y)

elif(z>x and z>y):
    print(z)

else:
    exit()
~

### FIXED CODE ###

A, B = map(int, input().split())
x = A+B
y = A-B
z = A*B

if(x>=y>=z or x>=z>=y):
    print(x)
elif(y>=x>=z or y>=z>=x):
    print(y)
else:
    print(z)
s = str(input())
print(s.count(1))

### FIXED CODE ###

s = str(input())
print(s.count("1"))
n = int(input())
l = [map(int, input().split())]

ans = 0
l.sort()

for i in range(n):
    ans += l[2*i]

print(ans)

### FIXED CODE ###

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

ans = 0
l.sort()

for i in range(n):
    ans += l[2*i]
    
print(ans)
# -*- coding: utf-8 -*-
a1 = list(map(int, input().split()))
a2 = list(map(int, input().split()))
a3 = list(map(int, input().split()))
a = [a1, a2, a3]
n = int(input())
b = []
for i in range(n):
    bn = int(input())
    b.append(bn)
for i in range(3):
    for j in range(3):
        if a[i][j] in b:
            a[i][j] = -5
for i in range(3):
    if sum(a[i]) == -15:
        bng = 1
for i in range(3):
     cnt = 0
     for j in range(3):
       cnt += a[j][i]
       if cnt == -15:
         bng = 1
        
cnt = 0
for i in range(3):
        cnt += a[i][i]
if cnt == -15:
        bng = 1 
                
if bng == 1:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

# -*- coding: utf-8 -*-
a1 = list(map(int, input().split()))
a2 = list(map(int, input().split()))
a3 = list(map(int, input().split()))
a = [a1, a2, a3]
n = int(input())
b = []
bng = 0
for i in range(n):
    bn = int(input())
    b.append(bn)
for i in range(3):
    for j in range(3):
        if a[i][j] in b:
            a[i][j] = -5
for i in range(3):
    if sum(a[i]) == -15:
        bng = 1
for i in range(3):
     cnt = 0
     for j in range(3):
       cnt += a[j][i]
       if cnt == -15:
         bng = 1
        
cnt = 0
for i in range(3):
        cnt += a[i][i]
if cnt == -15:
        bng = 1 
if a[0][2] + a[1][1] + a[2][0] == -15:
    bng = 1
                
if bng == 1:
    print("Yes")
else:
    print("No")
# 偶数かつ3または5で割り切れる

N = int(input())
a = list(map(int(input().split())))
for i in range(N):
    if a[i] % 2 == 0:
        if a[i] % 3 != 0 and a[i] % 5 != 0:
            print("DENIED")
            exit(0)
print("APPROVED")


### FIXED CODE ###

N = int(input())
a = list(map(int,input().split()))
result = "APPROVED"
for i in range(N):
    if a[i] % 2 == 0:
        if a[i] % 3 != 0 and a[i] % 5 != 0:
            result = "DENIED"
            break
print(result)
number = int(input())

if number % 4 = 0:
  print("YES")

else:
  print("NO")

### FIXED CODE ###

r, g, b = map(int, input().split())
 
number = r * 100 + g * 10 + b
 
if number % 4 == 0:
  print("YES")
else:
  print("NO")
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

n,m = map(int,input().split())
A = [int(input()) for _ in range(m)] #壊れた階段

pos = 0
count = 1
dp = [0] * (n+1)
dp[0] = 1

for i in range(N+1):
    if (i+1) in A and (i+2) in A:
        print(0)
        exit()
    if (i+1) not in A:
        dp[i+1] += dp[i]
    if (i+2) not in A:
        dp[i+2] += dp[i]

print(dp[n])

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

MOD = 10 ** 9 + 7
n,m = map(int,input().split())
A = set(int(input()) for _ in range(m)) #壊れた階段

dp = [0] * (n+1)
dp[0] = 1

for i in range(1,n+1):
    if i in A:
        continue
    x = dp[i-1]
    if i > 1:
        x += dp[i-2]
    dp[i] = x%MOD

print(dp[n])
A,B=int(input()).split()
def asf(A,B):
  same_num=(A+B)/2
  k=same_num-min(A,B)
  return k
print(asf(A,B))

### FIXED CODE ###

A,B=map(int,input().split())
def asf(A,B):
  same_num=(A+B)/2
  if same_num%1==0:
  	return int(same_num)
  else:
    return "IMPOSSIBLE"
print(asf(A,B))
N, M = map(int, input().split())
ans = [-1] * N

def find(x):
    global ans
    if ans[x] == -1:
        return x
    else:
        return find(ans[x])
    
for _ in range(M):
    x, y, z = map(int, input().split())
    x -= 1
    y -= 1
    xx = find(x)
    yy = find(y)
    if ans[x] == ans[y] == -1:
        ans[y] = x
    elif xx == yy:
        continue
    else:
        ans[yy] = xx

n = 0
for i in ans:
    if i == -1:
        n += 1

print(n)

### FIXED CODE ###

N, M = map(int, input().split())
ans = [-1] * N

def find(x):
    global ans
    if ans[x] == -1:
        return x
    else:
        ans[x] = find(ans[x])
        return ans[x]
    
for _ in range(M):
    x, y, z = map(int, input().split())
    x -= 1
    y -= 1
    xx = find(x)
    yy = find(y)
    if ans[x] == ans[y] == -1:
        ans[y] = x
    elif xx == yy:
        continue
    else:
        ans[yy] = xx

n = 0
for i in ans:
    if i == -1:
        n += 1

print(n)
import itertools
import sys
H, W = [int(i) for i in input().split(' ')]

cross = [[0] * (H + W -1) for _ in range(H + W - 1)]
for i, line in enumerate(sys.stdin):
    for j, c in enumerate(line.strip()):
        if c == "#":
            cross[i+j][i-j+W-1] = 1

across = [[0] + list(itertools.accumulate(xs)) for xs in cross]
r_cross = [[xs[i] for xs in cross] for i in range(H + W - 1)]
across2 = [[0] + list(itertools.accumulate(xs)) for xs in r_cross]

r = 0
for i in range(H+W-1):
    for j in range(H+W-1):
        if cross[i][j] != 1:
            continue
        for k in range(j+1, H+W-1):
            if cross[i][k] == 1:
                if i - (k-j) >= 0:
                    r += across[i - (k - j)][k+1] - across[i - (k - j)][j]
                if i + (k-j) < H + W - 1:
                    r += across[i + (k - j)][k+1] - across[i + (k - j)][j]

for i in range(H+W-1):
    for j in range(H+W-1):
        if cross[j][i] != 1:
            continue
        for k in range(j+1, H+W-1):
            if cross[k][i] == 1:
                if i - (k-j) >= 0:
                    r += across2[i - (k - j)][k] - across2[i - (k - j)][j+1]
                if i + (k-j) < H + W - 1:
                    r += across2[i + (k - j)][k] - across2[i + (k - j)][j+1]

print(r)


### FIXED CODE ###

N, = [int(i) for i in input().split(' ')]
import sys
As = []
for line in sys.stdin:
    As.append(int(line.strip()))

As = sorted(As)
r = 0
r2 = 0
if N == 2:
    r = As[1] - As[0]
elif N == 3:
    r = max(2*As[2] - As[1] - As[0], As[2] + As[1] - 2 * As[0])
elif N % 2 == 1:
    r -= sum(As[:(N//2) - 1]) * 2
    r -= As[(N // 2)] + As[(N // 2) - 1]
    r += sum(As[(N // 2)+1:]) * 2
    #print(r)

    r2 -= sum(As[:(N//2)]) * 2
    r2 += As[(N // 2)+1] + As[(N // 2)]
    r2 += sum(As[(N // 2)+2:]) * 2
    #print(r2)
    r = max(r, r2)
else:
    #print(As[:(N//2) - 1])
    r -= sum(As[:(N//2) - 1]) * 2
    r += As[(N // 2)] - As[(N // 2) - 1]
    r += sum(As[(N // 2)+1:]) * 2
    #r2 -= sum(As[:(N//2)]) * 2
    #r2 += As[(N // 2)+1] + As[(N // 2)]
    #r2 += sum(As[(N // 2)+2:]) * 2
    #r = max(r, r2)
print(r)