Harryxun/stf_run huggingface dataset:
from math import gcd
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

a,b = map(int,input().split())
c = gcd(a,b)
d = factorization(c)
print(len(d)+1-(c==1))

### FIXED CODE ###

from fractions import gcd
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

a,b = map(int,input().split())
c = gcd(a,b)
d = factorization(c)
print(len(d)+1-(c==1))
n, m = map(int, input().split())
A = list(map(int, input().split()))
A = sorted(A, reverse=True)

while m > 0:
    A[0] = A[0]//2
    m -= 1
    if A[0] < A[1]:
        A = sorted(A, reverse=True)

print(sum(A))

### FIXED CODE ###

import heapq

n, m = map(int, input().split())
A = sorted(list(map(lambda x: int(x)*(-1), input().split())))

heapq.heapify(A)

for i in range(m):
    a = heapq.heappop(A)
    a = a * (-1) // 2
    heapq.heappush(A, -a)

print(-sum(A))
N,K = map(int,input().split())
a = list(map(int,input().split()))
b = set(a)
c = [a.count(i) for i in b]
d = len(b)
ans = 0
for i in c:
  if K >= d:
    break
  ans += i
  d -= 1
  print(c[i])
print(ans)


### FIXED CODE ###

import sys
import collections
input = sys.stdin.readline

N,K = map(int,input().split())
a = list(map(int,input().split()))
c = collections.Counter(a)
d = len(c)
ans = 0
c_sorted = sorted(c.items(),key = lambda x:x[1])
for i in c_sorted:
    if K >= d:
        break
    ans += i[1]
    d -= 1
print(ans)
import sys
input = sys.stdin.readline
import bisect


def main():
    N, Q = [int(x) for x in input().split()]
    S = input().strip()

    ac = []
    for i, s in enumerate(S):
        if s == 'A' and S[i + 1] == 'C':
            ac.append(i)

    for _ in range(Q):
        x, y = [int(x) for x in input().split()]
        l = bisect.bisect_left(ac, x - 1)
        r = bisect.bisect_right(ac, y - 2)
        print(r - l)

    
    




if __name__ == '__main__':
    main()




### FIXED CODE ###

import sys
input = sys.stdin.readline
import bisect


def main():
    N, Q = [int(x) for x in input().split()]
    S = input().strip()

    ac = []
    for i in range(len(S) - 1):
        if S[i] == 'A' and S[i + 1] == 'C':
            ac.append(i)

    for _ in range(Q):
        x, y = [int(x) for x in input().split()]
        l = bisect.bisect_left(ac, x - 1)
        r = bisect.bisect_right(ac, y - 2)
        print(r - l)

    
    




if __name__ == '__main__':
    main()
x=input()
a=[1]
for i in range(1,len(x)):
    if x[i]==x[i-1]:
        a[-1]+=1
    else:a+=[1]
ans=0    
if x[0]=="T":
    ans+=a.pop(0)
if x[-1]=="S":
    ans+=a.pop(-1)
    
while len(a)>1:
    a=[i-j for i,j in zip(a[::2],a[1::2]) if i!=j]
    if a and a[0]<0:
            ans-=a.pop(0)
    if a and [-1]>0:
            ans+=a.pop(-1)
    a=[abs(i) for i in a if i!=0]
print(ans+abs(a[0]) if a else ans)

### FIXED CODE ###

a=[]
for i in input():
    if i=="S":
        a+=i
    
    if a:
        if i=="T" and a[-1]=="T":
            a+=i
        if i=="T" and a[-1]=="S":
            a.pop(-1)
    elif i=="T" and len(a)==0:
        a+=i    
print(len(a))
input_1 = input()
mylist = list(map(int, input_1.split(" ")))
H = mylist[0]
A = mylist[1]
if H % A =! 0:
  answer = H//A + 1
else:
  anser = H//A
print(answer)


### FIXED CODE ###

input_1 = input()
mylist = list(map(int, input_1.split(" ")))
H = mylist[0]
A = mylist[1]
if H % A != 0:
  answer = H//A + 1
else:
  answer = H//A
print(answer)
from itertools import permutations
import math
from functools import reduce

N, X = map(int, input().split())
xi = map(int, input().split())

dist = [abs(X - x) for x in xi]
print(reduce(math.gcd, dist))

### FIXED CODE ###

from functools import reduce
from fractions import gcd

N, X = map(int, input().split())
xi = map(int, input().split())

dist = [abs(X - x) for x in xi]
print(reduce(gcd, dist))
import numpy as np
l,r = map(int, input().split())
if (l-1//2019)<(r//2019):
  print(0)
else:
  arr1 = np.array(range(l,r+1))
  arr2 = np.array(range(l,r+1)).reshape(r-l+1,1)
  arr = arr1*arr2%2019
  for i in range(r-l+1):
    arr[i][i] = 2019
  print(np.min(arr))

### FIXED CODE ###

import numpy as np
l,r = map(int, input().split())
if ((l//2019)<(r//2019)):
  print(0)
else:
  arr1 = np.array(range(l,r+1))
  arr2 = np.array(range(l,r+1)).reshape(r-l+1,1)
  arr = arr1*arr2%2019 + (np.identity(r-l+1)*2019)
  print(int(np.min(arr)))
n,m = map(int,raw_input().split())

arr = []
for i in range(n):
	arr.append(map(int,raw_input().split()))


ans = float('-inf')

def check(k,o,f,p,i):
	global ans,m,n
	if i < n:

		if p < m:
			check(k+arr[i][0],o+arr[i][1],f+arr[i][2],p+1,i+1)

		check(k,o,f,p,i+1)

	if p == m:
		ans = max(ans,abs(k)+abs(o)+abs(f))


check(0,0,0,0,0)

print ans

### FIXED CODE ###

n,m = map(int,raw_input().split())

arr = []

for i in range(n):
	arr.append(map(int,raw_input().split()))

v = [[1,1,1],[1,1,-1],[1,-1,-1],[1,-1,1],[-1,-1,-1],[-1,1,1],[-1,1,-1],[-1,-1,1]]

ans = 0

for i in range(8):
	tmp = []
	for j in range(n):
		tmp.append(arr[j][0] * v[i][0] + arr[j][1] * v[i][1] + arr[j][2] * v[i][2])

	tmp.sort()
	ans = max(ans,sum(tmp[n-m:]))

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

print(cnt)
    

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
cnt=0
for i in range(0,n):
  if a[i]>=b[i]:
    cnt+=b[i]
    b[i]=0
  else:
    cnt+=a[i]
    if b[i]-a[i]<=a[i+1]:
      cnt+=b[i]-a[i]
      a[i+1]-=(b[i]-a[i])
    else:
      cnt+=a[i+1]
      a[i+1]=0
 
print(cnt)
n,m=(int(i) for i in input().split(' '))
i=n
while True:
  if m%i==0:
    if m//i>=n:
      print(i)
    break
  else:
    i-=1


### FIXED CODE ###

N = int(input())
if N == 1:
    print('Hello World')
elif N == 2:
    A = int(input(''))
    B = int(input(''))
    print(A + B)
import sys

chash = {}
for i in range( ord( 'a' ), ord( 'z' ) ):
	chash[ chr( i ) ] = 0

lines = sys.stdin.readlines().rstrip()
for i in range( len( lines ) ):
	for j in range( len( lines[i] ) ):
		if lines[i][j].isalpha():
			chash[ lines[i][j].lower() ] += 1

for i in range( ord( 'a' ), ord( 'z' ) ):
	print( "{:s} : {:d}".format( chr( i ), chash[ chr( i ) ] ) )

### FIXED CODE ###

import sys
 
chash = {}
for i in range( ord( 'a' ), ord( 'z' )+1 ):
    chash[ chr( i ) ] = 0
 
while True:
    line = sys.stdin.readline().rstrip()
    if not line:
        break
    for i in range( len( line ) ):
        if line[i].isalpha():
            chash[ line[i].lower() ] += 1
 
for i in range( ord( 'a' ), ord( 'z' )+1 ):
    print( "{:s} : {:d}".format( chr( i ), chash[ chr( i ) ] ) )
h,w=map(int,input().split())
box=[list(input()) for i in range(h)]
count=h*w-(w+h-1)
for i in range(h):
    for j in range(w):
        if box[i][j]=="#":
            count -=1

another_box=[["#"]+box[i]+["#"] for i in range(h)]
another_box.insert(0,["#"]*(w+2))
another_box.append(["#"]*(w+2))
another_box[h][w]="G"

def maper(another_box,strat_x,strat_y):
    another_box[strat_x][strat_y]="#"
    for xx,yy in [[0,1],[0,-1],[1,0],[-1,0]]:
        n_x,n_y=strat_x+xx,strat_y+yy
        if another_box[n_x][n_y]==".":
            maper(another_box,n_x,n_y)
        elif another_box[n_x][n_y]=="G":
            another_box[n_x][n_y]="C"
    return another_box

flag=0
answer_box=maper(another_box,1,1)
for i in range(h+2):
    for j in range(w+2):
        if answer_box[i][j]=="C":
            flag=1

if flag==1:print(count)
else:print("-1")

### FIXED CODE ###

h,w=map(int,input().split())
b=[["#"]*(w+2)]
a=0
for i in range(h):
  c=["#"]
  for j in input():
    a+=j=="#"
    c.append(j)
  b.append(c+["#"])
b+=[["#"]*(w+2)]
b[h][w]=0
Q=[(1,1)]
x=0
y=-1
while Q:
	x+=1
	p=[]
	for i,j in Q:
		for dx,dy in [(1,0),(-1,0),(0,1),(0,-1)]:
			if b[i+dx][j+dy]==".":
				p+=[(i+dx,j+dy)]
				b[i+dx][j+dy]="#"
			elif b[i+dx][j+dy]==0:
				y=x
	if y>0:break
	Q=p
if y>0:print((h*w)-a-y-1)
else:print(-1)
import sys
from math import gcd
# from fractions import gcd

input = sys.stdin.readline

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

n = gcd(A,B)

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

frl = factorization(n)
if frl[0][0]==1:
	ans = 1
else:
	ans = len(frl)+1
print(ans)

### FIXED CODE ###

import sys
# from math import gcd
from fractions import gcd

input = sys.stdin.readline

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

n = gcd(A,B)

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

frl = factorization(n)
if frl[0][0]==1:
	ans = 1
else:
	ans = len(frl)+1
print(ans)
C,D=map(int,input().split())
print("Left" if A+B > C+D else "Balanced" if A+B == C+D else "Right")

### FIXED CODE ###

A,B,C,D=map(int,input().split())
print("Left" if A+B > C+D else "Balanced" if A+B == C+D else "Right")
a=int(input())
   for i in range(a):
     print("Hello World")


### FIXED CODE ###

n=input().split()
a=int(n[0])
b=int(n[1])
if a > b:
    print("a > b")
elif a < b:
    print("a < b")
else:
    print("a == b")
i=input();print(i**3)

### FIXED CODE ###

print(int(input())**3)
n = int(input())
p = list(map(int,input().split()))
cnt = 0
for i in range(n):
  if p[i] != (i+1):
    cnt += 1
print("YES" if cnt == 0 or cnt == 2 else "NO") 

### FIXED CODE ###

A,B = map(int, input().split())
if (A + B) % 2 == 0 :
  print ((A + B) // 2)
else :
  print ("IMPOSSIBLE")
from django.template.defaultfilters import first

while True:
    N = int(input())
    if N == 0:
        break
    
    first_group_menbers = set(input()[:-1].split(":")[1].split(","))
    
    d = {}
    for i in range(N-1):
        group, members = input()[:-1].split(":")
        d[group] = set(members.split(","))
        
    for i in range(N):
        for group, members in d.items():
            if group in first_group_menbers:
                first_group_menbers.remove(group)
                for m in members:
                    first_group_menbers.add(m)
    
    print(len(first_group_menbers))

### FIXED CODE ###

while True:
    N = int(input())
    if N == 0:
        break
    
    first_group_menbers = set(input()[:-1].split(":")[1].split(","))
    d = {}
    for i in range(N-1):
        group, members = input()[:-1].split(":")
        d[group] = set(members.split(","))
        
    for i in range(N-2):
        for group, members in d.items():
            if group in first_group_menbers:
                first_group_menbers.remove(group)
                for m in members:
                    first_group_menbers.add(m)
    
    print(len(first_group_menbers))
x**3

### FIXED CODE ###

x = int(input())
print(x**3)
s = input()
t = input()
ans = []
for i in range(len(s)-len(t)):
    S = s[i:i+len(t)]
    cnt = 0
    for j in range(len(t)):
        if t[j] == S[j]:
            cnt += 1
    ans.append(cnt)

a = ans.index(max(ans))
b = s[a:a+len(t)]
count = 0
for k in range(len(t)):
    if t[k] != b[k]:
        count += 1
print(count)
    

### FIXED CODE ###

s = input()
t = input()
ans = []
for i in range(len(s)-len(t)+1):
    S = s[i:i+len(t)]
    cnt = 0
    for j in range(len(t)):
        if t[j] == S[j]:
            cnt += 1
    ans.append(cnt)

a = ans.index(max(ans))
b = s[a:a+len(t)]
count = 0
for k in range(len(t)):
    if t[k] != b[k]:
        count += 1
print(count)
#n = int(input())
#n,k = map(int,input().split())
#x = list(map(int,input().split()))


s = list(input())
ans = True
li = list("abcdefghijklmnopqrstuvwxyzC")

if s[0]!="A":
    ans = False
memo = s[2:-1]
if not("C" in memo):
    ans = False
C_cnt = 0
for i in range(1,len(li)):
    if not(memo[i] in li):
        ans = False
    if memo[i] == "C":
        C_cnt += 1

if ans and C_cnt==1:
    print("AC")
else:
    print("WA")










### FIXED CODE ###

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


s = list(input())
ans = True
li = list("abcdefghijklmnopqrstuvwxyzC")

if s[0]!="A":
    ans = False
memo = s[2:-1]
if not("C" in memo):
    ans = False
C_cnt = 0
for i in range(1,len(s)):
    if not(s[i] in li):
        ans = False
    if s[i] == "C":
        C_cnt += 1

if ans and C_cnt==1:
    print("AC")
else:
    print("WA")
import math
n = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort(reverse=True)
M=n[1]
def kyoukai(lis,m):
    s=0
    for i in range(n[0]):
        s+=math.log2(lis[i])
        if s>=m*2:
            boundary=i+1
            break
    return boundary
d=kyoukai(a,M)
k=0
while k!=1:
    for i in range(d):
        a[i]=int(a[i]/2)
    if M-d>0:
        M-=d
        d=kyoukai(a,M)
    else:
        break
print(sum(a))

### FIXED CODE ###

import heapq

N, M= map(int, input().split())
A = list(map(int, input().split()))
a=[-1*i for i in A]
heapq.heapify(a)
for i in range(M):
    m=int(heapq.heappop(a)/2)
    heapq.heappush(a, m)

print(-1*sum(a))
from sys import stdin
from collections import deque
V, E = map(int, stdin.readline().split())
adj_list = [[] for _ in [] * V]
is_visited = [False] * V
for _ in [0] * E:
    s, t = map(int, stdin.readline().split())
    adj_list[s].append(t)
out = deque()
def dfs(u):
    is_visited[u] = True
    for v in adj_list[u]:
        if not is_visited[v]:
            dfs(v)
    out.appendleft(u)
for s in range(V):
    if not is_visited[s]:
        dfs(s)
print(*out, sep='\n')

### FIXED CODE ###

from sys import stdin
from collections import deque
V, E = map(int, stdin.readline().split())
adj_list = [[] for _ in [0] * V]
is_visited = [False] * V
for _ in [0] * E:
    s, t = map(int, stdin.readline().split())
    adj_list[s].append(t)
out = deque()
def dfs(u):
    is_visited[u] = True
    for v in adj_list[u]:
        if not is_visited[v]:
            dfs(v)
    out.appendleft(u)
for s in range(V):
    if not is_visited[s]:
        dfs(s)
print(*out, sep='\n')
N=input()
List=[int(i) for i in input().split()]
count=0
for i in range(N):
  if i != List[i]:
    count += 1
if count <=2:
  print("YES")
else:
  print("NO")
    

### FIXED CODE ###

n = int(input())
p = list(map(int,input().split()))
count = 0
for i in range(n):
    if p[i] != i + 1:
        count += 1
if count <= 2:
    print('YES')
else:
    print('NO')
n = [ input() for _ in range( int( input() ) )]
m = [ input() for = in range( int( input() ) )]
l = list( set(n) )
print( max( 0, max( n.count(l[i]) - m.count(l[i]) for i in range( len(l) ) ) ) )
        
                              

### FIXED CODE ###

n=[input() for _ in range(int(input()))]
m=[input() for _ in range(int(input()))]
l=list(set(n))
print(max(0,max(n.count(l[i])-m.count(l[i]) for i in range(len(l)))))
N,M = map(int,input().split())
LRD = list(list(map(int,input().split())) for i in range(M))
#print(LRD)
d = {LRD[0][0]:0}

for i in range(M):
    if (LRD[i][0] in d) and (LRD[i][1] not in d):
          d[LRD[i][1]] = d[LRD[i][0]]+LRD[i][2]
    elif (LRD[i][0] in d) and (LRD[i][1] in d):
        if d[LRD[i][1]] != d[LRD[i][0]]+LRD[i][2]:
            print("No")
            exit()
    elif (LRD[i][0] not in d) and (LRD[i][1] in d):
        d[LRD[i][0]] = d[LRD[i][1]] - LRD[i][2]
    else:
        d[LRD[i][0]] = 0
        d[LRD[i][1]] = d[LRD[i][0]] + LRD[i][2]

print("Yes")

### FIXED CODE ###

import itertools
import math
from collections import deque
from collections import defaultdict
from itertools import permutations
import heapq
import bisect
from scipy.sparse.csgraph import floyd_warshall as wf
INF = float("inf")


N,M = map(int,input().split())
Adj_list = defaultdict(set)

for i in range(M):
    a, b, c = map(int, input().split())
    Adj_list[a-1].add((b-1, c))
    Adj_list[b-1].add((a-1, -c))
visited =[None]*(N)
ok = True
stack = []
for x in range(N):
   if visited[x] is not None:continue
   visited[x] = 0
   stack = [x]
   while stack:
       v = stack.pop()
       for to,d in Adj_list[v]:
           if visited[to] is None:
               visited[to] = visited[v] + d
               stack.append(to)
           else:
               if visited[to] != visited[v]+d:
                   ok = False
                   break
   if ok == False:
        break
print("Yes" if ok else "No")
s=input();print(min(abs(int(s[i:i+3])-753)for i in range(7)))

### FIXED CODE ###

s=input();print(min(abs(int(s[i:i+3])-753)for i in range(len(s)-2)))
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

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():
    N, M = LI()
    pairs = []
    used = [0 for _ in range(N)]
    cur = 0
    for gap in range(1, M+1):
        while used[cur] or used[(cur + gap) % N]:
            cur += 1
        pairs.append((cur, cur + gap))
        used[cur] = 1
        used[(cur+gap) % N] = 1
    for p in pairs:
        print(p[0]+1, p[1]+1)



main()



### FIXED CODE ###

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

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

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():
    N, M = LI()
    used = [0 for _ in range(N)]
    cur = 0
    pairs = []
    used = set()
    if N % 2 == 0:
        a = 1
        b = N
        while len(pairs) < M:
            if b-a in used or N + a -b in used or b - a == N//2:
                b -= 1
            pairs.append((a, b))
            used.add(b-a)
            used.add(N+a - b)
            a += 1
            b -= 1

    else:
        a = 1
        b = N - 1
        while len(pairs) < M:
            pairs.append((a, b))
            a += 1
            b -= 1
    for p in pairs:
        print(p[0], p[1])



main()
N, Y = map(int, input().split())
flag = True
for x in range(N+1):
    for y in range(N+1):
        z = N-x-y
        if 10000*x + 5000*y + 1000*z == Y:
            print(str(x) + ' ' + str(y) + ' ' + str(z))
            flag = False
            break
            
    if not flag:
        break
    
if baloon:
  print('-1 -1 -1')

### FIXED CODE ###

N, Y = map(int, input().split())
flag = True
for x in range(N+1):
    for y in range(N+1):
        z = N-x-y
        if z>=0 and 10000*x + 5000*y + 1000*z == Y:
            print(str(x) + ' ' + str(y) + ' ' + str(z))
            flag = False
            break
            
    if not flag:
        break
    
if flag:
    print('-1 -1 -1')
n = int(input())
a = list(map(int,input().split()))

for i in range(n-1):
    if a[i] <= 0 and a[i+1] <= 0:
        a[i] = -a[i]
        a[i+1] = -a[i+1]
        
for i in range(n-2):
    if a[i] < 0 and a[i+1] >= 0 and a[i+2] <= 0:
        a[i] = -a[i]
        a[i+2] = -a[i+2]
        
for i in range(n-1):
    if a[i] < 0:
        if a[i]+a[i+1] < -(a[i]+a[i+1]):
            a[i] = -a[i]
            a[i+1] = -a[i+1]

if a[n-1]+a[n] < -(a[n-1]+a[n]):
    a[n-1] = -a[n-1]
    a[n] = -a[n]

print(sum(a))

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
dp_table = [0, -10 ** 10]
temp = [0,0]
for i in range(n):
    temp[0] = dp_table[0]
    temp[1] = dp_table[1]
    dp_table[0] = max(temp[0]+a[i],temp[1]-a[i])
    dp_table[1] = max(temp[0]-a[i],temp[1]+a[i])
    
print(dp_table[0])
import sys
input = sys.stdin.readlin

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

### FIXED CODE ###

import sys,heapq
#これを加える！！！！
def _heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)
def _heappop_max(heap):
    """Maxheap version of a heappop."""
    lastelt = heap.pop()    # raises appropriate IndexError if heap is empty
    if heap:
        returnitem = heap[0]
        heap[0] = lastelt
        heapq._siftup_max(heap, 0)
        return returnitem
    return lastelt

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

res = [0]*(n+1)
head = a[:n:]
heapq.heapify(head)
p = sum(head)
for i in range(n+1):
    res[i] = p
    p += a[n+i]
    heapq.heappush(head,a[n+i])
    p -= heapq.heappop(head)
end = a[2*n::]
heapq._heapify_max(end)
q = sum(end)
for i in range(n+1):
    res[n-i] -= q
    q += a[2*n-1-i]
    _heappush_max(end,a[2*n-1-i])
    q -= _heappop_max(end)
print(max(res))
def main():
    n,k=map(int,input().split())
    A = map(int,input().split())

    def prod(iterables):
        res = None
        for element in iterables:
            tmp = 1
            for e in element:
                tmp *= e
            if res is None or tmp > res:
                res = tmp
        return res
    
    pos, neg = [], []
    for a in A:
        if a >= 0:
            pos.append(a)
        else:
            neg.append(a)

    pos_n, neg_n = len(pos), len(neg)
    ans = None

    for i in range(neg_n):
        if k-i > pos_n:
            continue
        tmp = prod(permutations(neg, i)) * prod(permutations(pos, k-i)) % (10**9+7)
        if ans is None or tmp > ans:
            ans = tmp
    print(ans)
main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    n,k = map(int, input().split())
    A = sorted(map(int, input().split()))
    mod = 10**9 + 7
    ans, sign = 1, 1

    l, r = 0, n-1

    if k%2:
        ans = A[r]
        r-=1
        k-=1
        if ans < 0:
            sign = -1
    while k:
        x = A[l]*A[l+1]
        y = A[r]*A[r-1]

        if x*sign > y*sign:
            ans = x%mod * ans%mod
            l+=2
        else:
            ans = y%mod * ans%mod
            r-=2
        k-=2
    print((ans+mod)%mod)
main()
import numpy as np
q = list(map(int, input().split()))
w= list(map(int, input().split()))
memo=0
a=0
x=np.array(w)
k=max(np.sum(x[i:i+q[1]]))
 
print((a+q[1])/2)

### FIXED CODE ###

n,k= list(map(int, input().split()))
j = list(map(int, input().split()))
s=0
sumlist=[0]*(n+1)
anslist=[0]*(n-k+1)
for i in range(n):
    s+=j[i]
    sumlist[i+1]=s
for i in range(len(anslist)):
     z=sumlist[i+k]-sumlist[i]
     anslist[i]=z
ans=max(anslist)
ans+=k
ans=ans/2
print(ans)