Harryxun/stf_run huggingface dataset:
# import bisect
# from collections import Counter, deque
# import copy
# from fractions import gcd
# from functools import reduce
from itertools import permutations
import math
#import numpy as np
input = sys.stdin.readline

def resolve():
    N=int(input())
    l=[[0,0] for i in range(N)]
    for i in range(N):
        x,y=map(int,input().split())
        l[i][0],l[i][1]=x,y

    p=permutations(l)
    dist = 0
    for v in p:
        for i in range(N-1):
            dist+=math.sqrt((v[i][0]-v[i+1][0])**2+(v[i][1]-v[i+1][1])**2)
    print(dist/len(list(permutations((l)))))


resolve()

### FIXED CODE ###

# import bisect
# from collections import Counter, deque
# import copy
# from fractions import gcd
# from functools import reduce
from itertools import permutations

def resolve():
    N=int(input())
    l=[[0,0] for i in range(N)]
    for i in range(N):
        x,y=map(int,input().split())
        l[i][0],l[i][1]=x,y

    p=permutations(l)
    dist = 0
    for v in p:
        for i in range(N-1):
            dist+=((v[i][0]-v[i+1][0])**2+(v[i][1]-v[i+1][1])**2)**0.5

    print(dist/len(list(permutations((l)))))


resolve()
n,a,b,c = map(int,input().split())
l=[int(input()) for i in range(n)]
answer = 10*100
for i in range(1,2**(2*n)):
    a_u = []
    b_u = []
    c_u = []
    ans = 0
    j = i
    counte = 0
    while counte <= n:
        if j%4 == 0:
            a_u.append(l[counte])
        if j%4 == 1:
            b_u.append(l[counte])
        if j%4 == 2:
            c_u.append(l[counte])
        j = j//4
        counte += 1
    if len(a_u)*len(b_u)*len(c_u) > 0:
        ans += abs(sum(a_u)-a) + 10*(len(a_u)-1)
        ans += abs(sum(b_u)-b) + 10*(len(b_u)-1)
        ans += abs(sum(c_u)-c) + 10*(len(c_u)-1)
        answer = min(ans,answer)

print(answer)

### FIXED CODE ###

n, a, b, c = map(int,input().split())
L = [int(input()) for i in range(n)]
ans = 10**10

for i in range(4**n):
    ta, tb, tc = 0, 0, 0
    tmp = 0
    for j in range(n):
        k = (i>>(2*j)) & 3
        if k == 1:
            if ta > 0:
                tmp += 10
            ta += L[j]
        elif k == 2:
            if tb > 0:
                tmp += 10
            tb += L[j]
        elif k == 3:
            if tc > 0:
                tmp += 10
            tc += L[j]
    if ta * tb * tc == 0:
        continue
    tmp += abs(a - ta) + abs(b - tb) + abs(c - tc)
    ans = min(ans,tmp)

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

A = [input() for _ in range(N)]
B = [input() for _ in range(M)]

b_index = 0
for i in range(N):
    for j in range(len(A[i])):
        if A[i][j] == B[0][0]:
            for i2 in range(M):
                for j2 in range(len(B[i2])):
                    if A[i+i2][j+j2] != B[i2][j2]:
                        break
                else:
                    continue
                break
            else:
                print('Yes')
                exit()
print('No')


                



### FIXED CODE ###

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

A = [input() for _ in range(N)]
B = [input() for _ in range(M)]

b_index = 0
for i in range(N):
    for j in range(len(A[i])):
        if A[i][j] == B[0][0]:
            for i2 in range(M):
                for j2 in range(len(B[i2])):
                    if i+i2 > N-1 or j+j2 > len(A[i+i2])-1:
                        break
                    elif A[i+i2][j+j2] != B[i2][j2]:
                        break
                else:
                    continue
                break
            else:
                print('Yes')
                exit()
print('No')
N = int(input())
S = []
for _ in range(N):
    S.append(input())
    
import collections
c = collections.Counter(S)
most = c.most_common()
answerlist = [most[0][0]]
i = 0
while most[i][1] == most[i+1][1]:
    answerlist.append(most[i+1][0])
    i += 1
    if i == len(most)-1:
        break
sortanswer = sorted(answerlist)
for i in range(len(sortanswer)):
    print(sortanswer[i])

### FIXED CODE ###

N = int(input())
S = []
for _ in range(N):
    S.append(input())
    
import collections
c = collections.Counter(S)
most = c.most_common()
answerlist = [most[0][0]]
i = 0
if len(most) > 1:
    while most[i][1] == most[i+1][1]:
        answerlist.append(most[i+1][0])
        i += 1
        if i == len(most)-1:
            break
sortanswer = sorted(answerlist)
for i in range(len(sortanswer)):
    print(sortanswer[i])
import sys
readline = sys.stdin.readline

K = int(readline())
S = readline().rstrip()
S = len(S)
N = K + S

# K = 3, S = 5のとき
# ..X.X.X.
# Xが取る3か所を選んだ上で、
# 最も右のXよりも右のマス：各26通り
# 最も右のXを含む、それより左のマス：Xのマスは1通り、それ以外は各25通り
# 最も右のXが
# ..X.....　の状態から、
# .......X  
# の状態について、場合の数を求める

DIV = 10 ** 9 + 7
n = 10 ** 6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, n + 1 ):
    g1.append( ( g1[-1] * i ) % DIV )
    inverse.append( ( -inverse[DIV % i] * (DIV//i) ) % DIV )
    g2.append( (g2[-1] * inverse[-1]) % DIV )

def nCr(n, r, DIV):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % DIV

ans = 0
for xpos in range(S, N + 1):
  # xpos箇所からK箇所を選ぶ場合の数
  # 一番右に1個固定した状態で、残りのxpos - 1か所からS - 1個を選ぶ
  pat = nCr(xpos - 1, S - 1, DIV)
#  print(S,"from",xpos,"pat",pat)
  # その場合の数に対して、X以外の文字の選び方は25 ** (X - S)通りある
#  print("25 for",xpos - S,"boxes")
  pat *= pow(25, xpos - S, DIV)
  pat %= DIV
  
  # 残りのマスに対しては26通りずつ選べる
#  print("26 for ",N - xpos,"boxes")
  pat *= pow(26, N - xpos, DIV)
  pat %= DIV
#  print("xpos",xpos,"pat",pat)
  
  ans += pat
  ans %= DIV

print(ans)

### FIXED CODE ###

import sys
readline = sys.stdin.readline

K = int(readline())
S = readline().rstrip()
S = len(S)
N = K + S

DIV = 10 ** 9 + 7
n = (10 ** 6) * 5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, n + 1 ):
    g1.append( ( g1[-1] * i ) % DIV )
    inverse.append( ( -inverse[DIV % i] * (DIV//i) ) % DIV )
    g2.append( (g2[-1] * inverse[-1]) % DIV )

def nCr(n, r, DIV):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % DIV

# K = 3, S = 5のとき
# ..X.X.X.
# Xが取る3か所を選んだ上で、
# 最も右のXよりも右のマス：各26通り
# 最も右のXを含む、それより左のマス：Xのマスは1通り、それ以外は各25通り
# 最も右のXが
# ..X.....　の状態から、
# .......X  
# の状態について、場合の数を求める

ans = 0
for xpos in range(S, N + 1):
  # xpos箇所からK箇所を選ぶ場合の数
  # 一番右に1個固定した状態で、残りのxpos - 1か所からS - 1個を選ぶ
  pat = nCr(xpos - 1, S - 1, DIV)
#  print("xpos",xpos,"ncr",ncr)
#  print(S,"from",xpos,"pat",pat)
  # その場合の数に対して、X以外の文字の選び方は25 ** (X - S)通りある
#  print("25 for",xpos - S,"boxes")
  pat *= pow(25, xpos - S, DIV)
  pat %= DIV
  
  # 残りのマスに対しては26通りずつ選べる
#  print("26 for ",N - xpos,"boxes")
  pat *= pow(26, N - xpos, DIV)
  pat %= DIV
#  print("xpos",xpos,"pat",pat)
  
  ans += pat
  ans %= DIV

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

gyk1 = 0
for i in range(n):
  gyk1 += 1 / a[i]

print(1 / gyak1)

### FIXED CODE ###

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

gyk1 = 0
for i in range(n):
  gyk1 += 1 / a[i]

print(1 / gyk1)
print(s[3-'AGCT'.index(input())])

### FIXED CODE ###

b=input()
if b=='A':print('T')
elif b=='T':print('A')
elif b=='C':print('G')
else:print('C')
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    def group_count(self):
        return len(self.roots())
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(M)]

uf = UnionFind(N)
for a,b in AB:
    uf.union(a,b)

print(uf.group_count() - 1)

### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    def group_count(self):
        return len(self.roots())
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(M)]

uf = UnionFind(N)
for a,b in AB:
    uf.union(a-1,b-1)

print(uf.group_count() - 1)
n = int(input())
a = list(map(int,input().split()))
aabs = [i if i>=0 else i*(-1) for i in a]
MIN = min(aabs)
ans = 0
mcount = 0

for i in range(n):
  if a[i] < 0:
    mcount += 1
    
if mcount%2 == 0:
  for i in a:
    ans += abs(i)
    print(ans)
else:
  for i in a:
    ans += abs(i)
  print(ans - 2*MIN)
  

### FIXED CODE ###

import heapq

n,m = map(int,input().split())
a = list(map(int,input().split()))
a = list(map(lambda x: x*(-1), a))  # 各要素を-1倍することで，最小最大を逆転

heapq.heapify(a)#優先度付きキューに変換

for i in range(m):
  tmp = heapq.heappop(a)
  heapq.heappush(a,(-tmp//2)*(-1))#負の剰余では切り捨て方向が異なってしまうので，いったんプラスにする．
  
print(-sum(a))
s = input()
q = int(input())
a = []
# for j in range(q):
#     a.extend([list(map(str,input().split()))])
# # print(a)
# for i in a:
for j in range(q):
    i = map(str,input().split())
    if i ==["1"]:
        s = s[::-1]
    elif i[0]=="2" and i[1]=="1":
        s = i[2]+s
    elif i[0]=="2" and i[1]=="2":
        s = s +i[2]
print(s)

### FIXED CODE ###

s = input()
q = int(input())
a = []
# for j in range(q):
#     a.extend([list(map(str,input().split()))])
# # print(a)
# for i in a:
pre = ""
nex = ""
c = 1
for j in range(q):
    i = list(map(str,input().split()))
    if i ==["1"]:
        c *= -1
        # s = s[::-1]
    elif i[0]=="2" and i[1]=="1":
        # s = i[2]+s
        if c == 1:
            pre=i[2]+pre
        else:
            nex = nex + i[2]
    elif i[0]=="2" and i[1]=="2":
        # s = s +i[2]
        if c ==1:
            nex = nex +i[2]
        else:
            pre = i[2]+pre
s = pre+s+nex
if c ==-1:
    s = s[::-1]
print(s)
from functools import lru_cache


@lru_cache(maxsize=100000)
def get_ways(n):
    if n == 1 or n == 2:
        return n
    elif n == 0:
        return 1
    elif n == -1:
        return 0
    else:
        return get_ways(n - 2) + get_ways(n - 1)


N, M = map(int, input().split())
ans = 1
tmp = 0
for i in range(M):
    a = int(input())
    ans *= get_ways(a - tmp - 1)
    tmp = a + 1
ans *= get_ways(N - tmp)
print(ans % 1000000007)


### FIXED CODE ###

from functools import lru_cache
import sys
sys.setrecursionlimit(10**6)


@lru_cache(maxsize=1000000)
def get_ways(n):
    if n == 1 or n == 2:
        return n
    elif n == 0:
        return 1
    elif n == -1:
        return 0
    else:
        return get_ways(n - 2) + get_ways(n - 1)


N, M = map(int, input().split())
ans = 1
tmp = 0
for i in range(M):
    a = int(input())
    ans *= get_ways(a - tmp - 1)
    tmp = a + 1
ans *= get_ways(N - tmp)
print(ans % 1000000007)
a, b = map(int, input.split())
print(a * b % 2 == 0 ? "Even" : "Odd")

### FIXED CODE ###

a, b = map(int, input().split())
print("Even" if a * b % 2 == 0 else "Odd")
a,b,k=map(int,input().split())
if k<=a:
	print(a-k,b)
elif k>=a and k<=b:
	print(a-a,b+a-k)
else: print(0 0)


### FIXED CODE ###

S,T =input().split()
print(T+S)
import math
from itertools import accumulate

def eratosthenes(n):
    prime_list = []
    num_list=[i for i in range(2, n+1)]
    limit = math.sqrt(n)
    while True:
        if limit <= num_list[0]:
            return prime_list + num_list
        prime_list.append(num_list[0])
        num_list = [e for e in num_list if e % num_list[0] != 0]

er_list = eratosthenes(100000)
count = []

j = 0
for i in range(er_list[-1]):
    if i == er_list[j]:
        j += 1
        if (i+1)//2 in er_list:
            count.append(1) 
        else:
            count.append(0)
            
count = list(accumulate(count))
            
Q = int(input())
for i in range(Q):
    l, r = map(int, input().split())
    print(count[r]-count[l-1])

### FIXED CODE ###

q = int(input())
    
def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True

ls = [0]

for i in range(1,100000):
    if is_prime(i) and is_prime((i+1)//2):
        ls.append(ls[i-1]+1)
    else:
        ls.append(ls[i-1])
        
for i in range(q):
    l,r = map(int,input().split())
    if l == r:
        if is_prime(l) and is_prime((l+1)//2):
            print(1)
        else:
          print(ls[r]-ls[l-1])  
    else:
        print(ls[r]-ls[l-1])
a, b, c, k = map(int, input().split())
    
if(k-a-b<=0):
    print(max(1*a+0*(k-a)))
else :
    print(max(1*a+0*b-1*(k-a-b)))

### FIXED CODE ###

a, b, c, k = map(int, input().split())
    
if(k-a<=0):
    print(k)
elif(k-a-b<=0):
    print(1*a - 0*(k-a))
else :
    print(1*a+0*b-1*(k-a-b))
N = int(input())
arr = list(map(int,input().split()))
arr = sorted(arr,reverse=True)
ans = 1
idx = 0
for a in arr:
  ans *= a
  if ans > 10**18:
    print(-1)
    exit()
print(ans)

### FIXED CODE ###

a,b = map(int,input().split())
print(a*b)
N = int(input())
ls = list(map(int,input().split()))
    
ls1 = sorted(ls)
ii = 0
if ls[0] == ls[1]:
    ii = ii + 1
for i in range(N):
    for j in ls1[:i]:
        if ls1[i] % j == 0:
            ii += 1
            break
        elif ls1[i]/2 <= j :
            break

print(N-ii)

### FIXED CODE ###

N = int(input())
ls = list(map(int,input().split()))
    
Pls = [0] * (10**6+1)

for i in ls:
    Pls[i] += 1

ii = 0
for j in range(len(Pls)):
    if Pls[j] == 0:
        continue
    elif Pls[j] == 1:
        ii += 1
        t = 2*j
        while t <= 10**6:
            Pls[t] = 0
            t += j
    else:
        t = 2*j
        while t <= 10**6:
            Pls[t] = 0
            t += j

print(ii)
import sympy as sym
(a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z) = sym.symbols('a b c d e f g h i j k l m n o p q r s t u v w x y z')

A = sym.sequence((N*(N+1))/2,(n, 1, 100))
print([int(N) for in A])

### FIXED CODE ###

N = int(input())

print(int(N*(N+1)/2))
N = input()
n = len(list(n))
d_list = [9, 900, 90000]
if n >= 5:
  ans = 90909
elif n >= 4:
  ans = 909
elif n >= 3:
  ans = 9 + N % 1000
elif n >= 2:
  ans = 9
else:
  ans = N % 10
print(ans)

### FIXED CODE ###

N = int(input())
n = len(list(str(N)))
if n >= 6:
  ans = 90909
elif n >= 5:
  ans = 909 + (N - 9999)
elif n >= 4:
  ans = 909
elif n >= 3:
  ans = 9 + (N - 99)
elif n >= 2:
  ans = 9
else:
  ans = N
print(ans)
import fractions

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

a = A[0]
for i in range(1, N):
    gcc = a * A[i] // fractions.gcd(a, A[i])
    a = gcc
    
b = 0
for i in range(N):
    b = b + gcc // A[i]

c = b % (1000000007)
print(c)

### FIXED CODE ###

import fractions

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

a = 1
for i in range(N):
    g = a * A[i] // fractions.gcd(a, A[i])
    a = g
    
b = 0
for i in range(N):
    b = b + g // A[i]

c = b % (1000000007)
print(c)
from heapq import *
import numpy as np
n,m,s,t=map(int,input().split())
a=[[]for i in range (n+1)]
b=[[]for i in range(n+1)]
for i in range(m):
    p,q,r,g=map(int,input().split())
    a[p].append([q,r])
    a[q].append([p,r])
    b[p].append([q,g])
    b[q].append([p.g])
def f(x,r):
    p=[float("INF")]*(n+1)
    p[x],q=0,[[0,x]]
    while q:
        y,z=heappop(q)
        for i in r[z]:
            if p[i[0]]>y+i[1]:
                heappush(q,[y+i[1],i[0]])
    return p
s1,t1=f(s,a),f(t,b)
q=np.array(s1[1:])+np.array(t1[1:])
q=q.tolist()
for i in range(n):
    print(10**15-min(q))
    q=q[1:]

### FIXED CODE ###

from heapq import heappush,heappop
n,m,s,t=map(int,input().split())
a,b=[[]for i in range (n+1)],[[]for i in range(n+1)]
for i in range(m):
    p,q,r,g=(int(i) for i in input().split())
    a[p].append((q,r))
    a[q].append((p,r))
    b[p].append((q,g))
    b[q].append((p,g))
def f(x,r):
    p=[float("inf")for i in range(n+1)]
    p[x],q=0,[[0,x]]
    while q:
        y,z=heappop(q)
        for i,j in r[z]:
            if p[i]>y+j:
                p[i]=y+j
                heappush(q,[p[i],i])
    return p
s1,t1,p=f(s,a),f(t,b),[]
for i in range(1,n+1):
    p.append((s1[i]+t1[i],i))
p,e=sorted(p),0
for i in range(n):
    while p[e][1]<=i: e+=1
    print(10**15-p[e][0])
N = int(input())

tree = {}
for i in range(1,N):
    u, v, w = map(int, input().split())
    w = w%2
    if u in tree:
        tree[u].append([v,w])
    else:
        tree[u] = [[v,w]]

    if v in tree:
        tree[v].append([u,w])
    else:
        tree[v] = [[u,w]]

iro = [-1]*(N)
def seachTree(current, parent):
    if len(tree[current]) == 0:
        return

    for elms in tree[current]:
        if elms[0] == parent:
            continue
        if elms[1] == 0:
            iro[elms[0]-1] = iro[current-1]
        else:
            iro[elms[0]-1] = not iro[current-1]

        seachTree(elms[0], current)

print(tree)
iro[0] = False
seachTree(1, 0)
for val in iro:
    print(int(val))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

N = int(input())

tree = {}
for i in range(1,N):
    u, v, w = map(int, input().split())
    w = w%2
    if u in tree:
        tree[u].append([v,w])
    else:
        tree[u] = [[v,w]]

    if v in tree:
        tree[v].append([u,w])
    else:
        tree[v] = [[u,w]]

iro = [-1]*(N)
def seachTree(current, parent):
    if len(tree[current]) == 0:
        return

    for elms in tree[current]:
        if elms[0] == parent:
            continue
        if elms[1] == 0:
            iro[elms[0]-1] = iro[current-1]
        else:
            iro[elms[0]-1] = not iro[current-1]

        seachTree(elms[0], current)

iro[0] = False
seachTree(1, 0)
for val in iro:
    print(int(val))
import numpy as np

def operation(infos):
  for i in xrange(len(infos)):
    for j in xrange(len(infos)):
      if(infos[j][0] == infos[i][1]):
        infos[i] = [infos[i][0],infos[j][1],infos[i][2]+infos[j][2]]
        print infos

def check(infos):
  for i in xrange(len(infos)):
    if(infos[i][0]==infos[i][1] and infos[i][2]!=0):
      return False
    for j in xrange(len(infos)):
      if(infos[i][0:2]==infos[j][0:2] and infos[i][2]!=infos[j][2]):
        return False
  return True
  


if __name__ == '__main__':

  # Get standard in
  n, m  = map(int, raw_input().split())
  infos = []
  for i in range(m):
    infos.append(map(int, raw_input().split()))

  print infos
  operation(infos)
  if(check(infos)):
    print 'Yes'
  else:
    print 'No'


### FIXED CODE ###

n = int(raw_input())
c0 = map(int, raw_input().split())
c1 = map(int, raw_input().split())

ame = []
for i in xrange(n):
  ame.append(sum(c0[:i+1]+c1[i:]))
print max(ame)
from math import gcd
def unzip(strlist,a,b):
    ret = []
    for word in strlist:
        tmp = ""
        for i in range(len(word)):
            tmp += chr(((ord(word[i])-97)*a+b)%26+97)
        ret.append(tmp)
    return ret

n = int(input())
for _ in range(n):
    instr = input().split()
    for a in range(1,26):
        if gcd(1,26)!=1 : continue
        for b in range(26):
            if "this" in unzip(instr, a, b):
                print(" ".join(unzip(instr, a, b)))
            elif "that" in unzip(instr, a, b):
                print(" ".join(unzip(instr, a, b)))

### FIXED CODE ###

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

def unzip(strlist,a,b):
    ret = []
    for word in strlist:
        tmp = ""
        for i in range(len(word)):
            tmp += chr(((ord(word[i])-97)*a+b)%26+97)
        ret.append(tmp)
    return ret

n = int(input())
for _ in range(n):
    instr = input().split()
    flag = False
    for a in range(1,26):
        if gcd(1,26)!=1 : continue
        if flag: break
        for b in range(26):
            if "this" in unzip(instr, a, b):
                print(" ".join(unzip(instr, a, b)))
                flag = True
                break
            elif "that" in unzip(instr, a, b):
                print(" ".join(unzip(instr, a, b)))
                flag = True
                break
H,W = map(int,input().split())
h,w = = map(int,input().split())
print((H-h)*(W-w))

### FIXED CODE ###

H,W = map(int,input().split())
h,w = map(int,input().split())
print((H-h)*(W-w))
N=int(input())
v=list(map(int,input().split())).sorted()
for a in range(N-1):
  v[1]=(v[0]+v[1])/2
  v.pop(0)
print(v[0])

### FIXED CODE ###

N=int(input())
v=list(map(int,input().split()))
v.sort()
for a in range(N-1):
  v[1]=(v[0]+v[1])/2
  v.pop(0)
print(v[0])
N,K = map(int,(input().split()))
V = list(map(int,(input().split())))
left = [0]*(N+1)
right = [0]*(N+1)
ans = []

for i in range(1,N+1):
    left[i] = left[i-1] + V[i-1]

for i in range(1,N+1):
    right[i] = right[i-1] + V[N-i]

for i in range(K+1):
    nega = []

    l = i
    for count in range(l):
        if l > 0 and V[count] < 0:
            nega.append(V[count])

    for j in range(K+1-i):

        r = j
        for count in range(1,r+1):
            if r > 0 and V[N-count] < 0:
                nega.append(V[N-count])

        b = K-i-j
        now = left[i] + right[j]
        nega.sort()
        s = 0
        for k in range(min(b,len(nega))):
            s += nega[k]
        
        if nega:
            ans.append(now-s)
        else:
            ans.append(now)

print(max(ans))

### FIXED CODE ###

N,K = map(int,(input().split()))
V = list(map(int,(input().split())))
left = [0]*(N+1)
right = [0]*(N+1)
ans = []

for i in range(1,N+1):
    left[i] = left[i-1] + V[i-1]

for i in range(1,N+1):
    right[i] = right[i-1] + V[N-i]


for i in range(min(N+1,K+1)):
    negal = []

    l = i
    for count in range(l):
        if l > 0 and V[count] < 0:
            negal.append(V[count])

    for j in range(min(N+1-i,K+1-i)):
        negar = []

        r = j
        for count in range(1,r+1):
            if r > 0 and V[N-count] < 0:
                negar.append(V[N-count])

        b = max(0,K-i-j)
        now = left[i] + right[j]

        nega = []
        nega.extend(negal)
        nega.extend(negar)
        nega.sort()
        s = 0
        for k in range(min(b,len(nega))):
            s += nega[k]
        
        if nega:
            ans.append(now-s)
        else:
            ans.append(now)

print(max(ans))