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

from collections import namedtuple
from heapq import heappop, heappush

inf = 10 ** 14 + 10

Edge = namedtuple('Edge', ('cost', 'to'))


def dijkstra(s):
    used = [False] * n
    used[s] = True

    dist = [inf] * n
    dist[s] = 0

    h = []
    for e_ in e[s]:
        heappush(h, e_)

    while h:
        c, v = heappop(h)
        if used[v]:
            continue
        used[v] = True
        dist[v] = c
        for e_ in map(lambda x: (x.cost + dist[v], x.to), e[v]):
            heappush(h, e_)
    return dist


n = int(input())
e = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    e[a].append(Edge(cost=c, to=b))
    e[b].append(Edge(cost=c, to=a))

q, v = map(int, input().split())
v -= 1

g = dijkstra(v)

for _ in range(q):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    print(g[x] + g[y])

# warshall_floyd
# n大で無理

# inf = 10 ** 14 + 10
#
# n = int(input())
# g = [[inf] * n for _ in range(n)]
# for i in range(n):
#     g[i][i] = 0
# for _ in range(n - 1):
#     a, b, c = map(int, input().split())
#     a -= 1
#     b -= 1
#     g[a][b] = c
#     g[b][a] = c
#
# for k in range(n):
#     for i in range(n):
#         for j in range(n):
#             g[i][j] = min(g[i][j], g[i][k] + g[k][j])
#
# q, v = map(int, input().split())
# v -= 1
# for _ in range(q):
#     x, y = map(int, input().split())
#     x -= 1
#     y -= 1
#     print(g[x][v] + g[v][y])
#


### FIXED CODE ###

from collections import namedtuple
from heapq import heappop, heappush
import sys

input = sys.stdin.readline


def solve():
    inf = 10 ** 14 + 10

    Edge = namedtuple('Edge', ('cost', 'to'))

    def dijkstra(s):
        used = [False] * n
        used[s] = True

        dist = [inf] * n
        dist[s] = 0

        h = []
        for e_ in e[s]:
            heappush(h, e_)

        while h:
            c, v = heappop(h)
            if used[v]:
                continue
            used[v] = True
            dist[v] = c
            for e_ in map(lambda x: (x.cost + dist[v], x.to), e[v]):
                heappush(h, e_)
        return dist

    n = int(input())
    e = [[] for _ in range(n)]
    for _ in range(n - 1):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        e[a].append(Edge(cost=c, to=b))
        e[b].append(Edge(cost=c, to=a))

    q, v = map(int, input().split())
    v -= 1

    g = dijkstra(v)

    for _ in range(q):
        x, y = map(int, input().split())
        x -= 1
        y -= 1
        print(g[x] + g[y])


if __name__ == '__main__':
    solve()

# warshall_floyd
# n大で無理

# inf = 10 ** 14 + 10
#
# n = int(input())
# g = [[inf] * n for _ in range(n)]
# for i in range(n):
#     g[i][i] = 0
# for _ in range(n - 1):
#     a, b, c = map(int, input().split())
#     a -= 1
#     b -= 1
#     g[a][b] = c
#     g[b][a] = c
#
# for k in range(n):
#     for i in range(n):
#         for j in range(n):
#             g[i][j] = min(g[i][j], g[i][k] + g[k][j])
#
# q, v = map(int, input().split())
# v -= 1
# for _ in range(q):
#     x, y = map(int, input().split())
#     x -= 1
#     y -= 1
#     print(g[x][v] + g[v][y])
#
### BUGGY CODE ###

from collections import defaultdict

class UnionFind():
    def __init__(self, n=0):
        self.d = [-1]*n
    
    def find(self, x):
        if self.d[x] < 0: return x
        self.d[x] = self.find(self.d[x])
        return self.d[x]

    def unite(self, x, y):
        x,y=self.find(x),self.find(y)
        if x==y:return False
        if self.d[x] > self.d[y]: x,y=y,x
        self.d[x] += self.d[y]
        self.d[y] = x
        return True

    def same(self, x,y): return self.find(x)==self.find(y)
    def size(self,x): return -self.d[self.find(x)]
    
def main():
  N,M,K=map(int,input().split())
  uf=UnionFind(N+1)
  n_friends=defaultdict(int)
  for i in range(M):
    a,b=map(int,input().split())
    uf.unite(a,b)
    n_friends[a] += 1
    n_friends[b] += 1

  B = [set() for _ in range(N+1)]
  for i in range(K):
    c,d=map(int,input().split())
    B[c].add(d)
    B[d].add(c)

  groups=defaultdict(set)
  for i in range(1,N+1):
    g = uf.find(i)
    if g>0:
      groups[g].add(i)

  print(*[len(groups[uf.find(i)].difference(B[i]))-n_friends[i]-1 for i in range(1,N+1)])

main()

### FIXED CODE ###

from collections import defaultdict

class UnionFind():
    def __init__(self, n=0):
        self.d = [-1]*n
    
    def find(self, x):
        if self.d[x] < 0: return x
        self.d[x] = self.find(self.d[x])
        return self.d[x]

    def unite(self, x, y):
        x,y=self.find(x),self.find(y)
        if x==y:return False
        if self.d[x] > self.d[y]: x,y=y,x
        self.d[x] += self.d[y]
        self.d[y] = x
        return True

    def same(self, x,y): return self.find(x)==self.find(y)
    def size(self,x): return -self.d[self.find(x)]
    
N,M,K=map(int,input().split())
uf=UnionFind(N+1)
n_friends=defaultdict(int)
for i in range(M):
  a,b=map(int,input().split())
  uf.unite(a,b)
  n_friends[a] += 1
  n_friends[b] += 1
  
ans = [uf.size(i)-n_friends[i]-1 for i in range(N+1)]

for i in range(K):
  c,d=map(int,input().split())
  if uf.same(c,d):
    ans[c] -= 1
    ans[d] -= 1
  
print(*ans[1:])
### BUGGY CODE ###

N,M=map(int,input().split())
A = [int(x) for x in input().split()]
length = len(A)
for i in range(M):
    b,c = map(int,input().split())
    A.extend(b*[c])
A.sort(reverse = True)
print(sum(A[:length]))

### FIXED CODE ###

read = input 
rn = lambda :map(int, read().split())
n,m = rn()
A = list(rn())
l = len(A)
d = {}
for x in A:
    if x not in d:
        d[x]=0
    d[x] += 1
for i in range(m):
    b, c = rn()
    if c not in d:
        d[c]=0
    d[c] += b
A = list(d.items())
A.sort(reverse=True)
ans = 0
cnt = l
# print(A)
for v, c in A:
    tmp = min(cnt, c)
    ans += tmp * v
    cnt -= tmp
print(ans)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10**6)

root = list()


def dfs(A, num, N):
    if A[num] in root:
        return root.index(A[num])
    else:
        root.append(A[num])
        return dfs(A, A[num]-1, N)


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

    start = dfs(A, 0, N)

    if K <= len(root):
        print(root[K-1])
    else:
        index = (K - start) % (len(root)-start)
        loop = root[start:]
        print(loop[index-1])


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

root = list()


def dfs(A, num, N, memo):
    if memo[A[num]-1] == 1:
        return root.index(A[num])
    else:
        root.append(A[num])
        memo[A[num]-1] = 1
        return dfs(A, A[num]-1, N, memo)


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

    memo = [0] * N
    start = dfs(A, 0, N, memo)

    if K <= len(root):
        print(root[K-1])
    else:
        index = (K - start) % (len(root)-start)
        loop = root[start:]
        print(loop[index-1])


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

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

n,q=map(int,input().split())
tree = [set() for _ in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    tree[a-1].add(b)
ans=[0]*n
def add_l(x):
    if not tree[x-1]:
        return
    for i in list(tree[x-1]):
        add_l(i)
        tree[x-1] |= tree[i-1]

add_l(1)
#print(tree)

for i in range(q):
    
    p,x=map(int,input().split())
    ans[p-1]+=x
    if tree[p-1]:

        for j in list(tree[p-1]):
            ans[j-1]+=x
print(*ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

# 遅延評価で加えてあげるだけ

N,Q = map(int,input().split())
AB = [[int(x) for x in input().split()] for _ in range(N-1)]
PX = [[int(x) for x in input().split()] for _ in range(Q)]

graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

value = [0] * (N+1)
for p,x in PX:
    value[p] += x

def dfs(v,parent,add):
    value[v] += add
    for x in graph[v]:
        if x == parent:
            continue
        dfs(x,v,value[v])

dfs(1,0,0)

answer = ' '.join(map(str,value[1:]))
print(answer)
### BUGGY CODE ###

from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

H, W, ch, cw, gh, gw, *S = open(0).read().split()
H, W, ch, cw, gh, gw = [int(_) - 1 for _ in [H, W, ch, cw, gh, gw]]
S = ''.join(S)
H += 1
W += 1

X = []
Y = []
D = []
for i in range(H * W):
    if S[i] == '#':
        continue
    h, w = divmod(i, W)
    for dh in range(-2, 3):
        for dw in range(-2, 3):
            j = i + dw + W * dh
            if 0 <= h + dh < H and 0 <= w + dw < W and i < j and S[j] == '.':
                X += [i]
                Y += [j]
                D += [0 if (dh, dw) in ((1, 0), (0, 1)) else 1]
dist = dijkstra(
    csr_matrix((D, (X, Y)), (H * W, H * W), dtype=int),
    indices=ch * W + cw,
    directed=0)
ans = dist[gh * W + gw]
if ans > 10**10:
    ans = -1
else:
    ans = int(ans)
print(ans)


### FIXED CODE ###

import collections, itertools
H, W, ch, cw, dh, dw, *S = open(0).read().split()
H, W, ch, cw, dh, dw = [int(_) + 1 for _ in [H, W, ch, cw, dh, dw]]
H += 3
W += 3
S = ['#' * W] + ['#' * W] + ['##' + s + '##'
                             for s in S] + ['#' * W] + ['#' * W]
Dist = [[None] * W for _ in range(H)]
Q = collections.deque([(0, ch, cw)])
while Q:
    d, ox, oy = Q.popleft()
    if Dist[ox][oy] is not None:
        continue
    stack = [[ox, oy]]
    warp = set()
    while stack:
        x, y = stack.pop()
        if (x, y) == (dh, dw):
            print(d)
            exit()
        Dist[x][y] = d
        for dx, dy in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
            nx, ny = x + dx, y + dy
            if Dist[nx][ny] is None:
                if S[nx][ny] == '.':
                    stack += [[nx, ny]]
                else:
                    warp.add((x, y))
    for x, y in warp:
        for dx, dy in itertools.product(range(-2, 3), repeat=2):
            nx, ny = x + dx, y + dy
            if Dist[nx][ny] is None and S[nx][ny] == '.':
                Q += [(d + 1, nx, ny)]
print(-1)
### BUGGY CODE ###

def main():
  n,k = map(int, input().split())
  a = list(map(int, input().split()))
  a.sort()
  ans = 0
  if k == 1:
    print(0)
  else:
    for i in range(k-1,n):
      if n-i+1<0:
        break
      if i == k-1:
        c = 1
        ans += (a[i]-a[n-i-1])*c
      else:
        c = c*i//(i-k+1)
        ans += (a[i]-a[n-i-1])*c
    print(ans%1000000007)
if __name__ == "__main__":
  main()


### FIXED CODE ###

n,k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
ans = 0

from operator import mul
from functools import reduce
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10 ** 9 + 7
N = 10 ** 5
fact = [1, 1]  
factinv = [1, 1]
inv = [0, 1]  

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

if k == 1:
  print(0)
else:
  for i in range(1,n):
    if n-i < k-1:
      break
    ans += a[n-i]*cmb(n-i,k-1,p)
    ans -= a[i-1]*cmb(n-i,k-1,p)
  print(ans%1000000007)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from bisect import bisect_left
n,m = map(int,input().split())
a = list(map(int,input().split()))

b = [0]*(n+1)
a.sort()
for i in range(n):
  b[i+1] = b[i]+a[i]

def is_ok(arg):
    c = 0
    f = False
    for i in a:
      if c >= m:
        break
      c += (n-bisect_left(a,arg-i))
    if c >= m:
      f = True
    return f

def bisect_ok(ng, ok):
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ok

x = bisect_ok(2*a[-1]*m+1,1)
ans = 0
cnt = 0
for i in a:
  ind = n-bisect_left(a,x-i)
  cnt += ind
  ans += i*ind+(b[-1]-b[n-ind])
if cnt > m:
  ans -= x*(cnt-m)
print(ans)

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from bisect import bisect_left

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

b = [0]*(n+1)
a.sort()
for i in range(n):
  b[i+1] = b[i]+a[i]

def is_ok(arg):
    c = 0
    f = False
    for i in a:
      if c >= m:
        break
      c += (n-bisect_left(a,arg-i))
    if c >= m:
      f = True
    return f

def bisect_ok(ng, ok):
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ok

x = bisect_ok(2*a[-1]+1,1)
ans = 0
cnt = 0
for i in a:
  ind = n-bisect_left(a,x-i)
  cnt += ind
  ans += i*ind+(b[-1]-b[n-ind])
if cnt > m:
  ans -= x*(cnt-m)
print(ans)
### BUGGY CODE ###

# 接続最大クラスタのサイズが答え？
from networkx import Graph, connected_components

N, M = [int(x) for x in input().split(' ')]

list_ab = [None] * M
for i in range(M):
    a, b = [int(x) for x in input().split(' ')]
    list_ab[i] = (a, b)


G = Graph()
G.add_nodes_from(range(N))
G.add_edges_from(list_ab)

# # get max connected component
# max_size = 0
# for component in connected_components(G):
#     max_size = max(max_size, len(component))
#     if max_size >= (N+1) // 2:
#         break
# print(max_size)

largest_cc = len(max(connected_components(G), key=len))
print(largest_cc)

### FIXED CODE ###

# 接続最大クラスタのサイズが答え？

N, M = [int(x) for x in input().split(' ')]

# from collections import defaultdict
# d = defaultdict(set)

# for i in range(M):
#     a, b = [int(x) for x in input().split(' ')]
#     d[a].add(b)
#     d[b].add(a)

class UF:
    def __init__(self):
        self.r = [-1] * N

    def root(self, i):
        r = self.r
        if r[i] < 0:
            return i
        else:
            r[i] = self.root(r[i])
            return r[i]

    def union(self, i, j):
        i -= 1
        j -= 1
        ri = self.root(i)
        rj = self.root(j)
        if ri == rj:
            return
        else:
            if not self.r[ri] < self.r[rj]:
                ri, rj = rj, ri
            self.r[ri] += self.r[rj]
            self.r[rj] = ri
            return

    def max_size(self):
        return -min(self.r)

uf = UF()
for i in range(M):
    uf.union(*[int(x) for x in input().split(' ')])
print(uf.max_size())
### BUGGY CODE ###

N = input()
A = [int(k) for k in input().split()]

result = True

for char in A:
    if(A.count(char) != 1):
        result = False
        break

if (result == True):
    print("YES")
else:
    print("NO")


### FIXED CODE ###

N = int(input())
A = [int(k) for k in input().split()]

result = True

# for char in A:
#     if(A.count(char) != 1):
#         result = False
#         break
# for i in range(N):
#     for j in range(i+1, N):
#         # print("A[i]= "+str(A[i])+", A[j]= "+str(A[j]))
#         if A[i] == A[j]:
#             result = False
A.sort()

for i in range(N-1):
    if (A[i] == A[i+1]):
        result = False
        break

if (result == True):
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

import itertools
N = int(input())
A = input().split()
Ai = [int(s) for s in A]
count = 0
for x, y in itertools.combinations(range(N), 2):
        if abs(x-y) == Ai[x]+Ai[y]:
            count += 1
print(count)

### FIXED CODE ###

from collections import defaultdict
dic = defaultdict(int)

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

for i, a in enumerate(A):
    dic[i + a] += 1

counter = 0
for i, a in enumerate(A):
    counter += dic[i-a]

print(counter)
### BUGGY CODE ###


n = int(input())

ans = 0
for i in range(n):
    ans += i
print(ans)

### FIXED CODE ###


n = int(input())

print(n*(n-1)//2)
### BUGGY CODE ###

n, m, k = map(int , input().split())
dif = set([i for i in range(1, n+1)])
m_list = [[] for _ in range(n+1)]
uni = [[i,1] for i in range(n+1)]
ab = [list(map(int, input().split())) for _ in range(m)]
cd = [list(map(int, input().split())) for _ in range(k)]
for i in range(m):
    a, b = ab[i]
    m_list[a].append(b)
    m_list[b].append(a)
    if uni[a][0] != uni[b][0]:
        a, b = sorted([uni[a][0], uni[b][0]])
        uni[a][1] += uni[b][1]
        for j in range(1, n+1):
            if uni[j][0] == b:
                uni[j][0] = a
        uni[b][0] = uni[a][0]

k_list = [[] for _ in range(n+1)]
for i in range(k):
    a, b = cd[i]
    if uni[a][0] == uni[b][0]:
        m_list[b].append(a)
        m_list[a].append(b)

result = []
for i in range(1, n+1):
    result.append(uni[uni[i][0]][1]-len(m_list[i])-1)

print(*result)

### FIXED CODE ###

class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return 
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]


n, m, k = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
cd = [list(map(int, input().split())) for _ in range(k)]
con = [1 for _ in range(n+1)]
uni = UnionFind(n+1)


for i in range(m):
    a, b = ab[i]
    con[a] += 1
    con[b] += 1
    uni.Unite(a, b)

for i in range(k):
    c, d = cd[i]
    if uni.isSameGroup(c,d):
        con[c] += 1
        con[d] += 1

result = []
for i in range(1, n+1):
    result.append(uni.Count(i)-con[i])
print(*result)
### BUGGY CODE ###

# coding: utf-8
# Your code here!
N, K = [int(_) for _ in input().split()]
S = str(input())

Nums = []
now, cnt = 1, 0
for i in range(N):
    if S[i] == str(now): cnt += 1
    else:
        Nums.append(cnt)
        now = 1 - now
        cnt = 1
if cnt != 0: Nums.append(cnt)
# print(Nums)

if len(Nums) % 2 == 0: Nums.append(0)

add = 2 * K + 1
ans = 0
for i in range(0, len(Nums), 2):
    tmp = 0
    left = i
    right = min(i+add, len(Nums))
    j = left
    while j < right:
        tmp += Nums[j]
        j += 1
    ans = max(tmp, ans)
print(ans)
        



### FIXED CODE ###

# coding: utf-8
# Your code here!
N, K = [int(_) for _ in input().split()]
S = str(input())

Nums = []
now, cnt = 1, 0
for i in range(N):
    if S[i] == str(now): cnt += 1
    else:
        Nums.append(cnt)
        now = 1 - now
        cnt = 1
if cnt != 0: Nums.append(cnt)
if len(Nums) % 2 == 0: Nums.append(0)


# add = 2 * K + 1
# ans = 0
# for i in range(0, len(Nums), 2):
#     tmp = 0
#     left = i
#     right = min(i+add, len(Nums))
#     j = left
#     while j < right:
#         tmp += Nums[j]
#         j += 1
#     ans = max(tmp, ans)
# print(ans)

#------------------------
add = 2 * K + 1
ans = 0
left = 0
right = 0
tmp = 0
for i in range(0, len(Nums), 2):
    nextLeft = i 
    nextRight = min(i + add, len(Nums))
    while nextLeft > left:
        tmp -= Nums[left]
        left += 1
    while nextRight > right:
        tmp += Nums[right]
        right += 1
    #print('left, right:   ', left, right)
    ans = max(tmp, ans)
        
print(ans)
### BUGGY CODE ###

N = int(input())
D = list(map(int,input().split()))
ans = 1
if D[0] != 0:
  print(0)
  exit()

prev = 0
for i in range (N):
  if i == 0:
    prev = 1
    if D[0] != 0 or D.count(i) > 1:
      print(0)
      exit()
  else:
    count = D.count(i)
    ans = ( ans * ((prev**count) %998244353 ) ) %998244353
    prev = count
print(ans)

### FIXED CODE ###

n = int(input())
d = list(map(int, input().split()))
b = 1
ans = 1
dd=[0]*10**5
for i in d:
    dd[i]+=1
max = max(d)
if d[0] == 0 and d.count(0) == 1:
    for i in range(1, max+1):
        if dd[i] == 0:
            print(0)
            exit()
        if dd[i] == 1:
            ans *= b
        else:
            if b != 1:
                ans *= pow(b, dd[i], 998244353)
        b = dd[i]
    print(ans % 998244353)
else:
    print(0)
### BUGGY CODE ###

import fractions
import functools

N = int(input())
A = [int(i) for i in input().split()] 

max_gcd = functools.reduce(fractions.gcd, A)

for i in range(N):
	tmp = A.copy()
	tmp.pop(i)
	gcd = functools.reduce(fractions.gcd, tmp)
	if max_gcd < gcd:
		max_gcd = gcd

print(max_gcd)


### FIXED CODE ###

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

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

N = int(input())
A = [int(a) for a in input().split()]

# GCDの結合則を利用する
# 左端、右端からの累積GCDを求めておくと、Aiを取り除いた場合のGCDがすぐに計算できる。
# つまり、
# L(i): n=0,...,iまでのGCD 
# R(i): n=i,...,N-1までのGCD
# このとき、Aiを除いた全体のGCDは、GCD(L(i-1), R(i+1))で計算できる。

L = [0] * N
R = [0] * N

L[0] = A[0]
R[-1] = A[-1]
for i in range(1, N):
    L[i] = gcd(L[i-1], A[i])
    idx = N-1-i
    R[idx] = gcd(R[idx+1], A[idx])

mx = 0
for i in range(N):
    if i == N-1:
        v = L[N-2]
    elif i == 0:
        v = R[1]
    else:
        v = gcd(R[i+1], L[i-1])
    mx = max(v, mx)
print(mx)
### BUGGY CODE ###

n=int(input())
l_list=[]

for _ in range(n):
  l=sorted(input())
  l_list.append(l)

count=0

for i in range(n):
  for j in range(i+1,n,1):
    if l_list[i] == l_list[j]:
      count+=1
print(count)

### FIXED CODE ###

from math import factorial
def com(n,r):
  if n<r:
    return 0
  return int(factorial(n) // factorial(r) // factorial(n-r))

n=int(input())
l_list=[]

for _ in range(n):
  l=sorted(input())
  l_list.append(l)

l_list = sorted(l_list)

count=0

ans = 0
i = 0
j = 1
while i < n:
  tmp = 0
  while i + j < n and l_list[i] == l_list[i + j]:
    tmp += 1
    j += 1
  if tmp != 0:
    ans += com(tmp+1, 2)
  i += j
  j = 1

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

N, K = map(int, input().split())
P = list(map(int, input().split()))
 
m, m_index = 0, 0
for i in range(N-K+1):
    total = sum(P[i:i+K])
    if total > m:
        m = total
        m_index = i

print(sum(map(lambda x: (x+1)/2, P[m_index:m_index+K])))

### FIXED CODE ###

from itertools import accumulate


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


expected = [(a+1)/2 for a in A]
accum_expected = list(accumulate(expected))
accum_expected.insert(0, 0)

ans = 0
for i in range(K, N+1):
    ans = max(ans, accum_expected[i]-accum_expected[i-K])
print(ans)
### BUGGY CODE ###

n,m = map(int,input().split())
ab = []
cost = [[] for _ in range(n+1)]
for _ in range(m):
    a, b = (int(x) for x in input().split())
    ab.append([a, b])
    cost[a].append(b)
 
check = [0]*(n+1)
 
#print(cost)
for i,j in ab:
    if check[i] == 0:
        cost[i].sort()
        check[i] = 1
    ID = cost[i].index(j)+1
    i = str(i)
    i = (6-len(i))*'0'+i
    ID = str(ID)
    ID = (6-len(ID))*'0'+ID
    print(i+ID)

### FIXED CODE ###

n,m = map(int,input().split())
py = []
p_y = [[] for i in range(n)]
for _ in range(m):
    p,y = map(int,input().split())
    py.append((p,y))
    p_y[p-1].append(y)
ans = {}
for i, tmp in enumerate(p_y):
    cnt = 1
    p_y[i] = tmp.sort()
    for j, jj in enumerate(tmp):
 
        ans[(i+1, jj)] = str(i+1).zfill(6) + str(j+1).zfill(6)
 
 
for i, tmp in enumerate(py):
    print(ans[tmp])
### BUGGY CODE ###

N,M = map(int, input().split())
ls = list(map(int, input().split()))
ls.sort()
def half(l):
  a=l.index(max(l))
  l[a]=l[a]//2
  return(l)
for i in range(M):
  half(ls)
print(sum(ls))

### FIXED CODE ###

from collections import deque
N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
q1=deque(A)
q2=deque([])
for i in range(M):
  if len(q1)!=0 and (len(q2)==0 or q1[0]>=q2[0]):
    x=q1.popleft()
  else:
    x=q2.popleft()
  q2.append(x//2)
print(int(sum(q1)+sum(q2)))