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

def solve():
    N, M = map(int, input().split())
    adjL = [[] for _ in range(N)]
    outdegs = [0] * N
    for _ in range(M):
        s, t = map(int, input().split())
        s, t = s-1, t-1
        adjL[s].append(t)
        outdegs[s] += 1

    ans = N
    for vRem in range(N):
        if outdegs[vRem] == 1: continue
        dp = [0] * N
        for v in reversed(range(N-1)):
            if v != vRem:
                dp[v] = sum([dp[v2] for v2 in adjL[v]]) / outdegs[v] + 1
            else:
                sumDP, maxDP = 0, -1
                for v2 in adjL[v]:
                    sumDP += dp[v2]
                    if dp[v2] > maxDP:
                        maxDP = dp[v2]
                dp[v] = (sumDP-maxDP) / (outdegs[v]-1) + 1
        ans = min(ans, dp[0])

    print(ans)


solve()


### FIXED CODE ###

def solve():
    import sys
    input = sys.stdin.readline

    N, M = map(int, input().split())
    adjL = [[] for _ in range(N)]
    outdegs = [0] * N
    for _ in range(M):
        s, t = map(int, input().split())
        s, t = s-1, t-1
        adjL[s].append(t)
        outdegs[s] += 1

    dp = [0] * N
    for v in reversed(range(N-1)):
        dp[v] = sum([dp[v2] for v2 in adjL[v]]) / outdegs[v] + 1

    ans = dp[0]
    for vRem in range(N-1):
        if outdegs[vRem] == 1: continue
        sumDP, maxDP = 0, -1
        for v2 in adjL[vRem]:
            sumDP += dp[v2]
            if dp[v2] > maxDP:
                maxDP = dp[v2]
        dp[vRem] = (sumDP-maxDP) / (outdegs[vRem]-1) + 1
        for v in reversed(range(vRem)):
            dp[v] = sum([dp[v2] for v2 in adjL[v]]) / outdegs[v] + 1
        ans = min(ans, dp[0])

    print(ans)


solve()
### BUGGY CODE ###

R, C, K = map(int, input().split())
rcvs = [list(map(int, input().split())) for _ in range(K)]

for i in range(len(rcvs)):
    rcvs[i][0] -= 1
    rcvs[i][1] -= 1

rewards = [[0 for _ in range(C)] for _ in range(R)]

for rcv in rcvs:
    rewards[rcv[0]][rcv[1]] = rcv[2]
    
#%%

dp = [[[0 for _ in range(4)] for _ in range(C+1)] for _ in range(R+1)]

for i in range(R):
    for j in range(C):
        reward = rewards[i][j]
        for k in range(4): # move downside without selecting
            if dp[i][j+1][k] > dp[i+1][j+1][0]:
                dp[i+1][j+1][0] = dp[i][j+1][k]
            if dp[i][j+1][k] + reward > dp[i+1][j+1][1]:
                dp[i+1][j+1][1] = dp[i][j+1][k] + reward
        for k in range(4): # move downside without selecting
            if dp[i+1][j][k] > dp[i+1][j+1][k]:
                dp[i+1][j+1][k] = dp[i+1][j][k]
            if k <= 2:
                if dp[i+1][j][k] + reward > dp[i+1][j+1][k+1]:
                    dp[i+1][j+1][k+1] = dp[i+1][j][k] + reward

answer = 0
for i in range(R):
    for j in range(C):
        for k in range(4):
            if answer < dp[i+1][j+1][k]:
                answer = dp[i+1][j+1][k]
print(answer)

### FIXED CODE ###

import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8
import sys

R, C, K = map(int, input().split())
rcvs = [list(map(int, input().split())) for _ in range(K)]
rcvs = np.array(rcvs, dtype=np.int64)

@njit(i8(i8[:,:]), cache=True)
def main(rcvs):
    rewards = np.zeros((R, C), dtype=np.int64)
    
    for i in range(len(rcvs)):
        rewards[rcvs[i][0]-1][rcvs[i][1]-1] = rcvs[i][2]
    
    dp = np.zeros((R+1, C+1, 4), dtype=np.int64)
    
    for i in range(R):
        for j in range(C):
            reward = rewards[i][j]
            dp[i+1][j+1][0] = max(dp[i][j+1])
            dp[i+1][j+1][1] = dp[i+1][j+1][0] + reward
            
            for k in range(4): # move downside without selecting
                dp[i+1][j+1][k] = max(dp[i+1][j][k], dp[i+1][j+1][k])
            if reward > 0:
                for k in range(3):
                    dp[i+1][j+1][k+1] = max(dp[i+1][j][k]+reward,dp[i+1][j+1][k+1])
    return max(dp[-1][-1])

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

#!/usr/bin/env python3
#ABC65 B
n = int(input())

a = [int(input()) for _ in range(n)]

bo = [1]
b = 1
c = 0
while 1:
    c += 1
    b = a[b-1]
    if b in bo:
        print(-1)
        quit()
    else:
        bo.append(b)
    if b == 2:
        break
print(c)


### FIXED CODE ###

#!/usr/bin/env python3
#ABC65 B
n = int(input())

a = [int(input()) for _ in range(n)]

b = 1
c = 0
for i in range(n):
    c += 1
    b = a[b-1]
    if b == 2:
        print(c)
        quit()
print(-1)
### BUGGY CODE ###

from collections import deque, Counter
 
N = int(input())
 
edge =  [[] for i in range(N-1)]
to = [[] for i in range(N)]
color = {}
edge_list = []
 
for i in range(N-1):
    a, b = map(int, input().split())
    to[a-1].append(b-1)
    to[b-1].append(a-1)
    edge[i] = [a-1, b-1]
    edge_list.append(a-1)
    edge_list.append(b-1)
 
K = Counter(edge_list).most_common()[0][1]
 
q = deque([])
q.append([0,-1])
 
is_visited = [False] * N
 
while(len(q) != 0):
    cur_node, pre_col = q.popleft()
    col_list = [False] * K
    if not pre_col == -1:
        col_list[pre_col] = True
 
    is_visited[cur_node] = True
 
    for next_node in to[cur_node]:
        if not is_visited[next_node]:
            for i in range(K):
                if not col_list[i]:
                    col_list[i] = True
                    color[(cur_node,next_node)] = i
                    q.append([next_node, i])
                    break
 
print(K)
 
for i in range(N-1):
    print(color[tuple(edge[i])] + 1)
 

### FIXED CODE ###

from collections import deque, Counter

N = int(input())

edge =  [[] for i in range(N-1)]
to = [[] for i in range(N)]
color = {}
edge_list = []

for i in range(N-1):
    a, b = map(int, input().split())
    to[a-1].append(b-1)
    to[b-1].append(a-1)
    edge[i] = [a-1, b-1]
    edge_list.append(a-1)
    edge_list.append(b-1)

K = Counter(edge_list).most_common()[0][1]

q = deque([])
q.append([0,-1])

is_visited = [False] * N

while(len(q) != 0):
    cur_node, pre_col = q.popleft()

    is_visited[cur_node] = True
    col_use = 0

    for next_node in to[cur_node]:
        if not is_visited[next_node]:
            if col_use == pre_col:
                col_use += 1

            color[(cur_node,next_node)] = col_use
            q.append([next_node, col_use])
            col_use += 1

print(K)

for i in range(N-1):
    print(color[tuple(edge[i])] + 1)
### BUGGY CODE ###

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

A_sum_list = [A_list[N-1]]
ans = A_list[N-1]*A_list[N-2]

for i in range(N-1, 1, -1):
    sum_temp = A_sum_list[0] + A_list[i-1]
    A_sum_list.insert(0, sum_temp)
    ans += (sum_temp * A_list[i-2])

#print(A_sum_list)
print(ans%(10**9 + 7))

### FIXED CODE ###

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

A_sum_list = [A_list[N-1]]
ans = A_list[N-1]*A_list[N-2]
sum_temp_old = A_list[N-1]

for i in range(N-1, 1, -1):
    sum_temp = sum_temp_old + A_list[i-1]
    sum_temp_old = sum_temp
    ans += (sum_temp * A_list[i-2])

#print(A_sum_list)
print(ans%(10**9 + 7))
### BUGGY CODE ###

import sys
from collections import deque, defaultdict
import copy
import bisect
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 9)

N = int(input())

A = []
for i in range(N):
	A.append(int(input()))

B = []
for i in range(N):
	loc = bisect.bisect_left(B, A[i])
	if loc == 0:
		B = [A[i]] + B
	else:
		B[loc - 1] = A[i]

print(len(B))

### FIXED CODE ###


import sys
from collections import deque, defaultdict
import copy
import bisect
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 9)

N = int(input())
A = []
for i in range(N):
	A.append(int(input()))

B = []
min = -10000000000
for i in range(N):
	loc = bisect.bisect_right(B, -A[i])
	if loc == len(B):
		B.append(-A[i])
	else:
		B[loc] = -A[i]

print(len(B))
### BUGGY CODE ###

n = int(input())
X, Y, P = [], [], []
for i in range(n):
    x, y, p = map(int, input().split())
    X.append(x)
    Y.append(y)
    P.append(p)

DX = [[0] * n for s in range(2**n)]
DY = [[0] * n for s in range(2**n)]
for s in range(2**n):
    for i in range(n):
        DX[s][i] = abs(X[i]) * P[i]
        DY[s][i] = abs(Y[i]) * P[i]
        for j in range(n):
            if s & (1 << j):
                DX[s][i] = min(DX[s][i], abs(X[i] - X[j]) * P[i])
                DY[s][i] = min(DY[s][i], abs(Y[i] - Y[j]) * P[i])

A = [10**20] * (n + 1)
for s in range(3**n):
    tmp = s
    c, sx, sy = 0, 0, 0
    for i in range(n):
        if tmp % 3 != 0:
            c += 1
        if tmp % 3 == 1:
            sx += 2**i
        if tmp % 3 == 2:
            sy += 2**i
        tmp //= 3
    d = 0
    for i in range(n):
        d += min(DX[sx][i], DY[sy][i])
    A[c] = min(A[c], d)
print(*A, sep="\n")


### FIXED CODE ###

n = int(input())
XYP = [tuple(map(int, input().split())) for i in range(n)]
X = [x for x, y, p in XYP]
Y = [y for x, y, p in XYP]
P = [p for x, y, p in XYP]
pow2 = [2**i for i in range(n + 1)]

DX = [[0] * n for s in range(pow2[n])]
DY = [[0] * n for s in range(pow2[n])]
for s in range(1 << n):
    for i in range(n):
        DX[s][i] = abs(X[i]) * P[i]
        DY[s][i] = abs(Y[i]) * P[i]
        for j in range(n):
            if s & (1 << j):
                DX[s][i] = min(DX[s][i], abs(X[i] - X[j]) * P[i])
                DY[s][i] = min(DY[s][i], abs(Y[i] - Y[j]) * P[i])

BC = [bin(s).count("1") for s in range(pow2[n])]

A = [10**20] * (n + 1)
for sx in range(pow2[n]):
    rx = (pow2[n] - 1) ^ sx
    sy = rx
    for _ in range(pow2[n - BC[sx]]):
        sy = (sy - 1) & rx
        d = 0
        for i in range(n):
            d += min(DX[sx][i], DY[sy][i])
        c = BC[sx] + BC[sy]
        A[c] = min(A[c], d)
print(*A, sep="\n")
### BUGGY CODE ###

n,k = map(int,input().split())
A = list(map(int,input().split()))
ass = 1
for i in range(k):
  ass *= A[i]
for j in range(n-k):
  if ass < ass*A[j+k]/A[j]:
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

n,k = map(int,input().split())
A = list(map(int,input().split()))
for i in range(n-k):
  if A[i]<A[i+k]:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array

# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


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

    N, K = il()
    A = il()

    tmp = 1
    for k in reversed(range(K)):
        tmp *= A[k]
    for k in range(K+1, N + 1):
        p = 1
        for i in range(k-K, k):
            p *= A[i]

        if tmp < p:
            print('Yes')
        else:
            print('No')

        tmp = p


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array

# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


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

    N, K = il()
    A = il()

    for k in range(K, N):
        if A[k - K] < A[k]:
            print('Yes')
        else:
            print('No')


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

N, M, K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
SUM_A=[0 for _ in range(N+1)]
for i in range(N):
    SUM_A[i+1] = A[i] + SUM_A[i]
    if SUM_A[i+1] > K:
        N=i
        break

SUM_B=[0 for _ in range(M+1)]
for i in range(M):
    SUM_B[i+1] = B[i] + SUM_B[i]
    if SUM_B[i+1] > K:
        M=i
        break


cnt = 0
for i in range(N+1):
    for j in range(M+1):
        if SUM_A[i]+SUM_B[j] <= K:
            if i+j > cnt:
                cnt = i+j
print(cnt)

### FIXED CODE ###

N, M, K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
SUM_A=[0 for _ in range(N+1)]
for i in range(N):
    SUM_A[i+1] = A[i] + SUM_A[i]
    if SUM_A[i+1] > K:
        N=i
        break

SUM_B=[0 for _ in range(M+1)]
for i in range(M):
    SUM_B[i+1] = B[i] + SUM_B[i]
    if SUM_B[i+1] > K:
        M=i
        break

cnt = N
for i in range(N+1)[::-1]:
    V=K-SUM_A[i]
    j = cnt-i
    while j < M+1 and SUM_B[j] <= V:
        j += 1
    j-=1
    if i+j > cnt:
        cnt = i+j
print(cnt)
### BUGGY CODE ###

def det(x,y,n):
    return (x+y)**2 - 4*(x**2 + y**2 + x*y - n)
def is_integer_num(n):
    if isinstance(n, int):
        return True
    if isinstance(n, float):
        return n.is_integer()
    return False

n = int(input())

for i in range(1, n+1):
    ans = 0
    for x in range(1,int(pow(n,0.5))+2):
        for y in range(1,int(pow(n,0.5))+2):
            D = det(x,y,i)
            #if x == 1 and y == 1:
                #print(D)
            if D >= 0 and is_integer_num(pow(D,0.5)):
                if -(x+y) + pow(D,0.5) > 0:
                    ans += 1
    print(ans)

### FIXED CODE ###

n = int(input())
ans = [0]*(n+1)
for i in range(1,101):
    for j in range(1,101):
        for k in range(1,101):
            
            a = i**2 + j**2 + k**2 + i*j + j*k + k*i
            
            if a < n+1:
                ans[a] += 1
for i in range(1,n+1):
    print(ans[i])
### BUGGY CODE ###

import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

n = int(input())
list_ABC = [ list(map(int,input().split(" "))) for i in range(n-1)]
q, k = map(int, input().split())
list_XY = [ list(map(int,input().split(" "))) for i in range(q)]

ma = [[0]*n for _ in range(n)]
for a, b, c in list_ABC:
    ma[a-1][b-1] = c
    ma[b-1][a-1] = c

a = csr_matrix(ma)
b = dijkstra(a, directed=False).astype(int)

for x, y in list_XY:
    print(b[x-1][k-1]+b[k-1][y-1])

### FIXED CODE ###

import sys
sys.setrecursionlimit(500000)
 
N = int(input())
ABC = [list(map(int, input().split())) for i in range(N-1)]
Q, K = map(int, input().split())
D = [0] * (N+1)
L = [[] for i in range(N+1)]
for a, b, c in ABC:
    L[a].append([b, c])
    L[b].append([a, c])
 
 
def dfs(n, np):
    for nc in L[n]:
        if nc[0] == np:
            continue
        else:
            D[nc[0]] = D[n] + nc[1]
            dfs(nc[0], n)
 
 
dfs(K, 0)
for i in range(Q):
    x, y = map(int, input().split())
    print(D[x] + D[y])
### BUGGY CODE ###

a,b,k=map(int, input().split());print(*[i for i in range(a,b+1)if(i>=a+k)*b-k<i])

### FIXED CODE ###

a,b,k=map(int,input().split());r=range(a,b+1);print(*sorted(set(r[:k])|set(r[-k:])),sep='\n')
### BUGGY CODE ###

N = int(input())
head_prob_table = [[0] * (N+1) for i in range(N)]
head_prob = list(map(float, input().split()))

head_prob_table[0][1] = head_prob[0]
head_prob_table[0][0] = 1-head_prob[0]

for i in range(1, N):
    for j in range(i+2):
        prob = 0
        prob += head_prob_table[i-1][j] * (1 - head_prob[i])
        if j > 0:
            prob += head_prob_table[i-1][j-1] * head_prob[i]
        head_prob_table[i][j] = prob

print(sum(head_prob_table[N-1][(N+1)//2:]))


### FIXED CODE ###

N = int(input())
def main():
    head_prob_table = [[0.0] * (N+1) for i in range(N)]
    head_prob = list(map(float, input().split()))

    head_prob_table[0][1] = head_prob[0]
    head_prob_table[0][0] = 1-head_prob[0]

    for i in range(1, N):
        for j in range(i+2):
            head_prob_table[i][j] += head_prob_table[i-1][j] * (1 - head_prob[i])
            if j > 0:
                head_prob_table[i][j] += head_prob_table[i-1][j-1] * head_prob[i]

    print(sum(head_prob_table[N-1][(N+1)//2:]))

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

n=int(input())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]
ma=max(A)
import heapq
BB=[]
Chk=[False]*n
for i in range(n):
  if A[i]==B[i]:
    Chk[i]=True
for i in range(n):
  BB.append([-B[i],i])
heapq.heapify(BB)
ans=0
while BB:
  b,ind=heapq.heappop(BB)
  if Chk[ind]:
    continue
  else:
    if ind==0:
      d=B[-1]+B[1]
    elif ind==n-1:
      d=B[-2]+B[0]
    else:
      d=B[ind-1]+B[ind+1]
    if d>=-b:
      break
    else:
      b_next=max(d,A[ind])
      ans+=(-b-b_next-1)//d+1
      b+=d*((-b-b_next-1)//d+1)
      B[ind]=-b
      if b>0:
        break
      elif A[ind]==-b:
        Chk[ind]=True
      else:
        heapq.heappush(BB,[b,ind])
  
print(ans if A==B else -1)


### FIXED CODE ###

n=int(input())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]

from heapq import heappop, heappush
push = lambda x,i: heappush(BB,(-x,i))
BB=[]

for i,b in enumerate(B):
  push(b,i)

ans=0
while BB:
  b,ind=heappop(BB)
  b,ai=-b,A[ind]
  if b<ai:
    ans=-1
    break
  d=B[(ind-1)%n]+B[(ind+1)%n]
  dd=(b-ai)//d
  if dd==0:
    if b==ai:
      continue
    ans=-1
    break
  ans+=dd
  B[ind]-=d*dd
  push(b-d*dd,ind)
  
print(ans)
### BUGGY CODE ###

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

x = list()
for i in range(n):
  y = int(a*(i+1)/b) - a*int((i+1)/b)
  x.append(y)

z = sorted(x)
print(z[-1])

### FIXED CODE ###

a,b,n=map(int,input().split())
x=min(b-1,n)
print((a*x)//b-a*(x//b))
### BUGGY CODE ###

a=[]
b={1:"b",2:"a"}

max=0

for _ in range (int(input())):
    a.append(input())
for item in a:
    if(max<a.count(item)):
        b.clear()
        max=a.count(item)
        b[item]=item
        
    elif (max==a.count(item)):
         
        b[item]=item

for item in sorted(b.values()):
    print(item)

### FIXED CODE ###

n = int(input())
dic = {}
for i in range(n):
    s = input()
    try:
        dic[s] += 1
    except:
        dic[s] = 1
high=max(dic.values())
val= sorted(dic.items())
for i in val:
    if(i[1]==high):
        print(i[0])
### BUGGY CODE ###

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

def solve_knapsack(capacity):
    # basic checks
 
    
    # populate the capacity = 0 columns, with '0' capacity we have '0' profit
    dp = [0]*(W + 1)
    weights, profits = [0]*(N+1), [0]*(N+1)
    for i in range(0, N):
        weights[i],profits[i] = map(int,input().split())
    

    for i in range(0, N):
        for c in range(capacity, weights[i]-1, -1):
            dp[c] = max(dp[c], profits[i] + dp[c - weights[i]])
 
    # maximum profit will be at the bottom-right corner.
    return dp[capacity]
  
def main():
    
 
    res = solve_knapsack(W)
 
    print(res)
if __name__ == "__main__":
	main()

### FIXED CODE ###

def main():
  n, w = [int(e) for e in input().split()]
  t = [-1 for i in range(w + 1)]
  t[w] = 0
  for _ in range(n):
    nw, nv = [int(e) for e in input().split()]
    for i in range(nw, w + 1):
      if t[i] == -1:
        continue
      if t[i - nw] < t[i] + nv:
        t[i - nw] = t[i] + nv
  print(max(t))
main()
### BUGGY CODE ###

N=int(input())
ans=10**12
for  x in range(1,N+1):
    if N%x==0:
        if (x+int((N/x)-2))<ans:
            ans=(x+int((N/x))-2)
print(ans)

### FIXED CODE ###

N=int(input())
ans=10**12
for  x in range(1,int((N)**0.5+1)):
    if N%x==0:
        if (x+int((N/x)-2))<ans:
            ans=(x+int((N/x))-2)
print(ans)
### BUGGY CODE ###

import sys
from collections import deque

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

input = sys.stdin.readline
n = int(input())
a_que = deque(list(map(int, input().split())))
ans = 1
for _ in range(n):
    out = a_que.popleft()
    m = 0
    for a in a_que:
        m = gcd(m, a)
    ans = max(ans, m)
    a_que.append(out)
print(ans)


### FIXED CODE ###

import sys

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

input = sys.stdin.readline
n = int(input())
a_list = list(map(int, input().split()))
l_list = [0]
r_list = [0]
l_gcd, r_gcd = 0, 0
for i in range(n-1):
    l_gcd = gcd(l_gcd, a_list[i])
    l_list.append(l_gcd)
    r_gcd = gcd(r_gcd, a_list[-i-1])
    r_list.append(r_gcd)
ans = 1
for i in range(n):
    ans = max(ans, gcd(l_list[i], r_list[-i-1]))
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
a = list(map(int, input().split()))
A = []
Index = 0

def getRate(list, int1, int2):
    value = 1
    for i in range(int1, int2):
        value = value * list[i]
    return value

for i in range(N-K+1):
    A.append(getRate(a, i, K + i))

for i in range(len(A)-1):
    if A[i] < A[i+1]:
        print("Yes")
    else:
        print("No")


### FIXED CODE ###

N, K = map(int, input().split())
a = list(map(int, input().split()))

ans = []
flag = 1
for i in range(N):
    if a[i] < a[i + K]:
        print('Yes')
    else:
        print("No")
    flag += 1
    if flag == N-K+1:
        break
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
http://abc062.contest.atcoder.jp/tasks/arc074_b

"""
import sys
from sys import stdin
from heapq import heappop, heappush
input = stdin.readline


def solve(A, N):
    red_pq = []
    blue_pq = []

    for a in A[:N]:
        heappush(red_pq, a)
    red_total = sum(A[:N])

    temp = A[N:]
    temp.sort()
    blue_total = sum(temp[:N])
    best_ans = red_total - blue_total


    for k in range(N, 2*N):
        t1 = A[k]
        heappush(red_pq, t1)
        t2 = heappop(red_pq)
        red_total += (t1 - t2)

        temp = A[k+1:]
        temp.sort()
        blue_total = sum(temp[:N])

        ans = red_total - blue_total
        best_ans = max(best_ans, ans)

    return best_ans


def main(args):
    N = int(input())
    A = [int(x) for x in input().split()]
    result = solve(A, N)
    print(result)


if __name__ == '__main__':
    main(sys.argv[1:])


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
http://abc062.contest.atcoder.jp/tasks/arc074_b

"""
import sys
from sys import stdin
from heapq import heappop, heappush
input = stdin.readline


def solve(A, N):
    red_pq = []
    blue_pq = []

    for a in A[:N]:
        heappush(red_pq, a)
    red_total = sum(A[:N])

    blue_total = 0
    for a in A[2*N:]:
        heappush(blue_pq, -a)
        blue_total += a

    blue_lut = [0] * (3*N)
    blue_lut[2*N] = blue_total
    for k in range(2*N - 1, N - 1, -1):
        t1 = A[k]
        heappush(blue_pq, -t1)
        t2 = heappop(blue_pq)
        blue_total += (t1 + t2)
        blue_lut[k] = blue_total

    best_ans = red_total - blue_total

    for k in range(N, 2*N):
        t1 = A[k]
        heappush(red_pq, t1)
        t2 = heappop(red_pq)
        red_total += (t1 - t2)

        ans = red_total - blue_lut[k+1]
        best_ans = max(best_ans, ans)

    return best_ans


def main(args):
    N = int(input())
    A = [int(x) for x in input().split()]
    result = solve(A, N)
    print(result)


if __name__ == '__main__':
    main(sys.argv[1:])