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

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

nums = A[:]
import math

gcd_queue = [
    (0, nums[0]),
]
for n in nums[1:]:
    tmp_queue = []
    for q in gcd_queue:
        tmp_queue.append((q[0] + q[1], n))
        tmp_queue.append((q[0] + q[1]*-1, n*-1))
    gcd_queue = set(tmp_queue[:])
    #print(gcd_queue)

gcd_queue = list(gcd_queue)
ans = gcd_queue[0][0] + gcd_queue[0][1]
for q in gcd_queue:
    ans = max(ans, q[0]+q[1])
print(ans)

### FIXED CODE ###

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

nums = A[:]
import math

gcd_queue = [
    (0, nums[0]),
]
for n in nums[1:]:
    tmp_queue = []
    for q in gcd_queue:
        tmp_queue.append((q[0] + q[1], n))
        tmp_queue.append((q[0] + q[1]*-1, n*-1))
    gcd_queue = set(tmp_queue[:])
    #print(gcd_queue)
    tmp = {}
    for q in gcd_queue:
        if str(q[1]) in tmp:
            tmp[str(q[1])] = max(q[0], tmp[str(q[1])])
        else:
            tmp[str(q[1])] = q[0]
    #print(tmp)
    gcd_queue = []
    for k, v in tmp.items():
        #print(k, v)
        gcd_queue.append((v, int(k)))
    

gcd_queue = list(gcd_queue)
ans = gcd_queue[0][0] + gcd_queue[0][1]
for q in gcd_queue:
    ans = max(ans, q[0]+q[1])
print(ans)
### BUGGY CODE ###


N, A,B = map(int, input().split())
str = []
for j in range(N//(A+B)+1):
    for i in range(A):
        if len(str)>N:
            break
        str.append('b')

    for i in range(B):
        if len(str)>N:
            break
        str.append('r')
    if len(str)>N:
        break

count = 0
for k in range(N):
    if str[k] == 'b':
        count+=1
print(count)


### FIXED CODE ###

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

count = N//(A+B)
if (N-count*(A+B))>A:
    print(count*A+A)
else:
    print(count*A+(N-count*(A+B)))
### BUGGY CODE ###

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

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

sum_a = sum(A)
# dc:Divisor Candidate(割る数の候補)
dc_list = [x for x in reversed(range(1, sum_a + 1)) if sum_a % x == 0]

for d in dc_list:
    mods = [a % d for a in A]
    mod_sum = sum(mods)
    if mod_sum % d != 0:
        continue
    mods = sorted(mods)

    op = 0
    mod_len = len(mods)
    for i, mod in enumerate(mods):
        op += mod

        if op > K:
            break

        if (mod_len - (i + 1)) * d == mod_sum and op <= K:
            print(d)
            exit(0)

### FIXED CODE ###

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

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

sum_a = sum(A)
# dc:Divisor Candidate(割る数の候補)
#dc_list = [x for x in reversed(range(1, sum_a + 1)) if sum_a % x == 0]
dc_list = []
for i in range(1, int(sum_a ** 0.5) + 1):
    if sum_a % i == 0:
        dc_list.append(i)
        if i != sum_a // i:
            dc_list.append(sum_a // i)

dc_list.sort(reverse = True)

for d in dc_list:
    mods = [a % d for a in A]
    mod_sum = sum(mods)
    if mod_sum % d != 0:
        continue
    mods = sorted(mods)

    op = 0
    mod_len = len(mods)
    for i, mod in enumerate(mods):
        op += mod

        if op > K:
            break

        if (mod_len - (i + 1)) * d == mod_sum and op <= K:
            print(d)
            exit(0)
### BUGGY CODE ###

n = int(input())
cond = []
for _ in range(n-1):
    c = list(map(int, input().split()))
    cond.append(c)

for i in range(n):
    if i == n-1:
        print(0)
    else:
        ela = 0

        for j in range(i, n-1):
            if j == i:
                # noru
                ela += cond[j][1]
            elif j != i:
                # noru
                if ela <= cond[j][1]:
                    ela = cond[j][1]
                elif ela > cond[j][1]:
                    k = 0
                    while True:
                        k += 1
                        product = k*cond[j][2]   
                        if product >= ela:
                            break
                    ela = product                     
            # susumu
            ela += cond[j][0]
        print(ela)

### FIXED CODE ###

# C
n = int(input())
cond = []
for _ in range(n-1):
    c = list(map(int, input().split()))
    cond.append(c)

for i in range(n):
    if i == n-1:
        print(0)
    else:
        ela = 0

        for j in range(i, n-1):
            if j == i:
                # noru
                ela += cond[j][1]
            elif j != i:
                # noru
                if ela <= cond[j][1]:
                    ela = cond[j][1]
                elif ela > cond[j][1]:
                    k = cond[j][2]
                    if ela%k == 0:
                        pass
                    else:
                        ela = ela + (k-(ela%k))               
            # susumu
            ela += cond[j][0]
        print(ela)
### BUGGY CODE ###

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

for i in X:
    list.remove(i)
    print(list[N//2-1])
    list.append(i)
    list.sort()


### FIXED CODE ###

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

for i in range(N):
    if list[int((N/2))]<=X[i]:
        print(list[int(N/2)-1])
    else:
        print(list[int(N/2)])
### BUGGY CODE ###

import sys

def mink(numk,l):
    x = 1
    for _ in range(k):
        x = a[x-1]
    return x

input = sys.stdin.readline
n,k = map(int,input().split())
a = list(map(int,input().split()))

# kが小さい時
if k <= 10**19:
    print(mink(k,a))
    sys.exit()

z = 1
p = [1]
for _ in range(k):
    z = a[z-1]
    if z in p:
        p.append(z)
        break
    p.append(z)

# 周期の来る前の回数
num = p.index(p[-1])

p = p[num:]

# 周期
pn = len(p)-1

k -= num

# 回数/周期のあまり
anum = k%pn
print(p[anum])


### FIXED CODE ###

import sys

input = sys.stdin.readline
n,k = map(int,input().split())
a = list(map(int,input().split()))

p = [1]
for i in range(n):
    p.append(a[p[i]-1])

if k <= n:
    print(p[k])
else:
    # 周期の来る前の回数
    num = p.index(p[-1])
    p = p[num:]

    # 周期
    pn = len(p)-1
    k -= num

    # 回数/周期のあまり
    ans = k%pn
    print(p[ans])
### BUGGY CODE ###

n = int(input())

nums = list(map(int, input().split()))
q = int(input())

ans = []

for _ in range(q):
    b, c = map(int, input().split())
    
    nums = sorted(nums)

    if b in nums:
        nums = [(c if num == b else num) for num in nums]
    
    ans.append(sum(nums))

for a in ans:
    print(a)

### FIXED CODE ###

from collections import Counter

n = int(input())

nums = tuple(map(int, input().split()))

count = Counter(nums)
s = sum(nums)

answers = []
q = int(input())
for _ in range(q):
    b, c = map(int, input().split())
    s = s + (c - b) * count[b]
    count[c] += count[b]
    count[b] = 0
    answers.append(s)
    
for answer in answers:
    print(answer)
### BUGGY CODE ###

n = int(input())

S = input()

ans = min(S.count("W"),S.count("E"))
for i in range(1,n):
	left = S[:i-1]
	right = S[i+1:]
	exans = left.count("W")+right.count("E")
	ans = min(ans,exans)

print(ans)

### FIXED CODE ###

n = int(input())
S = input()

west = [0]*(n+2)
east = [0]*(n+2)
ans = 10**6
for i in range(1,n+1):
	if S[i-1] == "W":
		west[i] = west[i-1]+1
	else:
		west[i] = west[i-1]
	if S[-i] == "E":
		east[-i-1] = east[-i]+1
	else:
		east[-i-1] = east[-i]

for i in range(1,n+1):
	ans = min(ans,west[i-1]+east[i+1])

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

N=int(input())
S=input()
cnt=0
for i in range(1000):
  con=0
  if i<10:
    a="00"+str(i)
  elif i<100:
    a="0"+str(i)
  else:
    a=str(i)
  for j in range(N):
    if S[j]==a[con]:
      con+=1
      if con==3:
        cnt+=1
        break
print(cnt)

### FIXED CODE ###

N=int(input())
S=input()
cnt=0
for i in range(1000):
  con=0
  if i<10:
    a="00"+str(i)
  elif i<100:
    a="0"+str(i)
  else:
    a=str(i)
  for j in range(N):
    if S[j]==a[con]:
      con+=1
      if con==3:
        cnt+=1
        break
print(cnt)
### BUGGY CODE ###

#木の根を得る
def root(x):
    while par[x] >= 0:
        x = par[x]
    return x

#木の併合
def unite(x, y):
    rx = root(x)
    ry = root(y)
    if rx != ry:
        if rx > ry:
            rx, ry = ry, rx
        par[rx] += par[ry]
        par[ry] = rx

N, M = map(int,input().split())
par = [-1]*N
K = []
for i in range(M):
    a, b = map(int, input().split())
    K.append([a-1, b-1])
K = K[::-1]

result = [0]
for i, j in K:
    unite(i, j)
    ans = 0
    for l in range(N):
        if root(l) == l:
            t = par[l]*(-1)
            ans += t*(t-1)//2
    result.append(ans)

result = result[::-1]
for i in result[1:]:
    print(result[0] - i)

### FIXED CODE ###

#木の根を得る
def root(x):
    while par[x] >= 0:
        x = par[x]
    return x

#木の併合
def unite(x, y):
    rx = root(x)
    ry = root(y)
    if rx != ry:
        if rx > ry:
            rx, ry = ry, rx
        par[rx] += par[ry]
        par[ry] = rx

def size(x):
    return -par[root(x)]

def same(x, y):
    rx = root(x)
    ry = root(y)
    return rx == ry

N, M = map(int,input().split())
par = [-1]*N
K = []
for i in range(M):
    a, b = map(int, input().split())
    K.append([a-1, b-1])
K = K[::-1]

result = [0]
ans = 0
for i, j in K:
    if not same(i, j):
        a = size(i)
        b = size(j)
        unite(i, j)
        c = size(i)
        ans += c*(c-1)//2 - (a*(a-1)//2 + b*(b-1)//2)
    result.append(ans)

result = result[::-1]
for i in result[1:]:
    print(result[0] - i)
### BUGGY CODE ###

def iter_bit(k, LIMIT):
    v = (1 << k) - 1

    while v < LIMIT:
        yield v
        x = v & -v
        y = v + x
        v = (v & ~y) // x >> 1 | y


def solve(n, cards):
    dp = [{} for _ in range(1 << n)]
    dp[-1][0] = 0
    LIMIT = 1 << n

    for d in range(n):
        for state in iter_bit(n - d, LIMIT):
            scores = dp[state]
            k = state
            curr = 0
            while k:
                b = k & -k
                i = b.bit_length() - 1
                num = cards[i][(d - i) % 2]
                next_dp = dp[state ^ b]
                for left_num, score in scores.items():
                    if left_num > num:
                        continue
                    ns = score + curr
                    if num not in next_dp or next_dp[num] > ns:
                        next_dp[num] = ns
                k ^= b
                curr += 1

    if len(dp[0]) > 0:
        return min(dp[0].values())
    else:
        return -1


n = int(input())
aaa = list(map(int, input().split()))
bbb = list(map(int, input().split()))
cards = list(zip(aaa, bbb))
print(solve(n, cards))


### FIXED CODE ###

def iter_bit(k, LIMIT):
    v = (1 << k) - 1

    while v < LIMIT:
        yield v
        x = v & -v
        y = v + x
        v = (v & ~y) // x >> 1 | y


def solve(n, cards):
    dp = [{} for _ in range(1 << n)]
    dp[-1][0] = 0
    LIMIT = 1 << n

    for d in range(n):
        for state in iter_bit(n - d, LIMIT):
            scores = dp[state]
            k = state
            curr = 0
            while k:
                b = k & -k
                i = b.bit_length() - 1
                num = cards[i][(d - i) % 2]
                next_dp = dp[state ^ b]
                for left_num, score in scores.items():
                    if left_num > num:
                        continue
                    ns = score + curr
                    if num not in next_dp or next_dp[num] > ns:
                        next_dp[num] = ns
                k ^= b
                curr += 1

    if len(dp[0]) > 0:
        return min(dp[0].values())
    else:
        return -1


n = int(input())
aaa = list(map(int, input().split()))
bbb = list(map(int, input().split()))
cards = list(zip(aaa, bbb))
print(solve(n, cards))
### BUGGY CODE ###

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

s = 0
c = set()

for i in range(n):
    if a[i] not in c:
        num = a.count(a[i])
        s += num*(num-1) / 2
        c.add(a[i])

for i in range(n):
    print(int(s - (a.count(a[i]) - 1) ))

### FIXED CODE ###

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

num_count = {}

for e in a:
    if e in num_count.keys():
        num_count[e] += 1
    else:
        num_count[e] = 1

s = 0
c = set()

for i in range(n):
    if a[i] not in c:
        num = num_count[a[i]]
        s += num*(num-1) / 2
        c.add(a[i])

for i in range(n):
    print(int(s - (num_count[a[i]] - 1) ))
### BUGGY CODE ###

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

tot = 0
num2 = [0]*(N-1)


for i in range(len(num)-1):
  num1 = num[i] % (10**9+7)
  num2[i] = sum(num[1+i:]) % (10**9+7)
  
  tot += num1 * num2[i]
  
  if tot >= (10**9+7): tot = tot % (10**9+7)

print(tot)

### FIXED CODE ###

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

tot = 0
num2 = [0]*(N-1)
numtot = sum(num)

for i in range(len(num)-1):
  numtot -= num[i]
  num2[i] = numtot % (10**9+7)
  
  num1 = num[i] % (10**9+7)
  
  tot += num1 * num2[i]
  
  if tot >= (10**9+7): tot = tot % (10**9+7)

print(tot)
### BUGGY CODE ###

import bisect

n, m = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]

for _ in range(m):
    b, c = [int(i) for i in input().split()]
    a += [c] * b

a_sorted = sorted(a, reverse=True)

print(sum(a_sorted[0:n]))


### FIXED CODE ###

import bisect

n, m = [int(i) for i in input().split()]
a_list = [int(i) for i in input().split()]

new_cards_info = {}

for a in a_list:
    if a in new_cards_info:
        new_cards_info[a] += 1
    else:
        new_cards_info[a] = 1

for _ in range(m):
    b, c = [int(i) for i in input().split()]
    if c in new_cards_info:
        new_cards_info[c] += b
    else:
        new_cards_info[c] = b

new_cards_info = sorted(new_cards_info.items(), key=lambda x:x[0], reverse=True)

sum = 0
count = 0

for key, size in new_cards_info:
    sum += key * size
    over = count + size - n
    if over >= 0:
        sum -= key * over
        break
    count += size

print(sum)
### BUGGY CODE ###

s = list(input())
K = int(input())
l = []
N = len(s)

for i in range(N):
    for j in range(N-i):
        tmp = s[j:j+i+1]
        l.append(''.join(tmp))

l = list(set(l))
l.sort()
#print(l)


ans = l[K-1]
print(ans)



### FIXED CODE ###

s = input()
K = int(input())
l = ['zzzzzzzzzzzzzzz','zzzzzzzzzzzzzzz','zzzzzzzzzzzzz','zzzzzzzzzzzz','zzzzzzzzz']
N = len(s)

for i in range(K+1):
    for j in range(N-i):
        tmp = s[j:j+i+1]
        if tmp not in l:
            l.append(tmp)
        l.sort()
        l = l[0:5]


l.sort()
#print(l)


ans = l[K-1]
print(ans)
### BUGGY CODE ###

import itertools
X = int(input())

l = [i for i in range(-10000, 10000)]
c = itertools.permutations(l, 2)
for a, b in c:
    if a**5 - b**5 == X:
        print(a, b)
        break



### FIXED CODE ###

import itertools
X = int(input())

l = [i for i in range(-1000, 1000)]
c = itertools.permutations(l, 2)
for a, b in c:
    if a**5 - b**5 == X:
        print(a, b)
        break
### BUGGY CODE ###

R, G, B, N = list(map(int, input().split()))

count = 0
for i in range(0, N+1, R):
    for j in range(0, N+1, G):
        if (N-i-j) % B == 0 and N >= (i+j):
            count += 1
print(count)

### FIXED CODE ###

R, G, B, N = list(map(int, input().split()))
 
count = len([1 for i in range(0, N+1, R) for j in range(0, N+1, G) if (N-i-j) % B == 0 and N >= (i+j)])
print(count)
### BUGGY CODE ###

def lcs(x,y):
    xs = len(x)
    ys = len(y)
    x = " " + x
    y = " " + y
    c = [[0 for i in xrange(len(x))] for j in xrange(len(y))] 
    m = 0
#    for i in xrange (xs+1):
#        c[i][0] = 0
#    for j in xrange (ys+1):
#        c[0][j] = 0


    for i in xrange (1,ys+1):
        for j in xrange (1,xs+1):
            if x[j] == y[i]:
                a = 1
            else:
                a = 0
            c[i][j] = max(c[i][j-1],c[i-1][j],c[i-1][j-1] + a)
        m = max(m,c[i][j])
    return max(max(c))

n = input()

for i in xrange (n):

    x = raw_input()
    y = raw_input()

    print lcs(x,y)
    

### FIXED CODE ###

def lcs():
    x, y = raw_input(), raw_input()
    b1 = [0 for k in range(len(y)+1)]
    for i in xrange(len(x)):
        a = x[i]
        b2 = b1 + []
        for j in xrange(len(y)):
            if a == y[j]:
                b1[j+1] = b2[j] + 1
            elif b1[j+1] < b1[j]:
                b1[j+1] = b1[j]
    print max(b1)
 
n = input()
for i in xrange(n):
    lcs()
### BUGGY CODE ###

n = int(input())
g=[]
for i in range(n):
    
    g.append(list(map(int,input().split())))
mod=10**9+7
def dp(p,vw):
    if p==n:
        return 1
    k=0
    
            
    for j in range(n):
        if g[p][j]==1 and vw[j]==0:
            #print(p,j)

            vw[j]=1
            k+=dp(p+1,vw)
            k%=mod
            #print(vw)

            vw[j]=0
                    
    return k%mod

viw=[0]*n
print(dp(0,viw))
            
    
    

### FIXED CODE ###

n = int(input())
g=[]
for i in range(n):
    
    g.append(list(map(int,input().split())))
mod=10**9+7
dp=[0]*(2**n)
dp[0]=1
for i in range(1,2**n):
    e=bin(i)[2:]
    y=e.count('1')
    for j in range(len(e)):
        if e[-j-1]=='1':
            if g[y-1][j]:
                    dp[i]+=dp[i-(2**j)]
                    dp[i]%=mod


print(dp[-1]%mod)
### BUGGY CODE ###

N,M = list(map(int,input().split()))
A = []
B = []
ans = 0
for _ in range(N):
    i = list(map(int,input().split()))
    A.append(i[0])
    B.append(i[1])
#print(min(A),'min')
#print(A.index(min(A)),'index')
while M != 0:
    if M - B[A.index(min(A))] >= 0:
        M -= B[A.index(min(A))]
        ans = ans + A[A.index(min(A))]*B[A.index(min(A))]
        B[A.index(min(A))] -= B[A.index(min(A))]
    else:
        ans += min(A)
        M -= 1
        B[A.index(min(A))] -= 1
    if B[A.index(min(A))] <= 0:
        B.pop(A.index(min(A)))
        A.pop(A.index(min(A)))
print(ans)

### FIXED CODE ###

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

AB = [list(map(int,input().split())) for i in range(N)]
AB.sort()
ans = 0
for _ in range(N):
    if AB[_][1] >= M:
        ans += AB[_][0]*M
        break
    else:
        ans += AB[_][0]*AB[_][1]
        M -= AB[_][1]
print(ans)
### BUGGY CODE ###

n,k=[int(x) for x in input().split()]
p=[(int(x)-1) for x in input().split()]
a=[0]
i=0
while p[i] not in a:
  a.append(p[i])
  i=p[i]
l=a.index(p[i])
if k<=l: print(1+a[k])  
else: print(1+a[l+(k-l)%(len(a)-l)])

### FIXED CODE ###

n,k=[int(x) for x in input().split()]
p=[(int(x)-1) for x in input().split()]
alp=[0 for _ in range(n)]
a=[0]
i=0
alp[0]=1
while alp[p[i]]==0:
  a.append(p[i])
  alp[p[i]]=1
  i=p[i]
l=a.index(p[i])
if k<=l: print(1+a[k])
else: print(1+a[l+(k-l)%(len(a)-l)])
### BUGGY CODE ###

def uf_find(x):
  z = x
  while z != p[z]:
    z = p[z]
  p[x] = z
  return z

def uf_unite(x,y):
  global rand
  x = uf_find(x)
  y = uf_find(y)
  if x != y:
    rand += 1
    if rand % 2 ==0:
      p[y] = x
    else:
      p[x] = y

N, M = map(int, input().split())
p = list(range(N))
rand = 0

for i in range(M):
  A, B = [int(j)-1 for j in input().split()]
  uf_unite(A,B)

  
for i in range(N):
  p[i] = uf_find(i)


q = [0]*N
for i in range(N):
  q[i] = p.count(i)
  
print(max(q))


### FIXED CODE ###

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

par = list(range(N))
rank = [1]*N
size = [1]*N

def find(x):
  if par[x] == x:
    return x
  else:
    return find(par[x])
  
def unite(x,y):
  x = find(x)
  y = find(y)
  
  if x == y:
    return
  if rank[x]<rank[y]:
    par[x]=y
    size[y]+= size[x]
  else:
    par[y] = x
    size[x] += size[y]
    if rank[x]==rank[y]:
      rank[x]+=1
    
for i in range(M):
  a,b = [int(i)-1 for i in input().split()]
  unite(a,b)
  
print(max(size))
### BUGGY CODE ###

n, k = map(int, input().split())
P = list(map(int, input().split()))
ExP = list(map(lambda x: (x+1)/2, P))
ans = 0
for i in range(n-k+k):
#     print(ExP[i: i+k])
    ans = max(ans, sum(ExP[i: i+k]))
print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
P = list(map(int, input().split()))
ExP = list(map(lambda x: (x+1)/2, P))
ans = 0
prev = 0

#for i = 0
now = sum(ExP[0: k])
#print(0, now)
ans = max(ans, now)
prev = now

for i in range(1, n-k+1):
    now = prev - ExP[i-1] + ExP[i+k-1]
#    print(i, now)
    ans = max(ans, now)
    prev = now
print(ans)
### BUGGY CODE ###

def main():
	import sys
	readline = sys.stdin.readline

	#s = tuple(input())
	s = input().rstrip()
	length = len(s)

	dp = [[0]*13 for _ in range(length)]
	MOD = 10**9+7

	if s[-1] == '?':
		for i in range(10):
			dp[0][i] = 1
	else:
		dp[0][int(s[-1])] = 1

	a = 1
	for i in range(1,length):
		a = 10 * a % 13
		if s[-(i+1)] != '?':
			num = int(s[-(i+1)])
			for j in range(13):
				dp[i][(a*num+j)%13] += dp[i-1][j] % MOD
		else:
			num = (10**i) % 13
			#a = 0
			for j in range(10):
				for k in range(13):
					dp[i][(a*j+k)%13] += dp[i-1][k] % MOD
				#a += num

	print(dp[-1][5] % MOD)

if __name__ == '__main__':
	main()

### FIXED CODE ###

INF = 10 ** 9 + 7

S = input()
# dp[i][j]はうしろからi桁を13で割った余りがjであるものの個数
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
mul = 1

for i in range(len(S)):
    x = S[-(i + 1)]
    if x == "?":
        for k in range(10):
            for j in range(13):
                dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                dp[i + 1][(mul * k + j) % 13] %= INF
    else:
        k = int(x)
        for j in range(13):
            dp[i + 1][(mul * k + j) % 13] += dp[i][j]
            dp[i + 1][(mul * k + j) % 13] %= INF
    mul = mul * 10 % 13  # 計算量削減のためここで13で割っている

print(dp[len(S)][5])
### BUGGY CODE ###

s = input()
q = int(input())
reverse_flag = False

for i in range(q):
  query = input().split()
  if query[0] == "1":
    reverse_flag = not reverse_flag
  else:
    if (query[1] == "1") ^ reverse_flag:
      s = query[2] + s
    else:
      s += query[2]

print(s[::-1] if reverse_flag else s)

### FIXED CODE ###

from collections import deque

d = deque(input())
q = int(input())
reverse_flag = False

for i in range(q):
  query = input().split()
  if query[0] == "1":
    reverse_flag = not reverse_flag
  else:
    if (query[1] == "1") ^ reverse_flag:
      d.appendleft(query[2])
    else:
      d.append(query[2])

print("".join(list(d)[::-1]) if reverse_flag else "".join(d))
### BUGGY CODE ###

mod=10**9+7
N,X=map(int,input().split())
S=[int(i) for i in input().split()]
S.sort(reverse=True)

Factorial=[1]*(N+1)
for i in range(1,N+1):
  Factorial[i]=Factorial[i-1]*(i)%mod
def power(x,y):
  if y==0:
    return 1
  elif y==1:
    return x%mod
  elif y%2==0:
    return power(x,y//2)**2%mod
  else:
    return ((power(x,y//2)**2)*x)%mod
inv=[0]*(N+1)
for i in range(N+1):
  inv[i]=power(i,mod-2)
dp=[[0]*(X+1) for i in range(N+1)]
for x in range(X+1):
  dp[N][x]=x
for i in range(N)[::-1]:
  for x in range(X+1):
    dp[i][x]+=dp[i+1][x%S[i]]*inv[N-i]
    dp[i][x]%=mod
    dp[i][x]+=(N-i-1)*dp[i+1][x]*inv[N-i]
    dp[i][x]%=mod
print((dp[0][X]*Factorial[N])%mod)

### FIXED CODE ###

mod=10**9+7
N,X=map(int,input().split())
S=[int(i) for i in input().split()]
S.sort(reverse=True)

Factorial=[1]*(N+1)
for i in range(1,N+1):
  Factorial[i]=Factorial[i-1]*(i)%mod
def power(x,y):
  if y==0:
    return 1
  elif y==1:
    return x%mod
  elif y%2==0:
    return power(x,y//2)**2%mod
  else:
    return ((power(x,y//2)**2)*x)%mod
inv=[0]*(N+1)
for i in range(N+1):
  inv[i]=power(i,mod-2)
dp=[[0]*(X+1) for i in range(N+1)]
for x in range(X+1):
  dp[N][x]=x
for i in range(N)[::-1]:
  for x in range(X+1):
    dp[i][x]=dp[i+1][x%S[i]]+(N-i-1)*dp[i+1][x]
    dp[i][x]%=mod
print((dp[0][X])%mod)
### BUGGY CODE ###

import itertools
while 1:
	n = input()
	if n == 0: break
	a = sorted(map(int,raw_input().split()))
	all = sum(a)
	ans = all
	for i in range((n+1)/2+1):
		c = 0
		for party in itertools.combinations(a,i):
			d = all-2*sum(party)
			if c == 0 and d < -ans:
				break
			ans = min(ans,abs(d))
			c = 1
	print ans

### FIXED CODE ###

def S(i,x,y):
	if 2*x >= A: return 2*x-A
	if 2*y >= A: return 2*y-A
	return min(S(i+1,x+a[i],y),S(i+1,x,y+a[i]))
while 1:
	n = input()
	if n == 0: break
	a = sorted(map(int,raw_input().split()))[::-1]
	A = sum(a)
	print S(1,a[0],0)