Harryxun/stf_run huggingface dataset:
N,M = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
B = [0 for i in range(10**5+1)]
S = [0]
s = 0
for i in range(N):
    B[A[i]] += 1
    s += A[i]
    S.append(s)
for i in range(2,10**5+2):
    B[-i] += B[-i+1]
d = 0
u = 2*10**5
for i in range(30):
    x = (u+d)//2
    if i == 30:
        x += 1
    m = 0
    for i in range(N):
        a = A[i]
        y = max(x - a,0)
        if y <= 10**5:
            m += B[y]
    if m >= M:
        d = x
    else:
        u = x
ans = 0
for i in range(N):
    a = A[i]
    x = max(d - a,0)
    if x <= 10**15:
        y = B[x]
    else:
        y = 0
    ans += (S[N] - S[N-y]) + a*y
ans -= (m-M)*d
print(ans)

### FIXED CODE ###

N,M = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
B = [0 for i in range(10**5+1)]
S = [0]
s = 0
for i in range(N):
    B[A[i]] += 1
    s += A[i]
    S.append(s)
for i in range(2,10**5+2):
    B[-i] += B[-i+1]
d = 0
u = 2*10**5
for i in range(30):
    x = (u+d)//2
    if i == 28:
        x += 1
    m = 0
    for i in range(N):
        a = A[i]
        y = max(x - a,0)
        if y <= 10**5:
            m += B[y]
    if m >= M:
        d = x
    else:
        u = x
ans = 0
for i in range(N):
    a = A[i]
    x = max(d - a,0)
    if x <= 10**5:
        y = B[x]
    else:
        y = 0
    ans += (S[N] - S[N-y]) + a*y
ans -= (m-M)*d
print(ans)
n = int(input())
dic = {}
for i in range(n):
  s = input()
  if s in dic.keys():
    dic[s] += 1
  else:
    dic[s] = 1

m = int(input())
for i in range(n):
  t = input()
  if t in dic.keys():
    dic[t] -= 1
    
ans = 0
for key in dic.keys():
  ans = max(ans, dic[key])
  
print(max(ans, 0))
  

### FIXED CODE ###

n = int(input())
dic = {}
for i in range(n):
  s = input()
  if s in dic.keys():
    dic[s] += 1
  else:
    dic[s] = 1

m = int(input())
for i in range(m):
  t = input()
  if t in dic.keys():
    dic[t] -= 1
    
ans = 0
for key in dic.keys():
  ans = max(ans, dic[key])
  
print(max(ans, 0))
A,B=map(int,input().split())
print("GREATER"if A>B else"LESS"if A<B else"EQUAL")

### FIXED CODE ###

A,B=int(input()),int(input())
print("GREATER"if A>B else"LESS"if A<B else"EQUAL")
n,k=map(int,input().split())
A=list(map(int,input().split()))


if k>=n:
  print(abs(A[k-1]-A[0]))
else:
  dp=list(range(n))
  for i in range(k):
    dp[i]=abs(A[i]-A[0])
  for i in range(n-k):
    temp=list(range(k))
    for j in range(k):
      temp[j-1]=dp[i]+abs(A[i+k]-A[i])
      dp[i+k]=min(temp)
  print(dp[n-1])

### FIXED CODE ###

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

if k>=n:
  print(abs(A[n-1]-A[0]))
else:
  dp=list(range(n))
  for i in range(k):
    dp[i]=abs(A[i]-A[0])
  for i in range(n-k):
    temp=list(range(k))
    for j in range(k):
      temp[j]=dp[i+j]+abs(A[i+k]-A[i+j])
    dp[i+k]=min(temp)
  print(dp[n-1])
print(int(input()[1:]))

### FIXED CODE ###

n = int(input())%1000
if n:
    print(1000-n)
else:
    print(n)
N=int(input())
A=list(map(int,input().split()))
UV=[list(map(int,input().split())) for i in range(N-1)]
c=[[] for i in range(N)]
for i,j in UV:
    c[i-1].append(j-1)
    c[j-1].append(i-1)
v=[0]*N
d=[10**9+1]*N
stk=[]
ans=[0]*N
from bisect import bisect_left
def dfs(p,l):
    i=bisect_left(d,A[p])
    stk.append((i,d[i]))
    d[i]=A[p]
    if i==l:
        l+=1
    ans[p]=l
    for n in c[p]:
        if v[n]==0:
            v[n]=1
            dfs(n,l)
    i,x=stk.pop()
    d[i]=x
v[0]=1
dfs(0,0)
print(*ans,sep='\n')

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
UV=[list(map(int,input().split())) for i in range(N-1)]
c=[[] for i in range(N)]
for i,j in UV:
    c[i-1].append(j-1)
    c[j-1].append(i-1)
v=[0]*N
d=[10**9+1]*N
stk=[]
ans=[0]*N
from bisect import bisect_left
import sys
sys.setrecursionlimit(10**9)
def dfs(p,l):
    i=bisect_left(d,A[p])
    stk.append((i,d[i]))
    d[i]=A[p]
    if i==l:
        l+=1
    ans[p]=l
    for n in c[p]:
        if v[n]==0:
            v[n]=1
            dfs(n,l)
    i,x=stk.pop()
    d[i]=x
v[0]=1
dfs(0,0)
print(*ans,sep='\n')
def gcd(x, y):
    if x % y:
        return gcd(y, x % y)
    return y

def lcm(a, b):
    return int(a * b / gcd(a, b))

n = int(input())
a = sorted([int(i) for i in input().split()])
l = a[0]
for i in a[1:]:
    l = lcm(l, i)
print(sum(map(lambda x: (l - 1) % x, a)))


### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
print(sum(a) - n)
n = int(input())
ab = [tuple(map(int,input().split())) for i in range(n-1)]
es = [[] for i in range(n)]
for a,b in ab:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)

def dfs(v, parent, dist):
    if dist[v] == -1:
        dist[v] = dist[parent]+1
    for next_v in es[v]:
        if dist[next_v] == -1:
            dfs(next_v,v,dist)

dist0 = [-1] * n
dist0[0] = 0
dfs(0,-1,dist0)

distn = [-1] * n
distn[n-1] = 0
dfs(n-1,-1,distn)

count_f = 0
for i in range(n):
    if dist0[i] <= distn[i]:
        count_f+=1

if count_f > n-count_f: print('Fennec')
else: print('Snuke')


### FIXED CODE ###

n = int(input())

ab = [tuple(map(int,input().split())) for i in range(n-1)]
es = [[] for i in range(n)]
for a,b in ab:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)
INF = float('inf')
dist0 = [INF] * n
dist0[0] = 0
import heapq
hq = [(0,0)]
heapq.heapify(hq)
while hq:
    c,v = heapq.heappop(hq)
    for to in es[v]:
        if c+1 >= dist0[to]: continue
        dist0[to] = c+1
        heapq.heappush(hq,(c+1,to))

distn = [INF] * n
distn[n-1] = 0
hq = [(0,n-1)]
heapq.heapify(hq)
while hq:
    c,v = heapq.heappop(hq)
    for to in es[v]:
        if c+1 >= distn[to]: continue
        distn[to] = c+1
        heapq.heappush(hq,(c+1,to))


count_f = 0
for i in range(n):
    if dist0[i] <= distn[i]:
        count_f+=1

if count_f > n-count_f: print('Fennec')
else: print('Snuke')
N = int(input())

D = []
for i in range(N):
    Da,Db = (map(int,input().split()))
    if Da == Db:
        D.append(1)
    else:
        D.append(0)

for i in range(N-2):
    if D[i]==1 and D[i+1] == 1 and D[i+2] == 1:
        ans = "Yes"
        break:
    else:
        ans = "No"
print(ans)

### FIXED CODE ###

N = int(input())

D = []
for i in range(N):
    Da,Db = (map(int,input().split()))
    if Da == Db:
        D.append(1)
    else:
        D.append(0)

for i in range(N-2):
    if D[i]==1 and D[i+1] == 1 and D[i+2] == 1:
        ans = "Yes"
        break
    else:
        ans = "No"
print(ans)
import numpy as np
N = int(input())

edge = np.zeros((N,N))
color = [0] * (N)

for i in range(N-1) :
    u , v , w = map(int,input().split())
    edge[u-1,v-1] = w
    edge[v-1,u-1] = w

color[0] = 1
stack = [0]

while len(stack) > 0 :
    v = stack.pop() # 現在の頂点

    for i in range(N) :
        if edge[v][i] > 0 and color[i] == 0 : # 辺があり，色がついていない場合
            if edge[v][i] % 2 == 0 :
                color[i] = color[v]
            else :
                color[i] = color[v] * -1
            stack.append(i)

for i in range(N) :
    if color[i] == 1 :
        print('1')
    else :
        print('0')

### FIXED CODE ###

from collections import deque

N = int(input())

edge = [[] for _ in range(N)]
check = [False] * N
dist = [0] * N

for i in range(N-1) :
    u , v , w = map(int,input().split())
    edge[u-1].append((v-1,w))
    edge[v-1].append((u-1,w))

q = deque([0])

while q :
    current = q.popleft()
    if check[current] :
        continue

    check[current] = True
    for ad , w in edge[current] :
        if not check[ad] :
            q.append(ad)
            dist[ad] = dist[current] + w

for w in dist :
    print(w % 2)
N = int(input())
S = list(input())
f=0
ijk = list()
for i in range(N):
    for j in range(N):
        for k in range(N):
            if(i<j<k):
                if(S[i]==S[j]):
                    pass
                elif(S[i]==S[k]):
                    pass
                elif(S[j]==S[k]):
                    pass
                else:
                    ijk.append([i+1,j+1,k+1])
# print(ijk)
for i in range(len(ijk)):
    if(ijk[i][1]-ijk[i][0] == ijk[i][2]-ijk[i][1]):
        pass:
    else:
        f += 1
print(f)

### FIXED CODE ###

n=int(input())
s=input()
r=g=b=0
for i in s:
  if i=="R":r+=1
  elif i=="G":g+=1
  else:b+=1

ans=r*g*b
for i in range(n):
  for j in range(i+1,n):
    k_ = j+(j-i)
    if(k_ >=n):
      break
    ans -= int(s[i]!= s[j] and s[i] != s[k_] and s[j] != s[k_])

print(ans)
import math
A, B, C, D = map(int,input().split())
hpa = math.ceil(A / D)
hhb = math.ceil(C / B)
if (hpa >= hpb):
    print('Yes')
else:
    print('No')


### FIXED CODE ###

import math
A, B, C, D = map(int,input().split())
hpa = math.ceil(A / D)
hpb = math.ceil(C / B)
if (hpa >= hpb):
    print('Yes')
else:
    print('No')
import numpy as np
N,M,X = map(int, input().split())
nd_list = np.ones(M)*X

next_list = []
for i in range(0,N):
    next_list.append(list(map(int, input().split())))
next_list = np.array(next_list)
min_tot = 10000000

def dfs(i,ab_list):
    global min_tot
    if i==N and np.all(ab_list[1:]>=nd_list):
        if min_tot > ab_list[0]:
            min_tot = ab_list[0]
        return True
    elif i ==N:
        return True

    dfs(i+1,ab_list)
    dfs(i+1,ab_list+next_list[i,:])


if min_tot ==10000000:
    print(-1)
else:
    print(min_tot)

### FIXED CODE ###

import numpy as np
N,M,X = map(int, input().split())
nd_list = np.ones(M)*X

next_list = []
for i in range(0,N):
    next_list.append(list(map(int, input().split())))
next_list = np.array(next_list)
min_tot = 10000000

def dfs(i,ab_list):
    global min_tot
    if i==N and np.all(ab_list[1:]>=nd_list):
        if min_tot > ab_list[0]:
            min_tot = ab_list[0]
        return True
    elif i ==N:
        return True

    dfs(i+1,ab_list)
    dfs(i+1,ab_list+next_list[i,:])


dfs(0,np.zeros(1+M))
if min_tot ==10000000:
    print(-1)
else:
    print(int(min_tot))
from collections import Counter
N = int(input())
Dlist = list(map(int, input().split()))
DCounter = Counter(Dlist)
if DCounter[0] == 1 and Dlist[0] == 0:
    num = 1
    mae = 1
    for key, value in sorted(Dlist.items()):
        num *= (mae ** value)
        mae = value
        num %= 998244353
    print(num % 998244353)
else:
    print(0)


### FIXED CODE ###

from collections import Counter
N = int(input())
Dlist = list(map(int, input().split()))
DCounter = Counter(Dlist)
if DCounter[0] == 1 and Dlist[0] == 0:
    num = 1
    for i in range(1, max(Dlist) + 1):
        num *= DCounter[i - 1] ** DCounter[i]

    print(num % 998244353)
else:
    print(0)
!/work/yota509/env_python3/bin/python3                                                              
# -*- coding: utf-8 -*-                                                                              


def read_input():
    a,b,c=map(int, input().split())
    if 2<=a<=5 and 1<=b<=100 and b<c<=200:
        return a,b,c
    else :
        print("Error")
        exit()

def main():
    num = 10
    # r=None                                                                                         
    # d=None                                                                                         
    # x=None                                                                                         

    r,D,x=read_input()
    sum_x=x

    for i in range(num):
        sum_x=r*sum_x-D
        print(sum_x)
        sum_x=sum_x



if __name__ == "__main__":
    main()


### FIXED CODE ###

def read_input():
    a,b,c=map(int, input().split())
    if 2<=a<=5 and 1<=b<=100 and b<c<=200:
        return a,b,c
    else :
        print("Error")
        exit()

def main():
    num = 10

    r,D,x=read_input()
    sum_x=x

    for i in range(num):
        sum_x=r*sum_x-D
        print(sum_x)
        sum_x=sum_x



if __name__ == "__main__":
    main()
def samestring():
  N=int(input())
  S=list(input())
  if N % 2 != 0:
    print('No')
  else:
    S1 = S[0:int(N/2)]
    S2 = S[int(N/2):]

  if S1 == S2:
    print('{}'.format('Yes'))
  else:
    print('{}'.format('No'))

samestring()

### FIXED CODE ###

def samestring():
  N=int(input())
  S=list(input())
  if N % 2 != 0:
    print('No')
  else:
    S1 = S[0:int(N/2)]
    S2 = S[int(N/2):]

    if S1 == S2:
      print('{}'.format('Yes'))
    else:
      print('{}'.format('No'))

samestring()
from itertools import accumulate
n,k = list(map(int,input().split()))
p = list(map(int,input().split()))

P = list(accumulate([(i+1)/2 for i in p]))
ans = max([P[i+k]-P[i] for i in range(n-k)])
print(ans)

### FIXED CODE ###

from itertools import accumulate
n,k = list(map(int,input().split()))
p = list(map(int,input().split()))

P = list(accumulate([(i+1)/2 for i in p]))
P = [0] + P
ans = max([P[i+k]-P[i] for i in range(n-k+1)])
print(ans)
x,y=map(int(),input().split())
if(x==y):
  print("Yes")
else:
  print("No")

### FIXED CODE ###

x,y=map(int,input().split())
if(x==y):
  print("Yes")
else:
  print("No")
import math
def main():
    N, K = map(int, input().split())
    if K ==1:
        print(N+1)
    elif N % K == 0:
        print(math.ceil(math.log(N,K))+1)
    else:
        print(math.ceil(math.log(N,K)))


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    K, R = map(int, input().split())

    if K >=10:
        print(R)
    else:
        print(R + 100*(10-K))

if __name__ =='__main__':
    main()
A,B= [int(input()) for i in range(2)]  
OnlyA = A+(A-1)

OnlyB = B+(B-1)

AaddB = A + B

print(max([OnlyA,OnlyB,AaddB]))


### FIXED CODE ###

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

OnlyA = A+(A-1)

OnlyB = B+(B-1)

AaddB = A + B

print(max([OnlyA,OnlyB,AaddB]))
while True:
    Input = raw_input().split()
 
    a  = int(Input[0])
    op = Input[1]
    b  = int(Input[2])
 
    if   op == "+":
        ans = a + b
        print ans
    elif op == "-":
        ans = a - b
        print ans
    elif op == "/":
        ans = a / b
        print ans
    elif op == "*":
        ans = a * b
        print ans
    elif op == "?":
        break
 

 
Compile Error Logs: 

You are not authorized to see the message. 
 
 
Status 
Judge: 5/5  Python  CPU: 00.01 sec  Memory: 6436 KB  Length: 376 B  2016-01-27 11:43  2016-01-27 11:43  
Results for testcases 
Case # Verdict CPU Time Memory In Out Case Name 
 Case #1: : Accepted  00.01 sec 6344 KB 12 B 2 B test_case_1 
 Case #2: : Accepted  00.01 sec 6384 KB 30 B 9 B test_case_2 
 Case #3: : Accepted  00.00 sec 6240 KB 178 B 69 B test_case_3 
  

### FIXED CODE ###

while True:
    a, op, b = raw_input().split()
    if op == "?":
        break
    else:
        if op == '+':
            print int(a) + int(b)
        elif op == '-':
            print int(a) - int(b)
        elif op == '*':
            print int(a) * int(b)
        elif op == '/':
            print int(a) / int(b)
        else:
            print "error"
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
BC = [list(map(int, input().split())) for i in range(Q)]

def calc(A):
    ans = 0
    for i in range(len(A)):
        ans += A[i] * (i + 1)

    return ans



VALUE = [0 for i in range(100)]

for i in range(N):
    VALUE[A[i] - 1] += 1

for i in range(Q):
    VALUE[BC[i][1] - 1] += VALUE[BC[i][0] - 1]
    VALUE[BC[i][0] - 1] = 0
    print(calc(VALUE))


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
BC = [list(map(int, input().split())) for i in range(Q)]

def calc(A):
    ans = 0
    for i in range(len(A)):
        ans += A[i] * (i + 1)

    return ans

VALUE = [0 for i in range(100000)]

for i in range(N):
    VALUE[A[i] - 1] += 1

ANS = []
ANS.append(calc(VALUE))

for i in range(Q):
    VALUE[BC[i][1] - 1] += VALUE[BC[i][0] - 1]
    ANS.append(ANS[i] + (BC[i][1] - BC[i][0]) * VALUE[BC[i][0] - 1])
    VALUE[BC[i][0] - 1] = 0

for i in range(1, Q + 1):
    print(ANS[i])
s, t = input().split(" ")
a, b = (int(x) for x in input().split(" "))
u = input()
 
if s==u:
  print(s-1,t)
else:
  print(s,t-1)  

### FIXED CODE ###

s, t = input().split(" ")
a, b = (int(x) for x in input().split(" "))
u = input()
 
if s==u:
  print(a-1, b)
else:
  print(a, b-1)
import numpy as np
 
def main():
	n = int(input())
	s = input()
	q = int(input())
	klist = list(map(int, input().split()))
	
	for times in range(q):
		r = 0
		k = klist[times]
		nowd, nowm, nowdm = 0, 0, 0
		for i in range(n):
			c = s[i]
			if (c == "D"):
				nowd += 1
			elif (c == "M"):
				nowm += 1
				nowdm += nowd
			elif(c == "C"):
				r += nowdm
			if(i >= k-1):
				cc = s[i-k+1]
				if (cc == "D"):
					nowd -= 1
					nowdm -= nowm
				elif (cc == "M"):
					nowm -= 1
		print(r)
main()

### FIXED CODE ###

# your code goes here
import numpy as np

def main():
	n = int(input())
	a = list(map(int, input().split()))
	m = np.mean(a)
	r = 0
	
	for i in range(n):
		if ((a[i]-m)**2 < (a[r]-m)**2):
			r = i
	print(r)
	
main()
n = int(input())

ai = []
for i in range(n):
    ai.append(int(input()))

ai = sorted(ai, reverse=True)

alice = 0
bob = 0

for index, x in enumerate(ai):
    if (index % 2 == 0):
        alice += x
    else:
        bob += x
        
print(alice - bob)

### FIXED CODE ###

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

sorted_ai = sorted(ai, reverse=True)

alice = 0
bob = 0

for index, x in enumerate(sorted_ai):
    if (index % 2 == 0):
        alice += x
    else:
        bob += x
        
print(alice - bob)
N = int(input())
a = np.array(list(map(int, input().split())))
print(max(a) - min(a))

### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
print(max(a) - min(a))
import heapq
INF = 10 ** 16


def dijkstra(n, town, k, start):
    d = []
    queue = []
    for i in range(n):
        d.append(INF)
    d[start] = 0
    heapq.heappush(queue, (0, start))
    # 都市kで交換した時の円またはスヌークのの最小値
    while len(queue) != 0:
        distance, v = queue.pop()
        if d[v] < distance:
            continue
        for u in range(len(town[v])):
            if d[town[v][u][0]] > d[v] + town[v][u][k]:
                d[town[v][u][0]] = d[v] + town[v][u][k]
                heapq.heappaush(queue, (d[town[v][u][0]], town[v][u][0]))

    return d


def main():
    n, m, s, t = map(int, input().split())
    s -= 1
    t -= 1
    money = 10 ** 15
    town = []

    for i in range(n):
        town.append([])
    for i in range(m):
        fro, to, a, b = map(int, input().split())
        fro -= 1
        to -= 1
        town[fro].append((to, a, b))
        town[to].append((fro, a, b))

    a = dijkstra(n, town, 1, s)
    b = dijkstra(n, town, 2, t)

    total = []
    for i in range(n):
        heapq.heappush(total, (a[i] + b[i], i + 1))
    mon, year = heapq.heappop(total)
    for i in range(n):
        while year <= i:
            mon, year = heapq.heappop(total)
        print(money - mon)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from heapq import heapify, heappop, heappush


def dijkstra(n, train, start):
    d = []
    queue = []
    INF = 10 ** 16
    for i in range(n):
        d.append(INF)
    d[start] = 0
    heapify(queue)
    heappush(queue, (0, start))
    # 都市kに行く時の円またはスヌークのの最小値
    while len(queue) != 0:
        distance, v = heappop(queue)
        if d[v] < distance:
            continue
        for u in range(len(train[v])):
            if d[train[v][u][0]] > d[v] + train[v][u][1]:
                d[train[v][u][0]] = d[v] + train[v][u][1]
                heappush(queue, (d[train[v][u][0]], train[v][u][0]))
    return d


def main():
    n, m, s, t = map(int, input().split())
    s -= 1
    t -= 1
    money = 10 ** 15
    train_en = []
    train_snuuk = []

    for i in range(n):
        train_en.append([])
        train_snuuk.append([])
    for i in range(m):
        fro, to, a, b = map(int, input().split())
        fro -= 1
        to -= 1
        train_en[fro].append((to, a))
        train_en[to].append((fro, a))
        train_snuuk[fro].append((to, b))
        train_snuuk[to].append((fro, b))

    a = dijkstra(n, train_en, s)
    b = dijkstra(n, train_snuuk, t)

    cost_sum = []
    for i in range(n):
        cost_sum.append((a[i] + b[i], i + 1))
    heapify(cost_sum)
    m, y = heappop(cost_sum)
    for i in range(n):
        while y <= i:
            m, y = heappop(cost_sum)
        print(money - m)


if __name__ == '__main__':
    main()
n = [int(input()) for i in range(int(input()))]
m = [int(input()) for i in range(int(input()))]
print(min(len(set(n))-len(set(m)),0))

### 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)))))
# coding: utf-8
# Your code here!

import math 

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



for i in range(1,k+1):
    a = 1
    b = 1
    for j in range(1,i+1):
        a *= (n-k+2-j)/j
    for j in range(1,i):
        b *= (k-j)/j
    a %= 10**9+7
    b %= 10**9+7
    print(int(a*b)%(10**9+7))


### FIXED CODE ###

# coding: utf-8
# Your code here!


from scipy.misc import comb
mod = 10**9 + 7

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

for i in range(1,k+1):
    a = int(comb(k-1, i-1, exact=True)) % mod
    b = int(comb(n-k+1, i, exact=True)) % mod 
    print(a*b%mod)
while True:
    n = input()
    if n == 0:
        exit()
    A = [int(raw_input()) for _ in xrange(n)]
    if all(a<=0 for a in A):
        print max(a)
        exit()
    
    r = 0
    tmp = 0
    ans = 0
    while r < n:
        tmp += A[r]
        if tmp < 0:
            l = r
            tmp = 0
        else:
            ans = max(ans, tmp)
        r += 1
    print ans

### FIXED CODE ###

while True:
    n = input()
    if n == 0:
        exit()
    A = [int(raw_input()) for _ in xrange(n)]
    if all(a <= 0 for a in A):
        print max(A)
        continue
    
    r = 0
    tmp = 0
    ans = 0
    while r < n:
        tmp += A[r]
        if tmp < 0:
            l = r
            tmp = 0
        else:
            ans = max(ans, tmp)
        r += 1
    print ans
=x**3


### FIXED CODE ###

x = int(input())
print(x**3)
import math
a, b, x = map(int, input().split())

V = (a ** 2) * b

if x <= V / 2:
  t = 2 * x / (a * (b ** 2))
elif x > V / 2:
  t = (a ** 3) / (2 * (V - x))
  
def f(x):
  return math.tan(x) - t
def g(x):
  return math.tan(x) - 1 / t
if t < 1:
  S = math.pi / 4
  for i in range(100):
    S = S - f(S) * (math.cos(S) ** 2)
  print(90 - 180 * S / math.pi)
else:
  S = math.pi / 4
  for i in range(100):
    S = S - g(S) * (math.cos(S) ** 2)
  print(180 * S / math.pi)

### FIXED CODE ###

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

V = (a ** 2) * b

if x <= V / 2:
  t = 2 * x / (a * (b ** 2))
elif x > V / 2 and x != V:
  t = (a ** 3) / (2 * (V - x))

if x != V and t != 0:
  def f(x):
    return math.tan(x) - t
  def g(x):
    return math.tan(x) - 1 / t
  if t < 1:
    S = math.pi / 4
    for i in range(100):
      S = S - f(S) * (math.cos(S) ** 2)
    print(90 - 180 * S / math.pi)
  else:
    S = math.pi / 4
    for i in range(100):
      S = S - g(S) * (math.cos(S) ** 2)
    print(180 * S / math.pi)
elif x == V:
  print(0)
def I(): return int(input())
N = I()
ans = 0
for i in range(105,N+1,2):
    count_yakusuu = 0
    for j in range(1,int(i**0.5)+1):
        if i%j==0:
            count_yakusuu += 2
    if count_yakusuu==8:
        ans += 1
print(ans)


### FIXED CODE ###

A,B = map(int,input().split())
print((A-1)*(B-1))
def dp(i, j):
    if i == 0:
        if j:
            return -float('inf')
        else:
            return 0
    if j:
        return max(dp(i-1, False) - a[i-1], dp(i-1, True) + a[i-1])
    else:
        return max(dp(i-1, False) + a[i-1], dp(i-1, True) - a[i-1])


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

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
c = 0
z = False
for aa in a:
    if aa < 0:
        c += 1
    elif aa == 0:
        z = True
if z or c % 2 ==0:
    print(sum(map(abs, a)))
else:
    ab = [abs(x) for x in a]
    ans = sum(ab) - min(ab)*2
    print(ans)