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

MOD = 10**9 + 7
N = int(input())
A = list(map(int,input().split()))

ans = 0
for i in range(N-1):
  for j in range(i+1, N):
    ans += (A[i]^A[j])%MOD
    ans %= MOD
print(ans%MOD)

### FIXED CODE ###

MOD = 10 ** 9 + 7
N = int(input())
A = list(map(int, input().split()))
maxA = max(A)

maxA_len = len(bin(maxA)[2:])
num0_each_digit = [0 for _ in range(maxA_len)]
num1_each_digit = [0 for _ in range(maxA_len)]

for i in range(N):
    for i_bit, bit in enumerate(bin(A[i])[2:].zfill(maxA_len)):
        if bit == '0':
            num0_each_digit[i_bit] += 1
            num0_each_digit[i_bit] %= MOD
        else:
            num1_each_digit[i_bit] += 1
            num1_each_digit[i_bit] %= MOD
ans = 0
for i in range(maxA_len):
    factor = (2 ** (maxA_len - i - 1)) % MOD
    ans += (num0_each_digit[i] * num1_each_digit[i] * factor) % MOD

print(ans % MOD)
### BUGGY CODE ###

r=range
h,*s=open(0)
h,w,k=map(int,h.split())
m=9e9
for i in r(1<<h-1):
 t,v,l=[],-1,1
 for j in r(h):z=i>>j&1;t+=[j+1]*z;l+=z
 t+=h,
 c=[0]*l
 for i in r(w):
  b=f=g=0;u=[]
  for j in r(l):d,b=sum(s[j][i]>"0"for j in r(b,t[j])),t[j];u+=d,;g|=d>k;c[j]+=d;f|=c[j]>k
  v+=f
  if f:c=u
 if g<1:m=min(m,v+l)
print(m)

### FIXED CODE ###

h,*s=open(0)
h,w,k=map(int,h.split())
s=[list(map(int,t[:w]))for t in s]
m=9e9
for i in range(1<<h-1):
  t=[]
  b=v=l=0
  for j in range(h):
    if i>>j&1:
      t+=s[b:j+1],
      b=j+1
      l+=1
  t+=s[b:],
  l+=1
  c=[0]*l
  for i in range(w):
    f=g=0
    u=[]
    for j in range(l):
      d=sum(t[i]for t in t[j])
      u+=d,
      if d>k:
        g=1
        break
      c[j]+=d
      f|=c[j]>k
    else:
      v+=f
      if f:c=u
    if g:break
  else:m=min(m,v+l-1)
print(m)
### BUGGY CODE ###

# coding: utf-8

state = list(input())
print_state = "".join(state)

times = 0
while "BW" in print_state:
    for i in range(len(state)):
        if state[i] == "B":
            if i < len(state)-1 and state[i+1] == "W":
                state[i] = "W"
                state[i+1] = "B"
                times += 1
                print_state = "".join(state)
                
print(times)

### FIXED CODE ###

# coding: utf-8

s = list(input())
time = 0
count = 0
for i in range(len(s)):
  if s[i] == "W":
    time += i - count
    count += 1

print(time)
### BUGGY CODE ###

N,Q = map(int, input().split())
S = input()
acCount = [0]*len(S)

count = 0
for i in range(len(S)-1):
  if S[i]=='A' and S[i+1]=='C':
    acCount[i+1] = 1

for i in range(Q):
  L,R = map(int, input().split())
  print(sum(acCount[L:R]))

### FIXED CODE ###

N,Q = map(int, input().split())
S = input()
acCount = [0]*len(S)

count = 0
for i in range(len(S)-1):
  if S[i]=='A' and S[i+1]=='C':
    count += 1
  acCount[i+1] = count

  
for i in range(Q):
  L,R = map(int, input().split())
  print(acCount[R-1]-acCount[L-1])
### BUGGY CODE ###


h,w,k=map(int,input().split())
maze=[input()for i in range(h)]

for i in range(h):
    for j in range(w):
        if maze[i][j]=="S":x,y=i,j;break
    else:
        continue
    break
ans=float("INF")
l=[[float("INF")]*w for i in range(h)]
l[x][y]=0
from collections import deque
dq=deque([(x,y)])
#pop/append/(append,pop)_left/in/len/count/[]/index/rotate()(右へnずらす)
p=[(x,y)]
while len(dq):
    nx,ny=dq.popleft()
    for a,s in [(0,1),(0,-1),(1,0),(-1,0)]:
        if 0<=a+nx<h and 0<=ny+s<w and l[a+nx][s+ny]==float("INf")and maze[a+nx][s+ny]==".":
            l[a+nx][ny+s]=l[nx][ny]+1
            if l[a+nx][ny+s]<=k:p.append((a+nx,s+ny))
            if l[a+nx][ny+s]<k:dq.append((a+nx,s+ny))
ans=float("INf")

for x,y in p:
    ans=min(ans,(min(x,y,h-1-x,w-1-y)+k-1)//k+1)
print(ans)

### FIXED CODE ###


h,w,k=map(int,input().split())
maze=[]

for i in range(h):
    maze.append(input())
    for j in range(w):
        if maze[i][j]=="S":x,y=i,j
    
ans=float("INF")
l=[[float("INF")]*w for i in range(h)]
l[x][y]=0
from collections import deque
dq=deque([(x,y)])
#pop/append/(append,pop)_left/in/len/count/[]/index/rotate()(右へnずらす)
p={(x,y)}
while len(dq):
    nx,ny=dq.popleft()
    for a,s in [(0,1),(0,-1),(1,0),(-1,0)]:
        if 0<=a+nx<h and 0<=ny+s<w and l[a+nx][s+ny]==float("INf")and maze[a+nx][s+ny]==".":
            l[a+nx][ny+s]=l[nx][ny]+1
            if l[a+nx][ny+s]<=k:p.add((a+nx,s+ny))
            if l[a+nx][ny+s]<k:dq.append((a+nx,s+ny))
ans=float("INf")

for x,y in p:
    ans=min(ans,(min(x,y,h-1-x,w-1-y)+k-1)//k+1)
print(ans)
### BUGGY CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

K = int(input())

sum = 0
for i in range(1, K+1):
    for j in range(1, K+1):
        for k in range(1, K+1):
            sum += gcd(i, j, k)

print(sum)


### FIXED CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

K = int(input())

sum1 = 0
sum2 = 0
sum3 = 0
for i in range(1, K+1):
    for j in range(1, K+1):
        for k in range(1, K+1):
            if i <= j <= k:
                sum1 += gcd(i, j, k)
                if i == j == k:
                    sum2 += gcd(i, j, k)
                if (i == j != k) or (j == k != i) or (k == i != j):
                    sum3 += gcd(i, j, k)

print(sum1 * 6 - sum2 * 5 - sum3 * 3)
### BUGGY CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

n = int(input())

cnt = 0

for i in range(n):
    i +=1
    for j in range(n):
        j +=1
        for k in range(n):
            k +=1

            cnt += gcd(i,j,k)

print(cnt)


### FIXED CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

n = int(input())

cnt = 0

for i in range(n):
    i +=1
    for j in range(n):
        j +=1
        for k in range(n):
            k +=1

            cnt += gcd(i,j,k)

print(cnt)
### BUGGY CODE ###

import math

k = int(input())
sum = 0
for a in range(1,k+1):
    for b in range(1,k+1):
        for c in range(1,k+1):
            sum += math.gcd(math.gcd(a,b),c)
print(sum)


### FIXED CODE ###

import math

k = int(input())
sum = 0
for a in range(1,k+1):
    for b in range(1,k+1):
        ab = math.gcd(a,b)
        for c in range(1,k+1):
            sum += math.gcd(ab,c)
print(sum)
### BUGGY CODE ###

n = int(input())
a = list(map(str, input().split()))
b = []
for i in a:
    b.append(i)
    b = list(reversed(b))
print(" ".join(b))

### FIXED CODE ###

n = int(input())
a = list(map(str, input().split()))
b = []
if n%2 == 0:
    print(" ".join(a[1::2][::-1]+a[0::2]))
else:
    print(" ".join(a[0::2][::-1]+a[1::2]))
### BUGGY CODE ###

import sys


n,k= map(int,input().split())
v={}

min = sys.maxsize

if n == 0 :print(0);exit()
if n >= 10**18 :print(0);exit()


while True:
    diff = abs(n- k)

    if v.get(diff):
        break
    else:
        v[diff] = True
        n = diff

        if diff < min:
            min = diff



print(min)

### FIXED CODE ###

import sys

n,k= map(int,input().split())
v={}

min = sys.maxsize

if n == 0 :print(0);exit()

if n > k :
    x = n%k
    if x == 0 or x > k: 
        print(x);exit()
    else:
        n=x
        v[x] = True

while True:
    diff = abs(n- k)

    if v.get(diff):
        break
    else:
        # print(diff)
        v[diff] = True
        n = diff

        if diff < min:
            min = diff



print(min)
### BUGGY CODE ###

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

from collections import defaultdict

d = defaultdict(int)

for i in range(n):
    d[s[i]]+= 1

r = 0
key = sorted(list(d.keys()))
ng = len(key)
for i in range(ng)[::-1]:
    for j in range(i+1):
        for k in range(j, i+1)[::-1]:
            ti = 0
            if key[i] == key[j] and key[j] == key[k]:
                if d[key[i]] < 3:
                    continue
                else:
                    ti = d[key[i]] * (d[key[i]]-1) * (d[key[i]]-2) // 6
            elif key[i] == key[j]:
                if d[key[i]] < 2:
                    continue
                else:
                    ti = d[key[i]] * (d[key[i]]-1) * d[key[k]] // 2
            elif key[j] == key[k]:
                if d[key[k]] < 2:
                    continue
                else:
                    ti = d[key[j]] * (d[key[j]]-1) * d[key[i]] // 2
            elif key[i] == key[k]:
                if d[key[i]] < 2:
                    continue
                else:
                    ti = d[key[i]] * (d[key[i]]-1) * d[key[j]] // 2
            else:
                ti = d[key[i]] * d[key[j]] * d[key[k]]
            if key[j] + key[k] <= key[i]:
                break
            else:
                r+=ti
print(r)


### FIXED CODE ###

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

import bisect

s = sorted(s)

res = 0
for i in range(n)[::-1]:
    for j in range(i)[::-1]:
        if s[j] <= s[i] / 2:
            break
        k = bisect.bisect_left(s, s[i]-s[j]+1)
        res += max(0, j-k)
print(res)
### BUGGY CODE ###

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

if 0 in A:
  print(0)
  exit()

for a in A:
  result *= a
  
if result > 10**18:
  print(-1)
else:
  print(result)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
result = 1
 
if 0 in A:
  print(0)
  exit()

for a in A:
  result *= a
  if result > 10**18:
    print(-1)
    exit()

print(result)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    for i in range(K):
        b = [0] * (N+1)
        for j in range(N):
            a = A[j]
            b[max(j-a, 0)] += 1
            b[min(j+a+1, N)] -= 1
        for k in range(1,N+1):
            b[k] += b[k-1]
        if b == A:
            break
        else:
            A = b[:N]
    print(*A)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    for i in range(K):
        b = [0] * (N+1)
        for j in range(N):
            a = A[j]
            b[max(j-a, 0)] += 1
            b[min(j+a+1, N)] -= 1
        for k in range(1,N+1):
            b[k] += b[k-1]
        b = b[:N]
        if b == A:
            break
        else:
            A = b
    print(*A)

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

def gcd(a, b):
  if(b % a == 0):
    return a
  else:
    ans = 1
    i = 2
    while a!= 1:
      if(a % i == 0):
        while a % i == 0:
          a/= i
        while b % i == 0:
          b/= i
          ans*= i
        i+= 1
    return ans
          

def ggcd(lista):
  if(len(lista) == 1):
    return lista.pop()
  else:
    l = lista.pop()
    for i in range(1, len(lista)):
      l = gcd(l, lista.pop())
    return l

N, X = map(int, input().split())
x = list(map(int, input().split()))
x.append(X)
d = []
gcds = set()
x.sort()

for i in range(N):
  d.append(x[i+ 1]- x[i])
  
gcds.add(d[0])

for i in range(N- 1):
  if(d[i+ 1] != d[i]):
    gcds.add(gcd(d[i+ 1], d[i]))

print(ggcd(gcds))

### FIXED CODE ###

def gcd(a, b):
  if(a == b):
    return a
  elif(a % b == 0):
    return b
  elif(b % a == 0):
    return a
  elif(a == 1 or b == 1):
    return 1
  elif(a > b):
    return gcd(a- a// b* b, b)
  elif(a < b):
    return gcd(a, b- b// a* a)

def ggcd(lista):
  if(len(lista) == 1):
    return lista.pop()
  else:
    l = lista.pop()
    for i in range(1, len(lista)):
      l = gcd(l, lista.pop())
    return l

N, X = map(int, input().split())
x = list(map(int, input().split()))
x.append(X)
d = []
gcds = set()
x.sort()

for i in range(N):
  d.append(x[i+ 1]- x[i])

gcds.add(d[0])

for i in range(N- 1):
  if(d[i+ 1] != d[i]):
    gcds.add(d[i+ 1])

print(ggcd(gcds))
### BUGGY CODE ###

n =int(input())
a=list(map(int, input().split()))
m=0
s=[]
for i in range(len(a)):
    m+=a[i]
    s.append(abs(sum(a)-m*2))
print(min(s))

### FIXED CODE ###

n =int(input())
a=list(map(int, input().split()))
m=0
s=[]
suma=sum(a)
for i in range(len(a)):
    m+=a[i]
    s.append(abs(suma-m*2))
print(min(s))
### BUGGY CODE ###

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10000000)
n,a=int(input()),list(map(int,input().split()))
b=[0]*3
for i in a:b[i-1]+=1
dp=[[[0]*(n+1) for i in range(n+1)]for i in range(n+1)]
flag=[[[False]*(n+1) for i in range(n+1)]for i in range(n+1)];flag[0][0][0]=True
def d(a,b,c):
  if flag[a][b][c]:return dp[a][b][c]
  p=1;flag[a][b][c]=True
  if a>0:p+=d(a-1,b,c)*(a/n)
  if b>0:p+=d(a+1,b-1,c)*(b/n)
  if c>0:p+=d(a,b+1,c-1)*(c/n)
  dp[a][b][c]=p/(1-((n-a-b-c)/n))
  return dp[a][b][c]
print(d(b[0],b[1],b[2]))

### FIXED CODE ###

n,a=int(input()),map(int,input().split());c=[0]*3
for i in a:c[i-1]+=1
x,y,z=c;dp=[[[None]*(z+2) for i in range(n-x+2)]for i in range(n+2)];dp[0][0][0]=0
for k in range(z+1):
  for j in range(n-x-k+1):
    for i in range(n-k-j+1):
      if i+j+k:dp[i][j][k]=((dp[i-1][j][k]*i if i else 0)+(dp[i+1][j-1][k]*j if j else 0)+(dp[i][j+1][k-1]*k if k else 0)+n)/(i+j+k)
print(dp[x][y][z])
### BUGGY CODE ###

N = int(input())
S = input()

ans = set()
kinds = [set() for _ in range(N + 1)]
history = {}

for i in range(N - 1, -1, -1):
    kinds[i] = kinds[i + 1].union(S[i])

for i in range(N - 2):
    for j in range(i + 1, N - 1):
        number = history.get((S[i], S[j],))
        if not number:
            history[(S[i], S[j],)] = len(kinds[j+1])


print(sum(history.values()))


### FIXED CODE ###

N = int(input())
S = input()

ans = 0
for i in range(10):
    for j in range(10):
        for k in range(10):
            fi = S.find(str(i))
            if fi < 0:
                continue
            fj = S[fi+1:].find(str(j))
            if fj < 0:
                continue
            fk = S[fi+fj+2:].find(str(k))
            if fk < 0:
                continue
            ans += 1

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

import heapq
def SME(start,end):
    A = []
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] : continue
                else :
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * 0.95 : break
    for i in range(L):
        if ANS[i] : continue
        else : ANS[i] = min(Whole[:i+1])
    for i in range(L,N):
        if ANS[i] : continue
        else : ANS[i] = min(Whole[i+1-L:i+1])
    return ANS

[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
ANS = [None]*N
ANS = SME(0, N)
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

MOD = 10**9 + 7

def gcd(a, b):
    return b if a % b == 0 else gcd(b, a % b)

def solve(n, a):
    a = sorted(a, reverse=True)
    p = a[0]
    for i in range(1, n):
        p = p * a[i] // gcd(p, a[i])
    q = sum(p // a[i] for i in range(n))
    return q % MOD

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

### FIXED CODE ###

MOD = 10**9 + 7
MAX_NUM = 10**3
is_prime = [True] * MAX_NUM
is_prime[0] = False
is_prime[1] = False
primes = []
for i in range(MAX_NUM):
    if is_prime[i]:
        primes.append(i)
        for j in range(2*i, MAX_NUM, i):
            is_prime[j] = False

def prime_factorization(x):
    res = {}
    for prime in primes:
        while x % prime == 0:
            if not prime in res:
                res[prime] = 0
            res[prime] += 1
            x //= prime
    if x > 1:
        res[x] = 1
    return res

def mod_pow(p, q):
    res = 1
    while q:
        if q & 1:
            res = (res * p) % MOD
        p = (p * p) % MOD
        q //= 2
    return res

def mod_inv(p):
    return mod_pow(p, MOD - 2)

def solve(n, a):
    D = {}
    for i in range(n):
        prime_num_mapping = prime_factorization(a[i])
        for prime, num in prime_num_mapping.items():
            if not prime in D:
                D[prime] = 0
            D[prime] = max(D[prime], num)
    L = 1
    for prime, num in D.items():
        L = (L * mod_pow(prime, num)) % MOD
    res = sum(L * mod_inv(x) for x in a)
    return res % MOD

n = int(input())
a = list(map(int, input().split()))
print(solve(n, a))
### BUGGY CODE ###

import time
def input_int_list():
    return [int(thing) for thing in input().split(" ")]

def No():
    print(-1)
    exit()


N,M=input_int_list()
s_c_tuple_list=[input_int_list() for i in range(M)]
the_dict={}
for tup in s_c_tuple_list:
    s,c=tup
    if s==1 and c==0:
        if N==1:
            pass
        else:
            No()
    if s in the_dict:
        if the_dict[s]==c:
            pass
        else:
            No()
    else:
        the_dict[s]=c

if 1 not in the_dict:
    if N==1:
        the_dict[1]=0
    else:
        the_dict[1]=1
time.sleep(2)
the_num=int("".join([str(the_dict[i+1]) if i+1 in the_dict else str(0) for i in range(N)]))

print(the_num)


### FIXED CODE ###

import time
def input_int_list():
    return [int(thing) for thing in input().split(" ")]

def No():
    print(-1)
    exit()


N,M=input_int_list()
s_c_tuple_list=[input_int_list() for i in range(M)]
the_dict={}
for tup in s_c_tuple_list:
    s,c=tup
    if s==1 and c==0:
        if N==1:
            pass
        else:
            No()
    if s in the_dict:
        if the_dict[s]==c:
            pass
        else:
            No()
    else:
        the_dict[s]=c

if 1 not in the_dict:
    if N==1:
        the_dict[1]=0
    else:
        the_dict[1]=1
the_num=int("".join([str(the_dict[i+1]) if i+1 in the_dict else str(0) for i in range(N)]))

print(the_num)
### BUGGY CODE ###

import math
import itertools
from functools import reduce
from itertools import product

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

l = int(input())
s = 0
li = list(range(1,l+1))
for i,j,k in product(li, repeat = 3):
  s += gcd(i,j,k)
print(s)

### FIXED CODE ###

import math

l = int(input())
s = 0

for i in range(1, l+1):
  for j in range(1, l+1):
    tmp = math.gcd(i,j)
    for j in range(1, l+1):
      s += math.gcd(tmp,j)
  
print(s)
### BUGGY CODE ###

import sys
import numpy as np
from collections import defaultdict

def main():
    input = sys.stdin.readline
    n = int(input())
    a = np.array(list(map(int, input().split())))
    b = np.array(list(map(int, input().split())))

    a_sort = np.sort(a)
    b_sort = np.sort(b)

    # 1. 回数関係なくそもそも不可能なやつ → no
    # 2-a. サイクルは1つだとしても，完璧じゃない組み合わせが1つ以上許容されるやつ → yes
    # 2-b. サイクルが2以上にわけられるやつ → yes

    # 1
    if (a_sort > b_sort).any():
        print('No')
        exit()

    # 2-a
    if (a_sort[1:] <= b_sort[:-1]).any():
        print('Yes')
        exit()

    # 2-b （startをとりあえず1とかにする）
    d = defaultdict(int)
    for i in range(n):
        d[a[i]] = b[i]

    from_ = 1
    count = 0
    while True:
        count += 1
        from_ = d[from_]
        if from_ == 1:
            break

    if count != n:
        print('Yes')
    else:
        print('No')

if __name__ == '__main__':
    main()


### FIXED CODE ###

import numpy as np

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

a_sort = np.sort(a)
b_sort = np.sort(b)

# 1. 回数関係なくそもそも不可能なやつ → no
# 2-a. サイクルは1つだとしても，完璧じゃない組み合わせが1つ以上許容されるやつ → yes
# 2-b. サイクルが2以上にわけられるやつ → yes

# 1
if (a_sort > b_sort).any():
    print('No')
    exit()

# 2-a
if (a_sort[1:] <= b_sort[:-1]).any():
    print('Yes')
    exit()

# 2-b （startをとりあえず0番目とかにする）
index = b.argsort()
a = a[index]
sort_dict = a.argsort().tolist()
from_ = 0
count = 0
while True:
    count += 1
    from_ = sort_dict[from_]
    if from_ == 0:
        break

if count != n:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

N,K = map(int,input().split())
V = list(map(int,input().split()))
ans = []
for i in range(1,K+1):
    for j in range(2**i):
        gem = 0
        minus = []
        flag = True
        A = 0
        B = -1
        for k in range(i):
            if (j >> k) & 1 == 1:
                if A <= N-1:
                    if V[A] >= 0:
                        gem += V[A]
                    else:
                        minus.append(V[A])
                    A += 1
                else:
                    flag = False
                    break
            else:
                if B >= -N:
                    if V[B] >= 0:
                        gem += V[B]
                    else:
                        minus.append(V[B])
                    B -= 1
                else:
                    flag = False
                    break
        if flag:
            minus.sort(reverse = True)
            for l in range(K-i):
                if minus:
                    minus.pop()
            ans.append(gem + sum(minus))
print(max(ans))
        

### FIXED CODE ###

N,K = map(int,input().split())
V = list(map(int,input().split()))
ans = []
for i in range(1,min(K,N)+1):
    for a in range(i+1):
        b = i-a
        AB = V[:a]
        if b > 0:
            AB += V[-b:]
        AB.sort(reverse = True)
        for j in range(K-i):
            if AB and AB[-1] < 0:
                AB.pop()
        ans.append(sum(AB))
print(max(ans))
### BUGGY CODE ###

import sys
input=sys.stdin.readline
n=int(input())
S=input()
nagasa=len(list(S))
num=2**(nagasa-1).bit_length()
SEG=[set([])]*2*num
def init(S):
    for i in range(n):
        SEG[i+num-1]=set([S[i]])
    for i in range(num-2,-1,-1) :
        SEG[i]=SEG[2*i+1]|SEG[2*i+2]
    
def update(k,x):
    k += num-1
    SEG[k] = set(x)
    while k:
        k = (k-1)//2
        SEG[k] = SEG[k*2+1] | SEG[k*2+2]
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    ans=set([])
    while q-p>1:
        if p&1 == 0:
            ans|= SEG[p]
        if q&1 == 1:
            ans|= SEG[q]
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        ans |=SEG[p]
    else:
        ans |= SEG[p]
        ans |= SEG[q]
    return ans
init(S)
q=int(input())
for i in range(q):
    a=input()
    if a[0]=='1':
        s,t=a[1:].split()
        s=int(s)
        update(s-1,t)
    if a[0]=='2':
        s,t=map(int, a[1:].split())
        print(len(query(s-1,t)))


### FIXED CODE ###

import sys
input=sys.stdin.readline
n=int(input())
S=input()
nagasa=len(list(S))
num=2**(nagasa-1).bit_length()
SEG=[0]*2*num
def word_num(a):
    return 1<<(ord(a)-96)
def init(S):
    for i in range(n):
        SEG[i+num-1]=word_num(S[i])
    for i in range(num-2,-1,-1) :
        SEG[i]=SEG[2*i+1]|SEG[2*i+2]
    
def update(k,x):
    k += num-1
    SEG[k] = word_num(x)
    while k:
        k-=1
        k//=2
        SEG[k] = SEG[k*2+1] | SEG[k*2+2]
    
def query(p,q):
    if q<=p:
        return 0
    p += num-1
    q += num-2
    ans=0
    while q-p>1:
        if p&1 == 0:
            ans|= SEG[p]
        if q&1 == 1:
            ans|= SEG[q]
            q -= 1
        p //=2
        q-=1
        q//=2
    if p == q:
        ans |=SEG[p]
    else:
        ans |= SEG[p]
        ans |= SEG[q]
    return ans
init(S)
q=int(input())
for i in range(q):
    a,s,t=input().split()
    if a=='1':
        s=int(s)
        update(s-1,t)
    if a=='2':
        s=int(s)
        t=int(t)
        print(bin(query(s-1,t)).count('1'))