Harryxun/stf_run huggingface dataset:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))


from collections import defaultdict
import heapq
n, m = map(int, input().split())
a = list(map(int, input().split()))
ns = defaultdict(set)
for _ in range(m):
    u,v = map(int, input().split())
    ns[u].add(v)
    ns[v].add(u)

score = 0
count = 0
others = []
seen = [False] * n
for start in range(n):
    if seen[start]:
        continue
    count += 1
    q = [start]
    s = [a[start]]
    seen[start] = True
    while q:
        u = q.pop()
        for v in ns[u]:
            if not seen[v]:
                heapq.heappush(s, a[v])
                q.append(v)
                seen[v] = True
    score += heapq.heappop(s)
    others = heapq.merge(others, s)
if n<2*(count-1):
    print("Impossible")
elif count==1:
    print(0)
else:
    for _ in range(2*(count-1)-count):
        score += heapq.heappop(others)
    print(score)

### FIXED CODE ###

# APC001D
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))


from collections import defaultdict
import heapq
n, m = map(int, input().split())
a = list(map(int, input().split()))
ns = defaultdict(set)
for _ in range(m):
    u,v = map(int, input().split())
    ns[u].add(v)
    ns[v].add(u)

score = 0
count = 0
others = []
seen = [False] * n
for start in range(n):
    if seen[start]:
        continue
    count += 1
    q = [start]
    s = [a[start]]
    seen[start] = True
    while q:
        u = q.pop()
        for v in ns[u]:
            if not seen[v]:
                heapq.heappush(s, a[v])
                q.append(v)
                seen[v] = True
    score += heapq.heappop(s)
    for item in s:
        heapq.heappush(others, item)

if n<2*(count-1):
    print("Impossible")
elif count==1:
    print(0)
else:
    for _ in range(2*(count-1)-count):
        score += heapq.heappop(others)
    else:
        print(score)
from bisect import bisect_left,insort_left
n=int(input())
s=input()
lindex=[[] for _ in range(26)]
for i in range(n):
  lindex[ord(s[i])-97].append(i)
q=int(input())
for i in range(q):
  q1,q2,q3=input().split()
  if q1=='1':
    q2=int(q2)-1
    idx=bisect_left(lindex[ord(s[q2])-97],q2)
    if s[q2]!=q3:
      del lindex[ord(s[q2])-97][idx]
      insort_left(lindex[ord(q3)-97],q2)
  else:
    l=int(q2)-1
    r=int(q3)-1
    cnt=0
    for j in range(26):
      if len(lindex[j])==0:
        continue
      idx=bisect_left(lindex[j],l)
      if len(lindex[j])>idx and lindex[j][idx]<=r:
        cnt+=1
    print(cnt)

### FIXED CODE ###

from bisect import bisect_left,insort_left
n=int(input())
s=list(input())
lindex=[[] for _ in range(26)]
for i in range(n):
  lindex[ord(s[i])-97].append(i)
q=int(input())
for i in range(q):
  q1,q2,q3=input().split()
  if q1=='1':
    q2=int(q2)-1
    idx=bisect_left(lindex[ord(s[q2])-97],q2)
    if s[q2]!=q3:
      del lindex[ord(s[q2])-97][idx]
      insort_left(lindex[ord(q3)-97],q2)
      s[q2]=q3
  else:
    l=int(q2)-1
    r=int(q3)-1
    cnt=0
    for j in range(26):
      if len(lindex[j])==0:
        continue
      idx=bisect_left(lindex[j],l)
      if len(lindex[j])>idx and lindex[j][idx]<=r:
        cnt+=1
    print(cnt)
data = input()

dataa,datab,datac,datad = data.split(' ')

dataa = int(dataa)
datab = int(datab)
datac = int(datac)
datad = int(datad)

length1 = dataa - datab
length2 = datab - datac
length11 = abs(length1) + abs(length2)
length3 = dataa - datac

if abs(length1) <>= datad:
    print('Yes')
elif abs(length2) <= datad:
    print('Yes')
elif abs(length11) <= datad:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

data = input()
data1,data2,data3,data4 = data.split()
data1 = int(data1)
data2 = int(data2)
data3 = int(data3)
data4 = int(data4)


if abs(data1 - data3) <= data4:
    print('Yes')
elif abs(data1 - data2) <= data4 and abs(data2 - data3) <= data4:
    print('Yes')
else:
    print('No')
import math

A = float(input())
B = float(input())

print(int(math.ceil((B - 1.0) / (A - 1.0))))

### FIXED CODE ###

import math

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

print(int(math.ceil((B - 1.0) / (A - 1.0))))
a = int(input().replace(' ', ''))
if a % 4 == 0: print('YES') else: print('NO')

### FIXED CODE ###

a = int(input().replace(' ', ''))
if a % 4 == 0:
  print('YES') 
else: 
  print('NO')
import time

nk = [int(x) for x in raw_input().strip().split()]
d = []
for i in range(nk[0]):
    d_tmp = raw_input().strip().split()
    d.append([int(d_tmp[0]), int(d_tmp[1]), int(d_tmp[2] == 'B')])

n1 = nk[0]
k1 = nk[1]

check_x = [0] * n1 * 4
check_y = [0] * n1 * 4
for i in range(n1):
    check_x[i * 4] = [d[i][0] - k1
    check_x[i * 4 + 1] = d[i][0] - k1 + 1
    check_x[i * 4 + 2] = d[i][0]
    check_x[i * 4 + 3] = d[i][0] + 1
    check_y[i * 4] = [d[i][1] - k1
    check_y[i * 4 + 1] = d[i][1] - k1 + 1
    check_y[i * 4 + 2] = d[i][1]
    check_y[i * 4 + 3] = d[i][1] + 1
check_x = list(set(check_x))
check_y = list(set(check_y))

#d = tuple(d)
n = 0
#t = time.clock()
for i in check_x:
    for j in check_y:
        n_tmp = [0, 0]
        for k in range(n1):
            x = (d[k][0] - i) // k1 % 2
            y = (d[k][1] - j) // k1 % 2
#            if x == y:
#                n_tmp[1 - d[k][2]] += 1
#            else:
#                n_tmp[d[k][2]] += 1
            n_tmp[(x == y) ^ d[k][2]] += 1
        if n_tmp[0] > n:
            n = n_tmp[0]
        if n_tmp[1] > n:
            n = n_tmp[1]
#print time.clock() - t
print n


### FIXED CODE ###

import numpy as np

def getBoundary(p, k, k2):
    if p - k + 1 >= 0:
        return [(p - k + 1, p + 1)]
    else:
        return [(0, p + 1), ((p - k + 1) % k2, k2)]

n, k = map(int, input().strip().split())
k2 = k * 2
b = [[0 for i in range(k2 + 1)] for j in range(k2 + 1)]

for i in range(n):
    x_str, y_str, c_str = input().strip().split()
    x = int(x_str) % k2
    y = (int(y_str) + (c_str == 'B') * k) % k2
    for xb, xe in getBoundary(x % k2, k, k2):
        for yb, ye in getBoundary(y % k2, k, k2):
            b[xb][yb] += 1
            b[xb][ye] -= 1
            b[xe][yb] -= 1
            b[xe][ye] += 1
    for xb, xe in getBoundary((x + k) % k2, k, k2):
        for yb, ye in getBoundary((y + k) % k2, k, k2):
            b[xb][yb] += 1
            b[xb][ye] -= 1
            b[xe][yb] -= 1
            b[xe][ye] += 1

arr_b = np.array(b)
for i in range(k2):
    arr_b[i + 1] += arr_b[i]
for j in range(k2):
    arr_b[:, j + 1] += arr_b[:, j]
print(arr_b.max())
N, M, *A = map(int, open(0).read().split())
    print(sum(A))
    vote = sum(A) / (4*M)
    num = list(filter(lambda x: x > vote, A))
    num = len(num)
    if num >= M:
      print("Yes")
    else:
      print("No")

### FIXED CODE ###

def resolve():
	N, M, *A = map(int, open(0).read().split())
	vote = sum(A) * (1 / (4*M))
	num = list(filter(lambda x: x >= vote, A))
	num = len(num)
	if num >= M:
		print("Yes")
	else:
		print("No")
resolve()
import sys

import numpy as np

readInt = lambda: int(sys.stdin.readline())
readIntN = lambda: [int(v) for v in sys.stdin.readline().split(" ")]

total = 0
ret = 1
n = readInt()
aa = []
for i in range(n):
    v = readInt()
    aa.append(v)
    total += v
    ret = (ret * 3) % 998244353

memo0 = [[-1] * 100000 for _ in range(300)]
def dfs0(i, c):
    if 0 <= memo0[i][c]:
        return memo0[i][c]

    if i == len(aa):
        memo0[i][c] = 3 if total <= (2 * c) else 0
        return memo0[i][c]

    acc = 0
    acc = (acc + dfs0(i + 1, c)) % 998244353
    acc = (acc + dfs0(i + 1, c)) % 998244353
    acc = (acc + dfs0(i + 1, c + aa[i])) % 998244353
    memo0[i][c] = acc
    return memo0[i][c]

memo1 = [[-1] * 100000 for _ in range(300)]
def dfs1(i, c):
    if 0 <= memo1[i][c]:
        return memo1[i][c]

    if i == len(aa):
        memo1[i][c] = 3 if total == (2 * c) else 0
        return memo1[i][c]

    acc = 0
    acc = (acc + dfs1(i + 1, c)) % 998244353
    acc = (acc + dfs1(i + 1, c + aa[i])) % 998244353
    memo1[i][c] = acc
    return memo1[i][c]

ret = (ret - dfs0(0, 0)) % 998244353
ret = (ret + dfs1(0, 0)) % 998244353
print(ret)

### FIXED CODE ###

import sys

readInt = lambda: int(sys.stdin.readline())
readIntN = lambda: [int(v) for v in sys.stdin.readline().split(" ")]

total = 0
ret = 1
n = readInt()
aa = []
for i in range(n):
    v = readInt()
    aa.append(v)
    total += v
    ret *= 3


L = (n * max(aa) + 1)
memo = [-1] * ((n+1) * L * 2)
def dfs(i, c):
    key = (i * L * 2) + 2 * c
    if 0 <= memo[key]:
        return memo[key: key+2]

    if i == n:
        memo[key + 0] = 3 if total <= (2 * c) else 0
        memo[key + 1] = 3 if total == (2 * c) else 0
        return memo[key: key + 2]

    v0 = dfs(i + 1, c)
    v1 = dfs(i + 1, c + aa[i])

    memo[key + 0] = (2 * v0[0] + v1[0]) % 998244353
    memo[key + 1] = (v0[1] + v1[1]) % 998244353
    return memo[key: key + 2]

a, b = dfs(0, 0)
ret = (ret - a + b) % 998244353
print(ret)
N = input()
A = list(map(int, input().split()))

count = 0
for i in all(i%2 == 0 for i in N ):
    N = [i/2 for i in N]
    count += 1
print(count)



### FIXED CODE ###

n = input()
a = list(map(int, input().split()))
cnt = 0
while all(i%2==0 for i in a):
    a = [i/2 for i in a]
    cnt += 1
print(cnt)
N, K, Q = map(int,input())
A = list(map(int,input().split()))

import numpy as np

players_score = np.array([k for i in range(k)])
for item in a:
    players_score -= 1
    players_score[item-1] += 1

indict = ['No' if i <= 0 else 'Yes' for i in players_score ]
for i in indict:
    print(i)

### FIXED CODE ###

import numpy as np

n, k, q = map(int, input().split())
a = np.array([int(input()) for i in range(q)])

players_score = np.full(n, k-q)

for item in a:
    players_score[item-1] += 1

for i in players_score:
    if i <= 0:
        print("No")
    else:
        print("Yes")
N K = map(int, inpur().split())

if N % K => 1:
  print(1)
else:
  print(0)

### FIXED CODE ###

N, K = map(int, input().split())
 
if N % K >= 1:
  print(1)
else:
  print(0)
A,B=map(int,input().split())
print(b if A >= 13 else int(b/2) if 12 >= A >= 6 else 0)

### FIXED CODE ###

A,B=map(int,input().split())
print(B if A >= 13 else int(B/2) if 12 >= A >= 6 else 0)
from collections import Counter, defaultdict, deque

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

al = list(map(int, input().split()))

if n % 2 == 0:
    lst = [0] * n
    for i in range(1, n):
        x = (al[i - 1] + n - 1) / 2
        y = x - al[i - 1]
        # print(x,y)
        # print(n-x-1,x)
        lst[int(n - x - 1)] += 1
        lst[int(x)] += 1
        if (lst[int(n - x - 1)] or lst[int(x)]) >= 3:
            print(0)
            exit()
    # print(lst)
    if 0 not in lst:
        print(int(2 ** (n / 2)) % ((10 ** 9) + 7))
    else:
        print(0)
else:
    lst = [0] * n
    for i in range(1, n):
        x = (al[i - 1] + n - 1) / 2
        y = x - al[i - 1]
        # print(x,y)
        # print(n - x - 1, x)
        lst[int(n - x - 1)] += 1
        lst[int(x)] += 1
        if (lst[int(n - x - 1)] or lst[int(x)]) >= 3:
            print(0)
            exit()
    # print(lst)
    if 0 not in lst:
        print(int(2 ** ((n - 1) / 2)) % ((10 ** 9) + 7))
    else:
        print(0)


### FIXED CODE ###

from collections import Counter

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

c_al = Counter(al)

if n % 2 == 0:
    for k,v in c_al.items():
        if v != 2:
            print(0)
            exit()
    print(pow(2, n // 2, 10 ** 9 + 7))

elif n % 2 != 0:
    for k, v in c_al.items():
        if k == 0:
            if v != 1:
                print(0)
                exit()
        elif v != 2:
            print(0)
            exit()
    print(pow(2, n // 2, 10 ** 9 + 7))
import networkx as nx
import matplotlib.pyplot as plt
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

x = I()
for i in range(-100, 100):
    for j in range(-100, 100):
        if i ** 5 - j ** 5 == x:
            print(i, j)
            exit()

for k in range(1, 10000):
    for l in range(10000):
        if (l + k) ** 5 - l ** 5 == x:
            print(l + k, l)
            exit()
        if (l + k) ** 5 - l ** 5 > x:
            break






### FIXED CODE ###

from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

x = I()
for i in range(-100, 100):
    for j in range(-100, 100):
        if i ** 5 - j ** 5 == x:
            print(i, j)
            exit()

for k in range(1, 10000):
    for l in range(10000):
        if (l + k) ** 5 - l ** 5 == x:
            print(l + k, l)
            exit()
        if (l + k) ** 5 - l ** 5 > x:
            break
n = int(input())
s = input()
baai = 0

def hanten(string):
    ans = ''
    for i in range(len(string)):
        if string[i] == 'B':
            ans += 'W'
        else:
            ans += 'B'
    return ans

def saiki(string, baai):
    if string == 'BB':
        return baai + 1
    elif string[0] == 'B':
        for i in range(1, len(string)):
            if i % 2 == 1 and string[i] == 'B':
                new_string = hanten(string[1:i]) + string[i+1:]
                baai = saiki(new_string, baai)
            elif i % 2 == 0 and string[i] == 'W':
                new_string = hanten(string[1:i]) + string[i+1:]
                baai = saiki(new_string, baai)
    else:
        return baai
    return baai

baai = saiki(s, 0)

ans = 1
for i in range(1, n+1):
    ans *= i
    ans = ans % (10**9+7)

ans = ans * baai % (10**9+7)
print(ans)

### FIXED CODE ###

mod = 10**9 + 7
n = int(input())
s = input()

crr = 0
lst= []
for i in range(2*n):
    if s[i] == 'B':
        if crr%2 == 1:
            lst.append(-1)
            crr -= 1
        else:
            lst.append(1)
            crr += 1
    else:
        if crr%2 == 1:
            lst.append(1)
            crr += 1
        else:
            lst.append(-1)
            crr -= 1

if crr!=0 or lst[0]!=1 or lst[-1]!=-1:
    print(0)
    exit()

plus = []
pcnt = 0
minus = []
mcnt = 0
where = []
for i in range(2*n):
    if lst[i] == 1:
        pcnt += 1
    else:
        mcnt += 1
        where.append(i)
    plus.append(pcnt)
    minus.append(mcnt)

ans = 1
for i in where:
    ans *= plus[i] - minus[i] + 1
    ans %= mod

for i in range(1, n+1):
    ans *= i
    ans %= mod

print(ans)
[N,M,K]= map(int, raw_input().split())
ans=["No","Yes"]
f=0
for m in range(M+1):
    for n in range(N+1):
        if K== m*N+n*M-2*m*n:
            f=1
print ans[f]


### FIXED CODE ###

S=raw_input()
if len(S)>3:
    if S[:4]=="YAKI":
        print "Yes"
    else:
        print "No"
else:
    print "No"
#C
# 7,77,777･･･=7*(1,11,111･･･)
# 7*(10^i)=7*(10^i-1)/10-1 = 7*(10^i-1)/9 がkで割れる
# 10^iを(9k,7の倍数だったら9k/7)で割ってあまりが１だったら良い
import sys
k=int(input())
if k%7==0:
    k/=7
k*=9
a=10%k
for i in range(k*9):
    a=a%k
    if a==1:
        print(i+1)
        sys.exit()
    a*=10
print(-1)

### FIXED CODE ###

#C
import sys
k=int(input())
s=0

for i in range(k):
    s=s*10+7
    if s%k!=0:
        s=s%k
    else:
        print(i+1)
        sys.exit()
print(-1)
n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse = True)
print('Yes' if a[m-1] >= 1/4M else 'No')


### FIXED CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse = True)
print('Yes' if a[m-1] >= sum(a)/4/m else 'No')
n = int(input())
h = list(map(int, input().split()))
a = []
ans = []
b = set(h)
if len(b) == 1:
  print(len(h)-1)
elif n == 0:
  print(0)
else:


  for i in range(n-1):
    if h[i] < h[i+1]:
      a.append(i+1)

  

  ans.append(a[0]-1)
  for i in range(len(a)-1):
    ans.append((a[i+1] - a[i])-1)
  ans.append((len(h) - a[len(a)-1])-1)
  if ans == []:
    print(0)
  else:
    print(max(ans))

### FIXED CODE ###

n = int(input())
h = list(map(int, input().split()))
a = []
ans = []
b = set(h)
if n == 0:
  print(0)
elif len(b) == 1:
  print(len(h)-1)
else:


  for i in range(n-1):
    if h[i] < h[i+1]:
      a.append(i+1)

  
  if a == []:
    print(len(h)-1)
  else:
    ans.append(a[0])
    ans[0] -= 1
    for i in range(len(a)-1):
      ans.append((a[i+1] - a[i])-1)
    ans.append((len(h) - a[len(a)-1])-1)
    if ans == []:
      print(0)
    else:
      print(max(ans))
n,q = map(int,input().split())
y = [[] for _ in range(n)]
c = [0 for _ in range(n)]
for _ in range(n-1):
  ai,bi = map(int,input().split())
  y[ai-1].append(bi-1)
  y[bi-1].append(ai-1)
for _ in range(q):
  pi,xi = map(int,input().split())
  c[pi-1] += xi
def f(j,b):
  for yj in y[j]:
    if yj != b:
      c[yj] += c[j]
      f(yj,j)
f(0,-1)
for i in range(n):
  print(c[i],end=" ")
    
  
  

### FIXED CODE ###

from collections import deque
def submit():
  n,q = map(int,input().split())
  y = [[] for _ in range(n)]
  c = [0]*n
  for _ in range(n-1):
    ai,bi = map(int,input().split())
    y[ai-1].append(bi-1)
    y[bi-1].append(ai-1)
  for _ in range(q):
    pi,xi = map(int,input().split())
    c[pi-1] += xi
  z = deque([[0,-1]])
  while z:
    j,b = z.popleft()
    for yj in y[j]:
      if yj != b:
        z.append([yj,j])
        c[yj] += c[j]
  for i in range(n):
    print(c[i],end=" ")
submit()
a

### FIXED CODE ###

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

x = list(map(int, input().split()))
y = list(map(int, input().split()))

max_x = (max(x) + 1) 

ok = 0
dame = 0

for i in y:
    if max_x <= i:
        ok = ok + 1
    else:
        dame = dame + 1

if dame != 0:
    print("War")
elif (X < max_x <= Y) and dame == 0:
    print("No War")
else:
    print("War")
a,b=int(input().split())
if b < 0:
    if (b-a+1) % 2 == 0:
        ans = 'Positive'
    elif (b-a+1) % 2 == 1:
        ans = 'Negative'
elif a > 0:
 ans='Positive'
else
 ans='Zeros'
  
print(ans)

### FIXED CODE ###

a,b=map(int,input().split())
if b < 0:
    if (b-a+1) % 2 == 0:
        ans = 'Positive'
    elif (b-a+1) % 2 == 1:
        ans = 'Negative'
elif a > 0:
 ans='Positive'
else:
 ans='Zero'
  
print(ans)
a,op,b=input()
a=int(a)
b=int(b)

if op=="+":
  print(a+b)
else:
  print(a-b)
  

### FIXED CODE ###

a,op,b=input().split()
a=int(a)
b=int(b)

if op=="+":
  print(a+b)
else:
  print(a-b)
n, y = map(int, input().split())
for i in range(n+1):
    for j in range(n-i+1)
        if i*10000 + j*5000 + (n-i-j)*1000 == y:
            print(i, j, (n-i-j))
            exit()

print(-1, -1, -1)

### FIXED CODE ###

n, y = map(int, input().split())
for i in range(n+1):
    for j in range(n-i+1):
        if i*10000 + j*5000 + (n-i-j)*1000 == y:
            print(i, j, (n-i-j))
            exit()

print(-1, -1, -1)
#125
import fractions
n = int(input())
a = [int(x) for x in input().split(' ')]
all_m = []
for i in range(1,n-1):
    a_1 = a[:i]
    a_2 = a[i+1:]
    m_1 = a_1[0]
    m_2 = a_2[0]
    for j in range(len(a_1)-1):
        m_1 = fractions.gcd(m_1,a_1[j+1])
    for j in range(len(a_2)-1):
        m_2 = fractions.gcd(m_2,a_2[j+1])
    all_m.append(fractions.gcd(m_1,m_2))
m = a[1]
for j in range(1,n):
    m = fractions.gcd(m,a[j+1])
all_m.append(m)
m = a[0]
for j in range(n-1):
    m = fractions.gcd(m,a[j+1])
all_m.appendm(m)
print(max(all_m))

### FIXED CODE ###

#125
from fractions import gcd
n = int(input())
a = [int(x) for x in input().split(' ')]

m_r = [0]
for i in range(n-1):
    m_r.append(gcd(m_r[-1], a[i]))

m_l = [0]
for i in range(1, n):
    m_l.append(gcd(m_l[-1], a[-i]))

m = []
for i in range(n):
    m.append(gcd(m_r[i], m_l[-i-1]))
print(max(m))
s=input()
p=list(set(list(s)))
a=[]
for i in p:
    a.append(s.count(i))
for x in a:
    if x%2!==0:
        print("No")
        exit()
print("Yes")



### FIXED CODE ###

s=input()
p=list(set(list(s)))
a=[]
for i in p:
    a.append(s.count(i))
for x in a:
    if x%2!=0:
        print("No")
        exit()
print("Yes")
def D(x):
    return str(x).__len__()

def price(x):
    return D(x)*b + a*x

d = 1

if price(1)>x:
    print(0)
else:
    while True:
        if price(d*10) <= x:
            d*=10
            if(d==1000000000):
                print(d)
                break
            continue
        else:
            print(max(d + (x-price(d))//a,d*10-1))
            break

### FIXED CODE ###

s = input()

l = ["SUN","MON","TUE","WED","THU","FRI","SAT"]

print(7-l.index(s))
a = int(raw_input())
if a < 1200:
  	print('ABC')
else:
  	print('ARC)
          

### FIXED CODE ###

a = int(input())
if a < 1200:
	print("ABC")
else: print("ARC")
n=int(input())
f=False
for i in range(1,5*10**4+1):
  if n==i*1.08//1
  	f=True
    
if f:
  print(i)
else:
  print(":(")

### FIXED CODE ###

n=int(input())
f=False
for i in range(1,5*10**4+1):
  if n==i*1.08//1:
    f=True
    break
if f:
  print(i)
else:
  print(":(")
N = int(input())
H = list(map(int, input().split()))
count = 0

for i in range(N):
    if H[0] <= H[i]:
        count += 1
        if H[i] <= H[i-1]:
            count -= 1
print(count if H[0] >= H[i] else count + 1)

### FIXED CODE ###

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

for i in range(2):
    if A >= B :
        ans += A
        A -= 1
    else:
        ans += B
        B -= 1
        
print(ans)
a = {x:0 for x in range(ord('a'), ord('z') + 1)}

while True:
    text = input()
    for x in text:
        a[ord(x.lower())] += 1

    for x in range(ord('a'), ord('z') + 1):
        print(chr(x), ':', a[x])

### FIXED CODE ###

a = {x:0 for x in range(ord('a'), ord('z') + 1)}

while True:
    try:
        text = input()
        for x in text:
            if ord('a') <= ord(x) <= ord('z') or ord('A') <= ord(x) <= ord('Z'):
                a[ord(x.lower())] += 1
    except EOFError:
        break

for x in range(ord('a'), ord('z') + 1):
    print(chr(x), ':', a[x])
from math import gcd
a, b = map(int, input().split())
g = gcd(a, b)
ans = 1
for i in range(2, int(g ** 0.5) + 1):
  if g % i != 0:
    continue
  while g % i == 0:
    g //= i
  ans += 1
print(ans)


### FIXED CODE ###

from fractions import gcd
a, b = map(int, input().split())
g = gcd(a, b)
ans = 1
for i in range(2, int(g ** 0.5) + 1):
  if g % i != 0:
    continue
  while g % i == 0:
    g //= i
  ans += 1
if g > 1:
  ans += 1
print(ans)
from math import gcd

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

a = (B-A+1)
b = -(B//C + B//D - B//(C*D//gcd(C,D)))
c = ((A-1)//C + (A-1)//D - (A-1)//(C*D//gcd(C,D)))

print(a+b+c)

### FIXED CODE ###

from fractions import gcd

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

a = (B-A+1)
b = -(B//C + B//D - B//(C*D//gcd(C,D)))
c = ((A-1)//C + (A-1)//D - (A-1)//(C*D//gcd(C,D)))

print(a+b+c)
ans = (a+b)*h/2
print(ans)

### FIXED CODE ###

a=int(input())
b=int(input())
h=int(input())
ans =  (a+b)*h//2
print(ans)