Harryxun/stf_run huggingface dataset:
"""
問題文

N個の整数 A1,A2,...,ANが黒板に書かれています。
あなたはこの中から整数を 1つ選んで、1 以上 109以下の好きな整数に書き換えます。
元の整数と同じ整数に書き換えても構いません。書き換えた後のN個の整数の最大公約数の最大値を求めてください。

制約
入力は全て整数である。
2≤N≤105
1≤Ai≤109
"""

"""
3 5 7
最大公約数: 1
最大の最大公約数: 1

8 4 6
最大公約数: 2
最大の最大公約数: 4
『aとbとcの最大公約数』　＝　『aとbの最大公約数』と『c』　の最大公約数
"""
import math
from functools import reduce
def gcd(*numbers):
    return reduce(math.gcd, numbers)

def main() : 
    N = int(input())
    a_list = input().split(" ")
    a_list = [int(i) for i in a_list]
    maxValue = 0
    for i in range(N) : 
        if i == 0 : sub_a_list = a_list[1:]
        elif i == N - 1 : sub_a_list = a_list[:N-1]
        else : sub_a_list = a_list[0 : i ] + a_list[i + 1 :] 
        rst = gcd(*sub_a_list)
        if maxValue < rst : maxValue = rst
    print(maxValue)
main()


### FIXED CODE ###

"""
問題文

N個の整数 A1,A2,...,ANが黒板に書かれています。
あなたはこの中から整数を 1つ選んで、1 以上 109以下の好きな整数に書き換えます。
元の整数と同じ整数に書き換えても構いません。書き換えた後のN個の整数の最大公約数の最大値を求めてください。

制約
入力は全て整数である。
2≤N≤105
1≤Ai≤109
"""

"""
3 5 7
最大公約数: 1
最大の最大公約数: 1

8 4 6
最大公約数: 2
最大の最大公約数: 4
『aとbとcの最大公約数』　＝　『aとbの最大公約数』と『c』　の最大公約数

A1 , A2 , A3 ... An

gcd(A1 , A2 , A3 ... An-1) * N
= gcd * N * N
= gcd * N^2

gcd(A1 , A2 , A3 ... An-1)
gcd(A1 , A2 , A3 ... An-2 , An) = gcd(A1 , A2 , A3 ... An-2) , An
"""
def gcd(a, b):  # a>b
    a, b = max(a, b), min(a, b)
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

from functools import reduce
def GCD(numbers):
    if len(numbers) == 0 : return 0
    if len(numbers) == 1 : return numbers[0]
    if len(numbers) == 2 : 
        return gcd(numbers[0] , numbers[1])
    else : 
        value = GCD(numbers[:len(numbers)-1])
        result = gcd(value , numbers[len(numbers) - 1])
        return result

def main() : 
    N = int(input())
    a_list = input().split(" ")
    a_list = [int(i) for i in a_list]
    R = [0 for i in range(N - 1)]
    L = [0 for i in range(N - 1)]
    R[0] = a_list[0]
    L[0] = a_list[-1]

    for i in range(1 , N-1) : 
        R[i] = gcd(R[i - 1] , a_list[i])
    
    for j in range(1 , N-1) : 
        L[j] = gcd(L[j - 1] , a_list[- j - 1])
    
    maxValue = 0
    for i in range(N - 2) : 
        value = gcd(R[i] , L[N - i - 3])
        if value > maxValue : maxValue = value
    print(max(maxValue , R[-1] , L[-1]))
main()
n,L = map(int,input().split())
N=0
G=0
for i in range(1,n):
    N +=(i+L-1)
NN = N
for i in range(1,n):
        DD = NN - (L+i-1)
        if DD>G :
            G = DD
print(G)
    

### FIXED CODE ###

A=str(input () )
B=0
while B!=3:
    if A[B]==A[B+1]:
        print('Bad')
        break
    else:    
        B=B+1
else:
    print('Good')
#入力
lst = input().spilit()

#整数値化
for i in range(len(lst)):
   lst[i] = int(lst[i])

#ソート
lst.sort()

#出力
if lst[0] == lst[2]
   print(3)
elif lst[0] == lst[1] or lst[1] == lst[2]:
   print(2)
else:
   print(1)

### FIXED CODE ###

#入力
lst = input().split()

#整数値化
for i in range(len(lst)):
   lst[i] = int(lst[i])

#ソート
lst.sort()

#出力
if lst[0] == lst[2]:
   print(1)
elif lst[0] == lst[1] or lst[1] == lst[2]:
   print(2)
else:
   print(3)
n,q=map(int,input().split())
s=input()
ac=[0]*n
for i in range(0,len(s)):
  if s[i]=='A' and s[i+1]=='C':
    ac[i]=1
for i in range(q):
  l,r=map(int,input().split())
  ans=0
  for j in range(l-1,r-1):
    ans+=ac[j]
  print(ans)

### FIXED CODE ###

n,q=map(int,input().split())
s=input()
a=[0]*(n)
for i in range(n-1):
  if s[i]=='A' and s[i+1]=='C':
    a[i+1]=a[i]+1
  else:
    a[i+1]=a[i]
for i in range(q):
  l,r=map(int,input().split())
  ans=a[r-1]-a[l-1]
  print(ans)
n = int(input())
a = list(map(int, input().split()))

if n%2 != 0:
  a.append(0)
  n += 1
 
a.sort()
d = 0

for i in range(int(n/2):
               d += a[2i+1]-a[2i]
           
print(d)

### FIXED CODE ###

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

if n%2 != 0:
  a.append(0)
  n += 1
 
a.sort()
d = 0

for i in range(int(n/2)):
               d += a[2*i+1]-a[2*i]
           
print(d)
S,T=open(0).read().split()
def main():
    for i in range(1,len(T)+1):
        for j in range(i+1):
            print(T[j:(len(T)-i+j)], S[j:(len(S)-i+j)])
            if T[j:(len(T)-i+j)] in S[j:(len(S)-i+j)]:
                return i
                break
if T in S:
    print(0)
else:
    print(main())

### FIXED CODE ###

S,T=open(0).read().split()
score = 0
for i in range(len(S)-len(T)+1):
    score=max(score,sum([T[k]==S[i+k] for k in range(len(T))]))
print(len(T)-score)
n, m = map(int, input().split())
h = list(input().split())
l = [0] * n

for i in range(0, int(m)):
    a, b = map(int, input().split())
    a_int = int(h[int(a)-1])
    b_int = int(h[int(b)-1])

    if (a_int < b_int):
        l[b_int - 1] = 1
       
cnt = 0
for k in range(0, len(l)):
    if(l[k]==1):
        cnt+=1

print(cnt)

### FIXED CODE ###

n, m = map(int, input().split())
h = list(input().split())
l = [1] * n

for i in range(0, int(m)):
    a, b = map(int, input().split())
    a_int = int(h[int(a)-1])
    b_int = int(h[int(b)-1])

    if (a_int < b_int):
        l[a - 1] = 0
    
    if (a_int > b_int):
        l[b - 1] = 0
    
    if (l[a-1] == 1):
        if (a_int == b_int):
            l[a - 1] = 0
            l[b - 1] = 0
    elif (l[b-1] == 1):
        if (a_int == b_int):
            l[a - 1] = 0
            l[b - 1] = 0 
       
cnt = 0
for k in range(0, len(l)):
    if(l[k]==1):
        cnt+=1

print(cnt)
import numpy as np
import sys

mod = 10 ** 9 + 7

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

if N == K:
    print(numpy.cumprod(A))
    sys.exit()

plus = A[A>=0]
minus = A[A<0]

if len(minus) == N:
    np.sort(minus)[::-1]
    print(numpy.cumprod(A[:K]))
    sys.exit()

ans = 1
flag = 0
if K % 2 == 1:
    flag = 1
    K -= 1
    ans *= plus[0]

n_plus = [(plus[i+flag] * plus[i+flag+1]) % mod for i in range((len(plus)-flag)//2)]
n_minus = [(minus[i] * minus[i+1]) % mod for i in range(len(minus)//2)]

p = 0
m = 0
for i in range(K//2):
    if p == len(n_plus):
        ans *= n_minus[m]
        ans %= mod
        m += 1
    elif m == len(n_minus):
        ans *= n_plus[p]
        ans %= mod
        p += 1
    elif n_plus[p] > n_minus[m]:
        ans *= n_plus[p]
        ans %= mod
        p += 1
    else:
        ans *= n_minus[m]
        ans %= mod
        m += 1

print(ans)

### FIXED CODE ###

import sys

mod = 10 ** 9 + 7

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

A.sort(reverse = True)

if A[0] < 0 and K % 2 == 1:
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans %= mod
    print(ans)
    sys.exit()

l = 0
r = N-1

ans = 1
if K % 2 == 1:
    ans *= A[0]
    l += 1

for _ in range(K // 2):
    if A[l] * A[l+1] > A[r] * A[r-1]:
        ans *= A[l] * A[l+1]
        ans %= mod
        l += 2
    else:
        ans *= A[r] * A[r-1]
        ans %= mod
        r -= 2

print(ans)
n = input()
s = []
h = []
c = []
d = []

for i in range(n):
  card = raw_input().split(" ")
  card[1] = int(card[1])
  if card[0] == "S":
  	s.append(card[1])
  if card[0] == "H":
  	h.append(card[1])
  if card[0] == "C":
  	c.append(card[1])
  if card[0] == "D":
  	d.append(card[1])

def sort_list(lst):
#make a temporary file for storing data
  temp = []
  for i in range(1,14):
    if i not in lst:
	temp.append(i)
  lst = sorted(temp)
  return lst
  
check_cards(mark,lst):
	lst = sort_list(lst)
	for i in lst:
		print mark+" "+str(i)

check_cards(S,s)
check_cards(H,h)
check_cards(C,c)
check_cards(D,d)

### FIXED CODE ###

n = int(raw_input())
lst = []
#store all the cards
for i in ["S","H","C","D"]:
	for j in xrange(1,14):
		lst.append("{0} {1}".format(i,j))
#discard the given cards
for i in range(n):
	a = raw_input()
	lst.remove(a)
#print the result
for i in range(len(lst)):
	print lst[i]
import sys
import math
import heapq
mod=10**9+7
inf=float("inf")
from math import sqrt
from collections import deque
from collections import Counter
from math import ceil
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from functools import lru_cache
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########

A=list(map(int,input().split()))
n=len(A)
PM=[[0,0] for i in range(n)]
for i in range(n):
    now=0
    mini=0
    for j in A[i]:
        if j=="(": now+=1 
        else:
            now-=1 ; mini=min(mini,now)
    PM[i]=[mini,now]

if sum([PM[i][1] for i in range(n)]  )!=0 : 
    print("No")
    exit()

MINI=0
NOW=0
PMf=[PM[i] for i in range(n) if PM[i][1]>=0]
PMf.sort()
for i in range(len(PMf)):
    MINI=min(MINI , NOW+PMf[-i-1][0] )
    NOW+=PMf[-i-1][1]
    if MINI<0 : print("No") ; exit()

PMs=[PM[i] for i in range(n) if PM[i][1]<0]
PMs=sorted(PMs , key=lambda x : x[1]-x[0])
for i in range(len(PMs)):
    MINI=min(MINI , NOW+PMs[-i-1][0] )
    NOW+=PMs[-i-1][1]
    if MINI<0 : print("No") ; exit()

print("Yes")


### FIXED CODE ###

import sys
input=lambda: sys.stdin.readline().strip()


n=int(input())
A=[]
#
PM=[[0,0] for i in range(n)]
for i in range(n):
    now=0
    mini=0
    for j in input():
        if j=="(": now+=1 
        else:
            now-=1 ; mini=min(mini,now)
    PM[i]=[mini,now]

if sum( [PM[i][1] for i in range(n)]  )!=0 : 
    print("No")
    exit()

MINI=0
NOW=0
PMf=[PM[i] for i in range(n) if PM[i][1]>=0]
PMf.sort()
for i in range(len(PMf)):
    MINI=min(MINI , NOW+PMf[-i-1][0] )
    NOW+=PMf[-i-1][1]
    if MINI<0 : print("No") ; exit()

PMs=[PM[i] for i in range(n) if PM[i][1]<0]
PMs=sorted(PMs , key=lambda x : x[1]-x[0])
for i in range(len(PMs)):
    MINI=min(MINI , NOW+PMs[-i-1][0] )
    NOW+=PMs[-i-1][1]
    if MINI<0 : print("No") ; exit()

print("Yes")
n = int(input())
res = 1
for i in range(1,n+1):
    for k in range(2,1+n):
        num = i**k
        if num > n:
            break
        if num <= n :
            res = max(res,num)
    
print(res)

### FIXED CODE ###

a,b,c,d = map(int,input().split())
if abs(a-b)<=d and abs(b-c)<=d:
     print("Yes")
elif abs(a-c)<=d:
    print("Yes")
else:
    print("No")
a,b=map(int,input().split())
s=sum(map(int,input().split()))
print("Yes" if a>=s else "No")


### FIXED CODE ###

H,A =map(int,input().split())
print(H//A+(1 if not H%A==0 else 0))
N, Q = (int(i) for i in input().split())  
s = input()
s="!"+s+"?"
spells = [input().split() for _ in range(Q)]
 
masu=[1]*(N+2)
for spell in spells:
   t=spell[0]
   d=spell[1]
   indexes = [i for i, x in enumerate(s) if x == t]
   if d=="R":
      for index in indexes:
         index=index+1
         masu[index]+=masu[index-1]
         masu[index-1]=0
   else:
      for index in indexes:
         masu[index]+=masu[index+1]
         masu[index+1]=0
 
masu.pop(0)
masu.pop(N)
print(sum(masu)+1)

### FIXED CODE ###

a, b, c = (int(i) for i in input().split())  
if a==b and b==c and a==c:
   print('Yes')
else:
   print('No')
n=int(input())
hoge=list(map(int,input().split()))

print(max(hoge)-min()hoge)

### FIXED CODE ###

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

print(max(hoge)-min(hoge))
S = int(input())
W = int(input())

if S <= W:
    print('unsafe')
else:
    print('safe')


### FIXED CODE ###

S, W = map(int,input().split())

if S <= W:
    print('unsafe')
else:
    print('safe')
A = int(input())
P = int(input())
B = 3*A + P

print(int(B/3))

### FIXED CODE ###

A,P = map(int,input().split())
print((3*A + P) // 2)
s = map(int, input().split())

A, B, C, D = [i for i in s]

greater = max(A, C)
less = min(B, D)

if min(0, greater - less):
　print(min(0, greater- less)
else:
   print("0")

### FIXED CODE ###

N = input()

if N == N[::-1]:
  print('Yes')
else:
  print('No')
n,m = map(int,input().split())
a = list(map(int,input().split()))

# for i in range(m):
#     a = sorted(a)
#     b,c = map(int,input().split())
#     for j in range(b):
#         if a[j] >= c:
#             break
#         else:
#             a[j] = c
# print(sum(a))
d = []
for i in range(m):
    b,c = map(int,input().split()) # b 交換できる枚数 c:カードの値
    d.append((b,c))

# dを降順にsorted
d = sorted(d,key=lambda x: x[1], reverse=True)

for i in range(m):
    b,c = d[i]
    a.extend([c]*b)
    if len(a) > 2*N:
        break

print(sum(sorted(a)[-n:]))

### FIXED CODE ###

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

# for i in range(m):
#     a = sorted(a)
#     b,c = map(int,input().split())
#     for j in range(b):
#         if a[j] >= c:
#             break
#         else:
#             a[j] = c
# print(sum(a))
d = []
for i in range(m):
    b,c = map(int,input().split()) # b 交換できる枚数 c:カードの値
    d.append((b,c))

# dを降順にsorted
d = sorted(d,key=lambda x: x[1], reverse=True)

for i in range(m):
    b,c = d[i]
    a.extend([c]*b)
    if len(a) > 2*n:
        break

print(sum(sorted(a)[-n:]))
# -*- coding: utf-8 -*-
import sys
N,M=list(map(int,raw_input().split()))

nl=[[] for i in range(N+1)]
for i in range(M):
	x,y=map(int,raw_input().split())
	nl[x].append(y)
	nl[y].append(x)	
#print nl


def dfs(v,p):
	F[v]=1
	for i in nl[v]:
		if color[v]=="w" and color[i]==0:
			color[i]="b"
		elif color[v]=="b" and color[i]==0:
			color[i]="w"				
		elif color[v]==color[i]:
			#２部グラフではない
			print N*(N-1)/2-M
			sys.exit()
		#print v,i,color,F
		
		if F[i]==0:
			#DFS(次の頂点i, 次に親となる頂点v)
			#print "dfs::"+str(i)
			dfs(i,v)


F=[0]*(N+1)
color=[0]*(N+1)
color[1]="w"
dfs(1,-1)

#２部グラフの場合
print color.count("b")*color.count("w")-M


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**7)
N,M=list(map(int,raw_input().split()))

nl=[[] for i in range(N+1)]
for i in range(M):
	x,y=map(int,raw_input().split())
	nl[x].append(y)
	nl[y].append(x)	
#print nl


def dfs(v):
	F[v]=1
	for i in nl[v]:
		if color[v]=="w" and color[i]==0:
			color[i]="b"
		elif color[v]=="b" and color[i]==0:
			color[i]="w"				
		elif color[v]==color[i]:
			#２部グラフではない
			print N*(N-1)/2-M
			sys.exit()
		else:
			continue
		#print v,i,color,F
		
		if F[i]==0:
			dfs(i)


F=[0]*(N+1)
color=[0]*(N+1)
color[1]="w"
dfs(1)

#２部グラフの場合
print color.count("b")*color.count("w")-M
a = int(input())
b = int(input())

print("%d %d"%((a*b),(2*a+2*b)))

### FIXED CODE ###

a,b = map(int, raw_input().split())
c = a*b
d = 2*(a+b)
print'%d %d'%(c,d)
def main():
    S = sorted(int(input()))
    if S[0] == S[1] or S[1] == S[2] or S[2] == S[3]:
        print("Bad")
    else:
        print("Good")


if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    S = input()
    if S[0] == S[1] or S[1] == S[2] or S[2] == S[3]:
        print("Bad")
    else:
        print("Good")


if __name__ == "__main__":
    main()
N, X = map(int,input().split())

L = input().split()
pos = 0
ans = 1
for i in range(N+1):
  pos += int(L[i])
  if(pos <= X):
    ans +=1
  else:
    break
  
print(ans)


### FIXED CODE ###

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

L = input().split()
pos = 0
ans = 1
for i in range(N):
  pos += int(L[i])
  if(pos <= X):
    ans +=1
  else:
    break
  
print(ans)
A, P = map(int, input().split())
print((A*3 + p)//2)

### FIXED CODE ###

A, P = map(int, input().split())
print((A*3 + P)//2)
h, w = map(int, input().split())
if h == 1 or w == 1
  print(1)
else:
  print(h*w//2 + (w*h % 2))

### FIXED CODE ###

h, w = map(int, input().split())
if h == 1 or w == 1:
  print(1)
else:
  print(h*w//2 + (w*h % 2))
N = input()
o = 1000-(N%1000) 
print(o)

### FIXED CODE ###

N = int(input())
o = (1000-N%1000)%1000
print(o)
a, b, c = = map(int, raw_input().split())
if (a * 100 + b * 10 + c) % 4 == 0:
    print "yes"
else:
    print "no"

### FIXED CODE ###

a, b, c = map(int, raw_input().split())
if (a * 100 + b * 10 + c) % 4 == 0:
    print "YES"
else:
    print "NO"
import math
a,b = map(int,input().split())
print(a*b//math.gcd(a,b))


### FIXED CODE ###

import fractions
a,b=map(int, input().split())
print((a*b)//fractions.gcd(a,b))
import math
import sys

#n, a, b= map(int, input().split())
n, m  = map(int, input().split())
#s = list(str(input()))
#n = int(input())
#a = list(map(int, input().split()))

a = [""]*m
b = [""]*m
for i in range(m):
  #a[i] = int(input())
  a[i], b[i] = map(int, input().split())

num = [int(i+1) for i in range(m)]
count = [0]*n

for i in range(m):
  for ii in range(n):
    if(a[i] == num[ii]):
      count[ii] = count[ii] + 1
    if(b[i] == num[ii]):
      count[ii] = count[ii] + 1

for i in range(n):
  print(count[i])

### FIXED CODE ###

import math
import sys

#n, a, b= map(int, input().split())
n, m  = map(int, input().split())
#s = list(str(input()))
#n = int(input())
#a = list(map(int, input().split()))

a = [""]*m
b = [""]*m
for i in range(m):
  #a[i] = int(input())
  a[i], b[i] = map(int, input().split())

num = [int(i+1) for i in range(n)]
count = [0]*n

for i in range(m):
  for ii in range(n):
    if(a[i] == num[ii]):
      count[ii] = count[ii] + 1
    if(b[i] == num[ii]):
      count[ii] = count[ii] + 1

for i in range(n):
  print(count[i])
import sys.stdin.readline
input = readline

N,Q = [int(i) for i in input().split()]
S = input()

ans = []
for _ in range(Q):
    a,b = [int(i) for i in input().split()]
    ans.append(S[a-1:b].count('AC'))

[print(i) for i in ans]


### FIXED CODE ###

import itertools
N,Q = [int(i) for i in input().split()]
S = list(input())

li = [0]*N
for i in range(N-1):
    if S[i] == 'A' and S[i+1] == 'C':
        li[i+1] = 1
ans = list(itertools.accumulate(li))
k = []
for j in range(Q):
    a,b = [int(i) for i in input().split()]
    k.append(ans[b-1]-ans[a-1])

[print(i) for i in k]
import copy
R, C, K = map(int,input().split())
i = [list(map(int,input().split())) for k in range(K)]
dp = []
for k in range(4):
   dp.append([])
   for r in range(R):
      dp[k].append([])
      for c in range(C):
         dp[k][r].append([])
         dp[k][r][c] = 0
location = copy.deepcopy(dp[0])
for k in range(K):
   location[i[k][0]-1][i[k][1]-1] = i[k][2]
dp[1][0][0] = location[0][0]
if R > 1:
   for r in range(R-1):
      dp[1][r+1][0] = location[r][0] + dp[1][r][0]
      dp[0][r+1][0] = max(dp[1][r][0],dp[0][r][0])
if C > 1:
   for c in range(C-1):
         dp[1][0][c+1] = max(location[0][c+1] + dp[0][0][c], dp[1][0][c])
         dp[2][0][c+1] = max(location[0][c+1] + dp[1][0][c], dp[2][0][c])
         dp[3][0][c+1] = max(location[0][c+1] + dp[2][0][c], dp[3][0][c])
   if R > 1:
      for r in range(R-1):
         for c in range(C-1):
            dp[0][r+1][c+1] = max(dp[0][r+1][c], dp[0][r][c+1], dp[1][r][c+1], dp[2][r][c+1], dp[3][r][c+1])
            dp[1][r+1][c+1] = max(dp[0][r+1][c+1] + location[r+1][c+1], dp[1][r+1][c])
            dp[2][r+1][c+1] = max(dp[1][r+1][c] + location[r+1][c+1], dp[2][r+1][c])
            dp[3][r+1][c+1] = max(dp[2][r+1][c] + location[r+1][c+1], dp[3][r+1][c])
if R==1 and C==1:
   ans = i[2]
else:
   ans = max(dp[0][R-1][C-1], dp[1][R-1][C-1], dp[2][R-1][C-1], dp[3][R-1][C-1])
print(ans)

### FIXED CODE ###

import sys
import copy
R, C, K = map(int, input().split())
item = [[0] * (C + 1) for _ in range(R + 1)]  # dp配列と合わせるために, 0行目, 0列目を追加している.
for s in sys.stdin.readlines():
    r, c, v = map(int, s.split())
    r -= 1
    c -= 1
    item[r][c] = v
    
dp0 = [[0] * (C+1) for r in range(R+1)]
dp1 = [[0] * (C+1) for r in range(R+1)]
dp2 = [[0] * (C+1) for r in range(R+1)]
dp3 = [[0] * (C+1) for r in range(R+1)]
 
for r in range(R):
   for c in range(C):
      dp3[r][c] = max(dp3[r][c], dp2[r][c] + item[r][c])
      dp2[r][c] = max(dp2[r][c], dp1[r][c] + item[r][c])
      dp1[r][c] = max(dp1[r][c], dp0[r][c] + item[r][c])
      dp1[r][c+1] = max(dp1[r][c], dp1[r][c+1])
      dp2[r][c+1] = max(dp2[r][c], dp2[r][c+1])
      dp3[r][c+1] = max(dp3[r][c], dp3[r][c+1])
      dp0[r+1][c] = max(dp0[r+1][c], dp1[r][c])
      dp0[r+1][c] = max(dp0[r+1][c], dp2[r][c])
      dp0[r+1][c] = max(dp0[r+1][c], dp3[r][c])
ans = max(dp0[R-1][C-1], dp1[R-1][C-1])
ans = max(ans, dp3[R-1][C-1])
ans = max(ans, dp2[R-1][C-1])
print(ans)
n = input()
s = ""
for i in range(1,n+1):
    if(i%3==0 or i%10==3 or i//10==3 or i//100==3 or i//1000==3):
        s += " " + str(i)
print(s)


### FIXED CODE ###

n = int(input())
print(" ",end="")
print(*[i for i in range(1,1+n) if i%3==0 or'3' in str(i)])
import sys


def g(a, b):
    d = abs(a - b)
    return g(d, a) if a % d != 0 else d


for line in sys.stdin():
    a, b = map(int, line.split())
    c = g(a, b)
    print(c, a * b // gcd)

### FIXED CODE ###

import sys
 
def gcd(inta, intb):
    large = max(inta, intb)
    small = min(inta,intb)
    mod = large % small
    if mod ==0:
        return small
    else:
        return gcd(small, mod) 
     
def lcm(inta, intb, intgcd):
    return (inta * intb // intgcd)
 
sets = sys.stdin.readlines()
for line in sets:
    a, b = map(int, line.split())
    c = gcd(a, b)
    print(c, lcm(a, b, c))
import random
import datetime
start = datetime.datetime.now()

D = int(input())
c = [int(i) for i in input().split()]
s = []
for _ in range(D):
    s.append([int(i) for i in input().split()])
score = 0
days = [[0]*26 for i in range(D+1)]
T = []
for k in range(D):
    t = int(input())-1
    T.append(t)
    for i in range(26):
        if i == t:
            days[k+1][i] = 0
        else:
            days[k+1][i] = days[k][i]+1
    score += s[k][t]
    for i in range(26):
        score -= days[k+1][i]*c[i]
now = datetime.datetime.now()
while not (now.second - start.second == 1 and (now.microsecond - start.microsecond + 100000)%100000 > 90000):
    d = random.randint(0, D-1)
    q = random.randint(0, 25)
    diff = s[d][q] - s[d][T[d]]
    i = d+1
    for k in range(d+1,D):
        if T[k] == q:
            i = k
            break
    else:
        i = D
    j = d+1
    for k in range(d+1,D):
        if T[k] == T[d]:
            j = k
            break
    else:
        j = D
    diff -= c[T[d]]*(days[d][T[d]]+1)*(j-d) - c[q]*days[d+1][q]*(i-d)
    now = datetime.datetime.now()
    if diff <= 0:
        continue
    score += diff
    L = days[d+1][q]
    for k in range(d+1,i+1):
        days[k][q]  -= L
    L = days[d][T[d]]+1
    for k in range(d+1,j+1):
        days[k][T[d]] += L
    T[d] = q
T = [str(i) for i in T]
print("\n".join(T))

### FIXED CODE ###

D = int(input())
c = [int(i) for i in input().split()]
days = [0]*26
ans = []
for k in range(D):
    s = [int(i) for i in input().split()]
    t = 0
    for i in range(1,26):
        if s[t] + days[t]*c[t] <= s[i] + days[i]*c[i]:
            t = i
    ans.append(t)
    for i in range(26):
        if i == t:
            days[i] = 0
        else:
            days[i] += 1
ans = [str(i+1) for i in ans]
print("\n".join(ans))
n,a,b = map(int, input().split())
cnt = 0

def digidsum(x):
  s = str(n)
  array_list = list(map(int,s))
  return sum(array_list)



for i in range(n):
  if sum(i+1) >= a and sum(i+1) <= b:
    cnt += i
print(cnt)

### FIXED CODE ###

n,a,b = map(int, input().split())
cnt = 0

def digidsum(x):
  s = str(x)
  array_list = list(map(int,s))
  return sum(array_list)



for i in range(n):

  if digidsum(i+1) >= a and digidsum(i+1) <= b:
    cnt += i+1
    
print(cnt)
N, C, K = [int(i) for i in input().split()]
T = list(sorted([int(i) for i in input().split()]))
ans = 1
limit = 0
ti = T[0]
for i in range(N - 1):
    limit += 1
    if ti + K < T[i + 1] or limit == C:
        ti = T[i + 1]
        ans += 1
        limit = 0
print(ans)


### FIXED CODE ###

N, C, K = [int(i) for i in input().split()]
T = sorted([int(input()) for i in range(N)])
ans = 1
limit = 0
ti = T[0]
for i in range(N - 1):
    limit += 1
    if ti + K < T[i + 1] or limit == C:
        ti = T[i + 1]
        ans += 1
        limit = 0
print(ans)
import math

print(int(input() * 2 * math.pi())


### FIXED CODE ###

import math

print(int(input()) * 2 * math.pi)
s = input()
ans = 'CODEFESTIVAL2016'
cnt = 0
for i in range(n):
  if s[i] != ans[i]:
    cnt += 1
print(cnt)


### FIXED CODE ###

s = input()
ans = 'CODEFESTIVAL2016'
cnt = 0
for i in range(len(s)):
  if s[i] != ans[i]:
    cnt += 1
print(cnt)
##C problem
N = int(input())
v = list(map(float, input().split()))
##初期処理
a=min(v)
##最初に出てくる指定した要素を削除
#v.remove(a)
#v.remove(b)
#v.append( (a+b)/2 )

for i in range(N-1):
        a=v[-1]
        remove(a)
        b=min(v)
        v.remove(b)
        v.append((a+b)/2)

### FIXED CODE ###

##C problem
N = int(input())
v = list(map(float, input().split()))

vs = sorted(v)

for i in range(N-1):

    a=vs[0]

    b=vs[1]
    c=(a+b)/2
    vs.remove(b)
    vs.insert(0,c)
    vs.remove(a)
    #print(i)
    #print(vs)

print(vs[0])