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

# D - Lamp

from numpy import zeros

H, W = map(int, input().split())
M = [[str(m) for m in input()] for _ in range(H)]
U = zeros((H, W), dtype=int)
L = zeros((H, W), dtype=int)
D = zeros((H, W), dtype=int)
R = zeros((H, W), dtype=int)

for i in range(H):
    for j in range(W):
        if M[i][j] != '#':
            if i == 0:
                U[i][j] = 1
            else:
                U[i][j] = U[i - 1][j] + 1
            if j == 0:
                L[i][j] = 1
            else:
                L[i][j] = L[i][j - 1] + 1

        k, l = H - i - 1, W - j - 1
        if M[k][l] != '#':
            if i == 0:
                D[k][l] = 1
            else:
                D[k][l] = D[k + 1][l] + 1
            if j == 0:
                R[k][l] = 1
            else:
                R[k][l] = R[k][l + 1] + 1

ans = 0
for i in range(H):
    for j in range(W):
        p = U[i][j] + L[i][j] + D[i][j] + R[i][j] - 3
        ans = max(ans, p)

print(ans)


### FIXED CODE ###

# # D - Lamp

import numpy as np

H, W = map(int, input().split())
M = [list(input()) for _ in range(H)]
M = (np.array(M) == '.') * 1

L = np.zeros((H, W), dtype=int)
R = np.zeros((H, W), dtype=int)
D = np.zeros((H, W), dtype=int)
U = np.zeros((H, W), dtype=int)

for i in range(W):
    if i == 0:
        L[:, i] = M[:, i]
        R[:, W - i - 1] = M[:, W - i - 1]
    else:
        L[:, i] = (L[:, i - 1] + 1) * M[:, i]
        R[:, W - i - 1] = (R[:, W - i] + 1) * M[:, W - i - 1]

for i in range(H):
    if i == 0:
        U[i, :] = M[i, :]
        D[H - i - 1, :] = M[H - i - 1, :]
    else:
        U[i, :] = (U[i - 1, :] + 1) * M[i, :]
        D[H - i - 1, :] = (D[H - i, :] + 1) * M[H - i - 1, :]

print(max(np.max(L + R + D + U - 3), 0))
### BUGGY CODE ###

from collections import deque
n = int(input())
Ps = list(map(lambda x: int(x)-1, input().split()))
cost = [min(min(i, n-1-i), min(j, n-1-j)) for i in range(n) for j in range(n)]
INF = 10**18
DIRC = [(-1, 0), (0, 1), (1, 0), (0, -1)]
exist = [1]*(n**2)


def bfs(init_v):
    next_v = deque([to_idx(init_v)])
    exist[init_v] = 0
    dist = [INF]*(n**2)
    dist[init_v] = cost[init_v]
    while next_v:
        i, j = next_v.popleft()

        for di, dj in DIRC:
            x, y = i+di, j+dj
            if x < 0 or y < 0 or n <= x or n <= y:
                continue

            if dist[to_v(x, y)] <= dist[to_v(i, j)]+exist[to_v(i, j)]:
                continue
            dist[to_v(x, y)] = dist[to_v(i, j)]+exist[to_v(i, j)]

            if cost[to_v(x, y)] <= dist[to_v(x, y)]:
                continue
            cost[to_v(x, y)] = dist[to_v(x, y)]
            next_v.append((x, y))


def to_idx(p):
    i, j = divmod(p, n)
    return i, j


def to_v(i, j):
    return i*n+j


ans = 0
for p in Ps:
    ans += cost[p]
    bfs(p)

print(ans)

### FIXED CODE ###

from collections import deque
n = int(input())
Ps = list(map(lambda x: int(x)-1, input().split()))
cost = [min(i, n-1-i, j, n-1-j) for i in range(n) for j in range(n)]
exist = [1]*(n**2)


def to_idx(p):
    return divmod(p, n)


def to_v(i, j):
    return i*n+j


def bfs(init_v):
    next_v = deque([init_v])
    exist[init_v] = 0
    while next_v:
        v = next_v.popleft()
        i, j = to_idx(v)
        if 0 < i:
            v2 = v-n
            if cost[v2] > cost[v]+exist[v]:
                cost[v2] = cost[v]+exist[v]
                next_v.append(v2)

        if i < n-1:
            v2 = v+n
            if cost[v2] > cost[v]+exist[v]:
                cost[v2] = cost[v]+exist[v]
                next_v.append(v2)

        if 0 < j:
            v2 = v-1
            if cost[v2] > cost[v]+exist[v]:
                cost[v2] = cost[v]+exist[v]
                next_v.append(v2)

        if j < n-1:
            v2 = v+1
            if cost[v2] > cost[v]+exist[v]:
                cost[v2] = cost[v]+exist[v]
                next_v.append(v2)

ans = 0
for p in Ps:
    ans += cost[p]
    bfs(p)
print(ans)
### BUGGY CODE ###

import itertools
n = int(input())
L = list(map(int, input().split()))

#%%
ans = 0
for c in itertools.combinations(L, 3):
    if (c[0] < c[1] + c[2]) and (c[1] < c[0] + c[2]) and (c[2] < c[0] + c[1]):
        ans += 1

print(ans)


### FIXED CODE ###

import bisect
n = int(input())
L = list(map(int, input().split()))
#%%
L.sort()

ans = 0
for i in range(n-2): # aを固定
    for j in range(i+1, n-1): # bを固定
        ab = L[i] + L[j]
        idx = bisect.bisect_left(L, ab, lo=j)
        ans += max(idx - (j+1), 0)

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

n = int(input())
li = list(map(int, input().split()))
ans = 0

li.sort()

for a, aa in enumerate(li):
  if a < n - 2:
    for b, bb in enumerate(li[a+1:]):
      for c, cc in enumerate(li[a+1+b+1:]):
        if aa + bb <= cc:
          break
        else:
          ans += 1
            
print(ans)

### FIXED CODE ###

import bisect

n = int(input())
li = list(map(int, input().split()))
ans = 0

li.sort()

for i in range(n):
  for j in range(i+1, n):
    cnt = bisect.bisect_left(li, li[i]+li[j])
    ans += cnt - j - 1
            
print(ans)
### BUGGY CODE ###

from sys import stdin
n = int(stdin.readline())
memo = []
for i in range(n):
    m = int(stdin.readline())
    if m in memo: del memo[memo.index(m)]
    else: memo.append(m)
print(len(memo))

### FIXED CODE ###

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

def main():
    import sys
    input = sys.stdin.buffer.readline
    N, M = (int(i) for i in input().split())
    ABC = []
    c_all_or = 0
    where_open = lambda s: sum(2**j for j in s)
    for i in range(M):
        a, b = (int(j) for j in input().split())
        c = {int(j)-1 for j in input().split()}
        c_all_or |= where_open(c)
        ABC.append((a,b,c))
    if c_all_or != ((1<<N) - 1):
        print(-1)
        return 0
    r = [10**9] * (1<<N)
    r[0] = 0
    for bit in range(1,1<<N):
        q = r[bit]
        for i in range(M):
            cur = where_open(ABC[i][2])
            less = (bit ^ cur) & bit
            q = min(q,r[less] + ABC[i][0])
        r[bit] = q
    
    print(r[(1<<N) - 1])
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.buffer.readline
    N, M = (int(i) for i in input().split())
    ABC = []
    c_all_or = 0
    where_open = lambda s: sum(2**j for j in s)
    for i in range(M):
        a, b = (int(j) for j in input().split())
        c = {int(j)-1 for j in input().split()}
        wc = where_open(c)
        c_all_or |= wc
        ABC.append((a,b,wc))
    if c_all_or != ((1<<N) - 1):
        print(-1)
        return 0
    r = [10**9] * (1<<N)
    r[0] = 0
    for bit in range(1,1<<N):
        q = r[bit]
        for i in range(M):
            cur = ABC[i][2]
            less = (bit ^ cur) & bit
            q = min(q,r[less] + ABC[i][0])
        r[bit] = q
    
    print(r[(1<<N) - 1])
if __name__ == '__main__':
    main()
### BUGGY CODE ###

N,M=[int(i) for i in input().split()]
inf=1000000007
aa=[]
for i in range(M):
	aa.append(int(input()))
dp=[0]*(N+1)
dp[0]=1
if 1 in aa:
	dp[1]=0
else:
	dp[1]=1
for i in range(2,N+1):
	if i in aa:
		dp[i]=0
	else:
		dp[i]=dp[i-2]%inf+dp[i-1]%inf
print(dp[N]%inf)

### FIXED CODE ###

N,M=[int(i) for i in input().split()]
inf=1000000007
dp=[-1]*(N+1)
for i in range(M):
	dp[int(input())]=0
dp[0]=1
if dp[1]==-1:
	dp[1]=1
for i in range(2,N+1):
	if dp[i]==0:
		continue
	else:
		dp[i]=(dp[i-2]+dp[i-1])%inf
print(dp[N]%inf)
### BUGGY CODE ###

a=int(input())
tem = 1
if a != 0:
    b=input().split(" ")
    for i in range(a):
        tem = tem * int(b[i])
    if tem> 10**18:
        tem = -1
print(tem)

### FIXED CODE ###

# we collect the input A1 upto An.
# limit cannot exceed 10**18
# if N = 0 then ans = 0
# in N is in range then compute ans * A[n]
# else if  ans is greater than limit then display 1
# finally if length equal 1 then display -1
N = int(input())
ans = 1
limit = 10 ** 18
length = 0

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

A0 = set(A)
if 0 in A0:
    ans = 0
else:
    pass

for n in range(N):
    ans = ans * A[n]
    if ans == 0:
        break
    elif ans > limit:
        length = 1
        break
    else:
        pass

if length == 1:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

import sys
import itertools
# import numpy as np
import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

S.append(0)
T.append(0)
MAX = 2005
dp0 = [[0] * MAX for _ in range(MAX)]
dp1 = [[0] * MAX for _ in range(MAX)]

dp0[0][0] = 1
for i in range(N + 1):
    for j in range(M + 1):
        dp0[i + 1][j] += dp0[i][j] % MOD
        dp1[i][j] += dp0[i][j] % MOD
        dp1[i][j + 1] += dp1[i][j] % MOD
        if S[i] == T[j]: 
            dp0[i + 1][j + 1] += dp1[i][j] % MOD
print(dp1[N][M] % MOD)


### FIXED CODE ###

import sys
import itertools
# import numpy as np
import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

S.append(0)
T.append(0)
MAX = 2005
dp0 = [[0] * MAX for _ in range(MAX)]
dp1 = [[0] * MAX for _ in range(MAX)]

dp0[0][0] = 1
for i in range(N + 1):
    for j in range(M + 1):
        dp0[i + 1][j] += dp0[i][j] % MOD
        dp1[i][j] += dp0[i][j] % MOD
        dp1[i][j + 1] += dp1[i][j] % MOD
        if S[i] == T[j]: 
            dp0[i + 1][j + 1] += dp1[i][j] % MOD
print(dp1[N][M] % MOD)
### BUGGY CODE ###

n, k = map(int,input().split())
h = list(map(int, input().split()))
c = [0 for i in range(n)]
c[0] = 0
c[1] = abs(h[1] - h[0])
# c[2] = c[0] + abs(h[2]-h[0])
# c[2] = c[1] + abs(h[2]-h[1])
# c[3] = c[1] + abs(h[3]-h[1])
# c[3] = c[2] + abs(h[3]-h[1])
for i in range(2, n):
    # c[i] = min(c[i-1]+abs(h[i]-h[i-1]), c[i-2]+abs(h[i]-h[i-2]))
    temp_min = float('inf')
    for j in range(1,k+1):
        if i >= j:
            temp_min = min(temp_min,c[i-j]+abs(h[i]-h[i-j]))
    c[i] = temp_min
print(c[-1])


### FIXED CODE ###

n,k = map(int,input().split())
h = list(map(int,input().split()))
dp = [0]*n
dp[0] = 0
dp[1] = abs(h[1]-h[0])
# dp[2] = min(abs(h[2]-h[0]), dp[1]+abs(h[2]-h[1]))
# dp[3] = min((abs(h[3]-h[1])+dp[1]), abs(h[3]-h[2])+dp[2])
for i in range(2,n):
    ans = 10000000000000000000000000
    for j in range(1,k+1):
        if i-j >= 0:
            tmp = abs(h[i]-h[i-j])+dp[i-j]
            ans = min(ans,tmp)
    # dp[i] = min((abs(h[i]-h[i-2])+dp[i-2]), abs(h[i]-h[i-1])+dp[i-1])
    dp[i] = ans
print(dp[-1])
### BUGGY CODE ###

#方針...ユークリッドの互除法を用いて2整数が互いに素かどうかを判定する関数を設計
#       O(route n)で2整数の公約数をリストとして出力する関数を設計
import math

def judge_disjoint(a,b):

    while (a!=0 and b!=0):
        if b<a:
            a,b = b,a
        b = b%a
    if (a==1 or b==1):
        return True
    else:
        return False

def common_divisor(a,b):
    ls_a=[]
    ls_b=[]
    A = int(math.sqrt(a))
    B = int(math.sqrt(b))
    for i in range(1,A+1):
        if (a%i==0):
            ls_a.append(i)
            ls_a.append(a//i)
    for i in range(1,B+1):
        if (b%i==0):
            ls_b.append(i)
            ls_b.append(b//i)
    ls = list(set(ls_a) & set(ls_b))
    return ls

A,B = list(map(int,input().split()))
ls = common_divisor(A,B)
ls.sort()
#print(ls)
N = len(ls)

def solve(ls):
    ls2=[1]
    ls.pop(0)

    if (len(ls)!=0):
        ls2.append(ls[0])
        for i in range(1,len(ls)):
            flag = True
            for j in range(i):
                if (ls[i]%ls[j]==0):
                    flag = False
            if flag:
                ls2.append(ls[i])
    return ls2


ans = len(solve(ls))


print(ans)


### FIXED CODE ###

#方針...gcd(A,B)の約数の中で素数or1となるものの個数を調べれば良い(O(route N))
import fractions
import math

def prime_fac(N):
    primes = {1:1}
    n = int(math.sqrt(N))
    for i in range(2,n+1):
        if N%i==0:
            primes[i] = 0
            while N%i==0:
                primes[i] += 1
                N = N//i
    if (N!=1):
        primes[N] = 1
    return primes

A,B = list(map(int,input().split()))
C = fractions.gcd(A,B)
primes = prime_fac(C)

print(len(primes))
### BUGGY CODE ###

n,a,b = map(int,input().split())
s = input()
ans = ["0"]*n
bcnt = 0
for i in range(n):
  if s[i] == "a":
    if ans.count("Yes") < a+b:
      ans[i] = "Yes"
    else:
      ans[i] = "No"
  elif s[i] == "b":
    bcnt += 1
    if ans.count("Yes") < a+b and bcnt <= b:
      ans[i] = "Yes"
    else:
      ans[i] = "No"
  else:
    ans[i] = "No"
print(*ans,sep='\n')

### FIXED CODE ###

n,a,b = map(int,input().split())
s = input()
ans = ["0"]*n
acnt = 0
bcnt = 0
for i in range(n):
  if s[i] == "a":
    if acnt < a+b:
      acnt += 1
      ans[i] = "Yes"
    else:
      ans[i] = "No"
  elif s[i] == "b":
    bcnt += 1
    if acnt < a+b and bcnt <= b:
      acnt += 1
      ans[i] = "Yes"
    else:
      ans[i] = "No"
  else:
    ans[i] = "No"
print(*ans,sep='\n')
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
x = []
acc = 0
ans = 0
for a in A:
    while acc & a:
        acc ^= x.pop(0)
    x.append(a)
    acc ^= a
    ans += len(x)
print(ans)


### FIXED CODE ###

from collections import deque
N = int(input())
A = list(map(int, input().split()))
x = deque()
acc = 0
ans = 0
for a in A:
    while acc & a:
        acc ^= x.popleft()
    x.append(a)
    acc ^= a
    ans += len(x)
print(ans)
### BUGGY CODE ###

import itertools

n,m,r = map(int,input().split())
wa = [[float("INF")]*n for i in range(n)]
l = [i-1 for i in map(int,input().split())]
for i in range(m):
    a,b,c = map(int,input().split())
    a -= 1
    b -= 1
    wa[a][b] = c
    wa[b][a] = c
for i in range(n):
    wa[i][i] = 0

for k in range(n):
    for i in range(n):
        for j in range(n):
            wa[i][j] = min(wa[i][j],wa[i][k]+wa[k][j])

ans = float("INF")

for p in list(itertools.permutations(l)):
    count = 0
    for i in range(r-1):
        count += wa[p[i]][p[i+1]]
    ans = min(ans,count)
print(ans)



### FIXED CODE ###

import itertools

n,m,r = map(int,input().split())
wa = [[float("INF")]*n for i in range(n)]
l = [i-1 for i in map(int,input().split())]
for i in range(m):
    a,b,c = map(int,input().split())
    a -= 1
    b -= 1
    wa[a][b] = c
    wa[b][a] = c
for i in range(n):
    wa[i][i] = 0

for k in range(n):
    for i in range(n):
        for j in range(n):
            wa[i][j] = min(wa[i][j],wa[i][k]+wa[k][j])

ans = float("INF")

for p in list(itertools.permutations(l)):
    count = 0
    for i in range(r-1):
        count += wa[p[i]][p[i+1]]
    ans = min(ans,count)
print(ans)
### BUGGY CODE ###

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

import math

maxcomb = 0
pair = 0

for i in range (0, N):
	z = math.comb(L[-1], L[i])
	if z > maxcomb:
		maxcomb = z
		pair = i

print(L[-1], L[pair])

### FIXED CODE ###

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

import math
import bisect
max = L[-1]
maxdiv2 = max//2
posleft = bisect.bisect_left(L, maxdiv2)
posright = bisect.bisect_right(L, maxdiv2)

if len(L) == 2:
	print(L[1], L[0])
	exit()

if posleft!= posright:
	print(max, L[posleft])
	exit()

if abs(max/2 - L[posleft]) > abs(max/2 - L[posleft-1]):
	print(max, L[posleft-1])
else:
	print(max, L[posleft])
### BUGGY CODE ###

S=list(map(int,input()))
N=len(S)#S[0]~S[N-1]
count=0
j=0
def make_list(x,S):#x:元の配列から切り取る番号 S:リスト受け取り
    a=[]
    for i in range(0,x):#S[0]~S[x-1]までを追加
        a.append(S[i])
    if x<len(S)-2:
        for i in range(x+2,len(S)):
            a.append(S[i])
    return a
while j==0:
    for i in range(N-1):#S[0]~S[N-2]
        if (S[i]==0 and S[i+1]==1)or(S[i]==1 and S[i+1]==0):
            count+=2
            S=make_list(i,S)#Sの書き換え
            N=len(S)#Nの書き換え
            if N==0:
                j=1
            break
        elif i==N-2:
            j=1
print(count)

### FIXED CODE ###

S=list(map(int,input()))
a=0
b=0
for i in range(len(S)):
    if S[i]==1:
        a+=1
    else:
        b+=1
print(2*min(a,b))
### BUGGY CODE ###

n = int(input())
d = list(map(int,input().split()))
m = int(input())
t = list(map(int,input().split()))


for i in range(m):
    try:
        z = d.index(t[i])
    except ValueError:
        print('NO')
        exit(0)
    else:
        d.pop(z)

print('YES')

### FIXED CODE ###

n = int(input())
d = list(map(int,input().split()))
m = int(input())
t = list(map(int,input().split()))
d.sort()
t.sort()
j = 0
for i in range(n):
    if d[i] == t[j]:
        j += 1
    if j == m:
        break

if j == m:
    print('YES')
else:
    print('NO')
### BUGGY CODE ###

# https://atcoder.jp/contests/abc160/tasks/abc160_d
N, X, Y = map(int, input().split())

visited = set()

# special case: first advance
for i in range(N - 1):
    visited.add((i, i + 1))
visited.add((X - 1, Y - 1))

print(len(visited))

for _ in range(N - 2):
    total = 0

    for point in visited.copy():
        x, y = point

        if (x - 1, y) not in visited and x - 1 >= 0:
            visited.add((x - 1, y))
            total += 1

        if (x + 1, y) not in visited and x + 1 != y:
            visited.add((x + 1, y))
            total += 1

        if (x, y - 1) not in visited and x != y - 1:
            visited.add((x, y - 1))
            total += 1

        if (x, y + 1) not in visited and y + 1 < N:
            visited.add((x, y + 1))
            total += 1

    print(total)


### FIXED CODE ###

# https://atcoder.jp/contests/abc160/tasks/abc160_d
N, X, Y = map(int, input().split())

visited = set()

# special case: first advance
for i in range(N - 1):
    visited.add((i, i + 1))
visited.add((X - 1, Y - 1))

print(len(visited))

next_items = visited.copy()
for _ in range(N - 2):
    candidates = []

    for point in next_items:
        x, y = point

        if (x - 1, y) not in visited and x - 1 >= 0:
            visited.add((x - 1, y))
            candidates.append((x - 1, y))

        if (x + 1, y) not in visited and x + 1 != y:
            visited.add((x + 1, y))
            candidates.append((x + 1, y))

        if (x, y - 1) not in visited and x != y - 1:
            visited.add((x, y - 1))
            candidates.append((x, y - 1))

        if (x, y + 1) not in visited and y + 1 < N:
            visited.add((x, y + 1))
            candidates.append((x, y + 1))

    print(len(candidates))
    next_items = candidates
### BUGGY CODE ###

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

X = sum(a)
x = sum(a[:1])

minsum = 10000000000

for i in range(1,n):
    x = sum(a[:i])
    minsum = min(minsum,abs(X-2*x))

print(minsum)


### FIXED CODE ###

# -*- coding: utf-8 -*-

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

X = sum(a)

minsum = 10000000000

cnt = 0

for i in range(1,n):
    cnt += a[i-1]
    minsum = min(minsum,abs(X-2*cnt))

print(minsum)
### BUGGY CODE ###

import math
import numpy as np

n,k=(int(x) for x in input().split())
a = [int(x) for x in input().split()]


for _ in range(k):
    new_a = []
    c = 0
    a_in = np.maximum(0,np.arange(0, n)-a)
    a_out = np.minimum(n,np.arange(0, n)+a)
    
    for x in np.arange(0,n):
        c += np.count_nonzero(a_in == x)
        c -= np.count_nonzero(a_out+1 == x)
        new_a.append(c)
    a = new_a
    if np.all(a==n):
        break

print(" ".join([str(x) for x in a]))

### FIXED CODE ###

import math
import numpy as np

n,k=(int(x) for x in input().split())
a = [int(x) for x in input().split()]


for _ in range(k):
    new_a = np.zeros(n+1,dtype=int)
    np.add.at(new_a, np.maximum(0,np.arange(0, n)-a), 1)
    np.add.at(new_a, np.minimum(n,np.arange(0, n)+a+1), -1)
    a = new_a.cumsum()[:-1]
    if np.all(a==n):
        break

print(" ".join([str(x) for x in a]))
### BUGGY CODE ###

import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]

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

ans=-float('inf')
for i in range(n+1):
    tmp1=a[:n+i]
    tmp2=a[n+i:]
    tmp1.sort(reverse=True)
    tmp2.sort()
    ans=max(ans,sum(tmp1[:n])-sum(tmp2[:n]))
print(ans)

### FIXED CODE ###

import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]

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

left=[0]*(n+1)
right=[0]*(n+1)
left[0]=sum(a[:n])
right[n]=sum(a[n+n:])

mae,usi=a[:n],list(map(lambda x: x*-1,a[n+n:]))

heapq.heapify(mae)
heapq.heapify(usi)

for i in range(n):
    tmp=heapq.heappushpop(mae,a[n+i])
    left[i+1]=left[i]+a[n+i]-tmp
    tmp=heapq.heappushpop(usi,-a[n+n-i-1])
    right[n-i-1]=right[n-i]+a[n+n-i-1]+tmp
# print(mae)
# print(left)
# print(right)
ans=-float('inf')
for i in range(n+1):
    ans=max(ans, left[i]-right[i])
print(ans)
### BUGGY CODE ###

import numpy as np
s = input()
cnt = 0
ss = []
nums = np.array([(i+1)*2019 for i in range(200000//2019) if not "0" in str((i+1)*2019)])
for start in range(len(s)):
  end = start + 3
  while(end+1<=len(s)):
    if int(s[start:end+1]) in nums:
      cnt += 1
    end += 1
print(cnt)

### FIXED CODE ###

s = input()
l = len(s)
dp = [0]*2019
dp[0] = 1
r = 0
for i in range(1, l + 1):
    r += int(s[-i]) * pow(10, i - 1, 2019)
    r %= 2019
    dp[r] += 1
    
print(sum([(i * (i - 1)) // 2 for i in dp]))
### BUGGY CODE ###

n, k = map(int, input().split())
h = sorted([int(input()) for i in range(n)])
ans = float("inf")
for i in range(n - k + 1):
    use = h[i:i + k]
    ans = min(ans, h[i + k - 1] - h[i])
print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
h = sorted([int(input()) for i in range(n)])
ans = float("inf")
for i in range(n - k + 1):
    ans = min(ans, h[i + k - 1] - h[i])
print(ans)
### BUGGY CODE ###

k,q = input().split()
k = int(k)
q = int(q)

d = input().split()
for i in range(k):
    d[i] = int(d[i])

for r in range(q):
    n,x,m = input().split()
    n = int(n)
    x = int(x)
    m = int(m)

    dd = [0]*k
    DD = [0]*(k+1)
    for i in range(k):
        dd[i] = (d[i]-1)%m + 1
        DD[i+1] = DD[i] + dd[i]
        
    #最後のこう
    
    alast = x + DD[k]*((n-1)//k) + DD[(n-1)%k]
    kuriagari = alast // m - x//m

#    print([x%m, alast, alast%m, n - kuriagari - 1])
    print (n - 1 - kuriagari)

### FIXED CODE ###

k,q = input().split()
k = int(k)
q = int(q)

d = input().split()
for i in range(k):
    d[i] = int(d[i]) - 1

import numpy as np
d = np.array(d)

for r in range(q):
    n,x,m = input().split()
    n = int(n)
    x = int(x)
    m = int(m)

    dd = d % m + np.ones(k,dtype="int")
    DD = np.concatenate((np.zeros(1, dtype="int"),np.cumsum(dd) ))
    
    alast = x + DD[k]*((n-1)//k) + DD[(n-1)%k]
    kuriagari = alast // m - x//m

#    print([x%m, alast, alast%m, n - kuriagari - 1])
    print (n - 1 - kuriagari)