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

N, Q = list(map(int, input().split()))
d = {}
for i in range(N - 1):
    a, b = list(map(int, input().split()))
    if a in d:
        d[a].add(b)
    else:
        d[a] = {b}
    if b in d:
        d[b].add(a)
    else:
        d[b] = {a}
counter = [0] * (N + 1)
for _ in range(Q):
    p, x = list(map(int, input().split()))
    counter[p] += x

parents = {1}
while True:
    children = set()
    for parent in parents:
        v = counter[parent]
        for child in d[parent]:
            d[child].remove(parent)
            children.add(child)
            counter[child] += v
    if len(children) == 0:
        break
    parents = children
print(*counter[1:])

### FIXED CODE ###

N, Q = list(map(int, input().split()))
d = {i: set() for i in range(1, N + 1)}
for i in range(N - 1):
    a, b = list(map(int, input().split()))
    d[a].add(b)
    d[b].add(a)
counter = [0] * (N + 1)
for _ in range(Q):
    p, x = list(map(int, input().split()))
    counter[p] += x

parents = {1}
while parents:
    children = set()
    for parent in parents:
        v = counter[parent]
        for child in d[parent]:
            d[child].remove(parent)
            children.add(child)
            counter[child] += v
    parents = children
print(*counter[1:])
### BUGGY CODE ###

S = input()
Q = int(input())


flg = True
for i in range(Q):
    que = input()
    if que == "1":
        if flg:
            flg = False
        else:
            flg = True
    else:
        j, F, C = que.split()
        if int(F) == 1:
            if flg:
                S = C + S
            else:
                S = S + C
        else:
            if flg:
                S = S + C
            else:
                S = C + S

if flg:
    print(S)
else:
    print(S[::-1])

### FIXED CODE ###

from collections import deque

S = input()
Q = int(input())

Sq = deque(S)


flg = True
for i in range(Q):
    que = input()
    if que == "1":
        if flg:
            flg = False
        else:
            flg = True
    else:
        j, F, C = que.split()
        if int(F) == 1:
            if flg:
                Sq.appendleft(C)
            else:
                Sq.append(C)
        else:
            if flg:
                Sq.append(C)
            else:
                Sq.appendleft(C)

if flg:
    for i in Sq:
        print(i, end="")
else:
    Sq.reverse()
    for i in Sq:
        print(i, end="")
### BUGGY CODE ###

from collections import defaultdict

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

dp = defaultdict(int)

def rec(l, r, xl, xr) :
    if l + 1 == r :
        return 0
    
    if dp[(l, r, xl, xr)] > 0 :
        return dp[(l, r, xl, xr)]
    
    ret = float('inf')
    for m in range(l + 1, r) :
        ret = min(ret, rec(l, m, xl, xl+xr) + rec(m, r, xl+xr, xr) + A[m] * (xl+xr))
   
    dp[(l, r, xl, xr)] = ret
    return ret
    
print(A[0] + rec(0, N-1, 1, 1) + A[N-1])


### FIXED CODE ###

# ikatakosさんの提出を見てlru_cacheなるものを知った。
# まだまだ知らないことがたくさんありますね。

from functools import lru_cache

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

@lru_cache(maxsize=None)
def rec(l, r, xl, xr) :
    if l + 1 == r :
        return 0
    
    return min(rec(l, m, xl, xl+xr)+rec(m, r, xl+xr, xr)+A[m]*(xl+xr) for m in range(l+1, r))
    
print(A[0] + rec(0, N-1, 1, 1) + A[N-1])
### BUGGY CODE ###

N,Q = map(int,input().split())
AB = [[] for _ in range(N-1)]
for n in range(N-1):
    AB[n] = list(map(int,input().split()))
PX = [[] for _ in range(Q)]
for q in range(Q):
    PX[q] = list(map(int,input().split()))
graph = [[] for _ in range(N+1)]
for ab in AB:
    graph[ab[0]].append(ab[1])
    graph[ab[1]].append(ab[0])
val = [0] * (N+1)
for px in PX:
    val[px[0]] += px[1]
parent = [0] * (N+1)
from collections import deque
Q  = deque([1])
while Q:
    q = Q.popleft()
    for c in graph[q]:
        if c == parent[q]:
            continue
        parent[c] = q
        Q.append(c)
        val[c] += val[q]
print(*val[1:])

### FIXED CODE ###

N,Q = map(int,input().split())
AB = [[] for _ in range(N-1)]
for n in range(N-1):
    AB[n] = list(map(int,input().split()))
PX = [[] for _ in range(Q)]
for q in range(Q):
    PX[q] = list(map(int,input().split()))
graph = [[] for _ in range(N+1)]
for ab in AB:
    graph[ab[0]].append(ab[1])
    graph[ab[1]].append(ab[0])
val = [0] * (N+1)
for px in PX:
    val[px[0]] += px[1]
parent = [0] * (N+1)
from collections import deque
Q  = deque([1])
while Q:
    q = Q.popleft()
    for c in graph[q]:
        if c == parent[q]:
            continue
        parent[c] = q
        Q.append(c)
        val[c] += val[q]
print(*val[1:])
### BUGGY CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
sys.setrecursionlimit(1000000)

h,w=map(int,input().split())
maze = [[]for _ in range(h)]
for i in range(h):
    maze[i].extend(list(input()))

R=[[0 for i in range(w)]for i in range(h)]
L=[[0 for i in range(w)]for i in range(h)]
U=[[0 for i in range(w)]for i in range(h)]
B=[[0 for i in range(w)]for i in range(h)]

for i in range(h):
    for j in range(w):
        if maze[i][j]=="#":continue
        if j==0: L[i][j]=1
        else: L[i][j]=L[i][j-1]+1
        if i==0: U[i][j]=1
        else: U[i][j]=U[i-1][j]+1

for i in range(h):
    for j in range(w):
        if maze[h-1-i][w-1-j]=="#":continue
        if i==0:B[h-1-i][w-1-j]=1
        else: B[h-1-i][w-1-j] = B[h-i][w-1-j]+1
        if j==0:R[h-1-i][w-1-j]=1
        else: R[h-1-i][w-1-j] = R[h-1-i][w-j]+1


#print(*B,sep="\n")
#print("\n")
#print(*U,sep="\n")


ma=0
for i in range(h):
    for j in range(w):
        if maze[i][j]=="#":continue
        ma=max(ma,R[i][j]+L[i][j]+U[i][j]+B[i][j]-3)

print(ma)


### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
sys.setrecursionlimit(1000000)

h,w=map(int,input().split())
maze = [[]for _ in range(h)]
for i in range(h):
    maze[i].extend(list(input()))

R=[[0 for i in range(w)]for i in range(h)]
L=[[0 for i in range(w)]for i in range(h)]
U=[[0 for i in range(w)]for i in range(h)]
B=[[0 for i in range(w)]for i in range(h)]

for i in range(h):
    for j in range(w):
        if maze[i][j]=="#":continue
        if j==0: L[i][j]=1
        else: L[i][j]=L[i][j-1]+1
        if i==0: U[i][j]=1
        else: U[i][j]=U[i-1][j]+1

for i in range(h):
    for j in range(w):
        if maze[h-1-i][w-1-j]=="#":continue
        if i==0:B[h-1-i][w-1-j]=1
        else: B[h-1-i][w-1-j] = B[h-i][w-1-j]+1
        if j==0:R[h-1-i][w-1-j]=1
        else: R[h-1-i][w-1-j] = R[h-1-i][w-j]+1


#print(*B,sep="\n")
#print("\n")
#print(*U,sep="\n")


ma=0
for i in range(h):
    for j in range(w):
        if maze[i][j]=="#":continue
        ma=max(ma,R[i][j]+L[i][j]+U[i][j]+B[i][j]-3)

print(ma)
### BUGGY CODE ###

N, P = map(int, input().split())
S = input()
if P==2:
    counter = 0
    for i in range(len(S)):
        if S[i] in ['2','4','6','8','0']:
            counter+=i+1
    print(counter)
elif P==5:
    counter = 0
    for i in range(len(S)):
        if S[i] in ['5','0']:
            counter+=i+1
    print(counter)
else:
    list_a=[0]*P
    list_a[0]+=1
    counter=0
    for i in range(N):
        temp=int(S[N-i-1:])%P
        counter+=list_a[temp]
        list_a[temp]+=1
    print(counter)

### FIXED CODE ###

N, P = map(int, input().split())
S = input()

counter=0
def power_func(a,b,p):
    if b==0:
        return 1
    elif b%2==0:
        d=power_func(a,b//2,p)
        return d*d %p
    elif b%2==1:
        return (a*power_func(a,b-1,p ))%p
if P==2:
    counter = 0
    for i in range(len(S)):
        if S[i] in ['2','4','6','8','0']:
            counter+=i+1
elif P==5:
    counter = 0
    for i in range(len(S)):
        if S[i] in ['5','0']:
            counter+=i+1
else:
    list_a=[0]*P
    list_a[0]+=1
    temp=0
    for i in range(N):
        M = power_func(10,N-i,P)
        temp=(int(S[i])*M+temp)%P
        counter+=list_a[temp]
        list_a[temp]+=1
print(counter)
### BUGGY CODE ###

import sys

s = sys.stdin.readline().rstrip()
q = int(sys.stdin.readline().rstrip())
query = [sys.stdin.readline().rstrip().split() for i in range(q)]
top = 1
for i in range(q):
    que = query[i]
    if que[0] == '1':
        top *= -1
    else:
        if que[1] == '1':
            if top > 0:
                s = que[2] + s
            else:
                s = s + que[2]
        else:
            if top > 0:
                s = s + que[2]
            else:
                s = que[2] + s
if top < 0:
    s = s[::-1]
print(s)


### FIXED CODE ###

import sys

s = sys.stdin.readline().rstrip()
q = int(sys.stdin.readline().rstrip())
query = [sys.stdin.readline().rstrip().split() for i in range(q)]
top = 1
s = list(s)
s_front = []
s_back = []
for i in range(q):
    que = query[i]
    if que[0] == '1':
        top *= -1
    else:
        if que[1] == '1':
            if top > 0:
                s_front.append(que[2])
                # s = ''.join([que[2], s])
                # s = que[2] + s
            else:
                s_back.append(que[2])
                # s = ''.join([s, que[2]])
                # s = s + que[2]
        else:
            if top > 0:
                s_back.append(que[2])
                # s = ''.join([s, que[2]])
                # s = s + que[2]
            else:
                s_front.append(que[2])
                # s = ''.join([que[2], s])
                # s = que[2] + s
s_front.reverse()
s_front.extend(s)
s_front.extend(s_back)
s = s_front
s = ''.join(s)
if top < 0:
    s = s[::-1]
print(s)
### BUGGY CODE ###

from math import gcd, sqrt


def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


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

    s_tmp = A[0]
    p_flag = True
    p_dic = [0] * (10**6+1)
    for a in A:
        s_tmp = gcd(s_tmp, a)
        if p_flag:
            tmp = list(set(prime_factorize(a)))
            for t in tmp:
                if p_dic[t] == 0:
                    p_dic[t] = 1
                else:
                    p_flag = False
                    continue

    if p_flag:
        print('pairwise coprime')
    elif s_tmp == 1:
        print('setwise coprime')
    else:
        print('not coprime')


if __name__ == "__main__":
    main()


### FIXED CODE ###

from math import gcd, sqrt


def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


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

    s_tmp = A[0]
    p_flag = True
    p_dic = [0] * (10**6+1)
    for a in A:
        s_tmp = gcd(s_tmp, a)
        if p_flag:
            tmp = list(set(prime_factorize(a)))
            for t in tmp:
                if p_dic[t] == 0:
                    p_dic[t] = 1
                else:
                    p_flag = False
                    continue

    if p_flag:
        print('pairwise coprime')
    elif s_tmp == 1:
        print('setwise coprime')
    else:
        print('not coprime')


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

# ABC154 D - Dice in Line
N,K = map(int, input().split())
P = [int(i) for i in input().split()]

ma = 0
for i in range(0,N-K+1):
  expect = (sum(P[i:i+K])+K)/2
  if ma < expect:
    ma = expect
print(ma)

### FIXED CODE ###

# ウィンドウをスライドさせる際に，期待値の全体を再計算するのをやめた
N,K = map(int, input().split())
P = [int(i) for i in input().split()]
 
expect = (sum(P[0:K])+K)/2
ma = expect
for i in range(K,N):
  expect += (P[i]-P[i-K])/2
  if ma < expect:
    ma = expect
print(ma)
### BUGGY CODE ###

def main():
    N, Q = (int(i) for i in input().split())
    C = [int(i) for i in input().split()]
    Query = [([int(i) for i in input().split()], j) for j in range(Q)]
    Query.sort(key=lambda p: p[0][1])
    lastappend = [0] * (N + 1)

    def sum(tree, i):
        s = 0
        while i > 0:
            s += tree[i]
            i -= i & -i
        return s

    def add(tree, i, x):
        while i <= N:
            tree[i] += x
            i += i & -i
    bit = [0] * (N + 1)
    idx = 0
    ans = []

    for i, a in enumerate(C, start=1):
        if lastappend[a] != 0:
            add(bit, lastappend[a], -1)
        lastappend[a] = i
        add(bit, i, 1)
        while idx < Q and i == Query[idx][0][1]:
            (le, ri), j = Query[idx]
            ans.append((j, sum(bit, ri) - sum(bit, le-1)))
            idx += 1
    ans.sort()
    for _, a in ans:
        print(a)


if __name__ == '__main__':
    main()


### FIXED CODE ###

SHIFT = 1 << 20


def main():
    N, Q = (int(i) for i in input().split())
    C = [int(i) for i in input().split()]
    Query = []
    for j in range(Q):
        le, ri = (int(i) for i in input().split())
        Query.append(ri << 40 | le << 20 | j)
    Query.sort()

    # Query復元
    for i in range(Q):
        j = Query[i] % (SHIFT)
        Query[i] >>= 20
        le = Query[i] % (SHIFT)
        Query[i] >>= 20
        ri = Query[i]
        Query[i] = (le, ri, j)
    Query.append((-1, -1, -1))

    def sum(tree, i):
        s = 0
        while i > 0:
            s += tree[i]
            i -= i & -i
        return s

    def add(tree, i, x):
        while i <= N:
            tree[i] += x
            i += i & -i

    lastappend = [-1] * (N + 1)
    bit = [0] * (N + 1)
    idx = 0  # Queryのindex
    ans = [0]*Q

    for i, a in enumerate(C, start=1):
        if lastappend[a] != -1:
            add(bit, lastappend[a], -1)
        lastappend[a] = i
        add(bit, i, 1)
        while i == Query[idx][1]:
            (le, ri, j) = Query[idx]
            ans[j] = sum(bit, ri) - sum(bit, le-1)
            idx += 1

    print(*ans, sep="\n")


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

import re
N,Q = map(int,input().split())	

S = input()

for _ in range(Q):
    l,r = map(int,input().split())	
    print(len(re.findall('AC', S[l-1:r])))


### FIXED CODE ###

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

S = input()

t = [0] * N
for i in range(1, N):
    if S[i-1:i+1] == 'AC':
        t[i] = t[i-1] + 1
    else:
        t[i] = t[i-1]
#    print(t)

for _ in range(Q):
    l,r = map(int,input().split())	
    print(t[r-1]-t[l-1])
### BUGGY CODE ###

s = input()
t = input()

#dp[i][j] => s[i], t[j]までの最長部分文字列

dp = [[""] *(len(t) + 1) for j in range(len(s) + 1)]
for i in range(1,len(s)+1):
    for j in range(1,len(t)+1):
        if s[i - 1] == t[j - 1]:
            dp[i][j] = "".join(dp[i - 1][j] + s[i - 1])
        else:
            #上か左の長いほうを入れる
            if len(dp[i][j-1]) < len(dp[i-1][j]):
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = dp[i][j - 1]
print(dp[-1][-1])


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**5)
s = input()
t = input()

#dp[i][j] => s[i], t[j]までの最長部分文字列

dp = [[0] * (len(t) + 1) for j in range(len(s) + 1)]
for i in range(1,len(s)+1):
    for j in range(1,len(t)+1):
        if s[i-1] == t[j-1]:
            x = 1
        else:
            x = 0
        dp[i][j] = max(dp[i-1][j-1] + x, dp[i-1][j], dp[i][j-1])


def make_ans(a, b):
    if a ==  0 or b == 0:
        return 
    if s[a-1] == t[b-1]:
        make_ans(a-1,b-1)
        ans.append(s[a-1])
    else:
        if a == 0:
            make_ans(a, b - 1)
        elif b == 0:
            make_ans(a - 1,b)
        else:
            if dp[a - 1][b] > dp[a][b - 1]:
                make_ans(a-1,b)
            else:
                make_ans(a,b-1)

ans = []
make_ans(len(s),len(t))
print("".join(ans))
### BUGGY CODE ###

import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()
A = [0 for _ in range(M)]
B = [0 for _ in range(M)]
first = []
for m in range(M):
    a, b = lr()
    if a == 1:
        first.append(b)
    A[m] = a
    B[m] = b
for i, b in enumerate(B):
    if b == N:
        if A[i] in first:
            print("POSSIBLE")
            exit(0)
print("IMPOSSIBLE")


### FIXED CODE ###

import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()
E = {i+1: set() for i in range(N)}
first = set()
for m in range(M):
    a, b = lr()
    if b == N:
        first.add(a)
    E[a].add(b)
if not first.isdisjoint(E[1]):
    print("POSSIBLE")
    exit(0)
print("IMPOSSIBLE")
### BUGGY CODE ###

N = int(input())
M = [str(input()) for i in range(N)]

# 紙に書かれた数字
K = []

for i in M:
    if i in K:
        K.remove(i)
    else:
        K.append(i)

print(len(K))


### FIXED CODE ###

import collections

N = int(input())
M = [int(input()) for i in range(N)]

value = list(collections.Counter(M).values())

sum = 0
for i in value:
    sum += i%2

print(sum)
### BUGGY CODE ###

import heapq
INF = float('inf')
yen = 10**15
def pcc(src, adj):
	pq = [(0,src)]
	heapq.heapify(pq)
	dist = [INF]*(n+1)
	dist[src] = 0
	while pq:
		d,u = heapq.heappop(pq)
		if d>dist[u]:continue
		for w, v in adj[u]:
			if dist[v] > dist[u] + w:
				dist[v] = dist[u] + w
				heapq.heappush(pq, (dist[v], v))
	return dist

n,m,s,t = (int(i) for i in input().split())
adjs = [[] for _ in range(n+1)]
adjt = [[] for _ in range(n+1)]
for _ in range(m):
	u,v,a,b = (int(i) for i in input().split())
	adjs[u].append([a,v])
	adjs[v].append([a,u])
	adjt[u].append([b,v])
	adjt[v].append([b,u])

dist_s = pcc(s,adjs)
dist_t = pcc(t,adjt)
# ~ ans = [0]*(n)
# ~ ans[n-1] = yen -dist_s[n] - dist_t[n]
# ~ for i in range(n-2,-1,-1):
	# ~ ans[i] = max(ans[i+1], yen - dist_s[i+1] - dist_t[i+1])
# ~ print(*ans, sep = '\n')
ans = [-1] * n
tmp = float('inf')
for i in range(n, 0, -1):
	if dist_s[i] + dist_t[i] < tmp:
		tmp = dist_s[i] + dist_t[i]
	ans[i-1] = 10 ** 15 - tmp
print(*ans, sep='\n')


### FIXED CODE ###

import heapq
def dijkstra(s, neighbor):
	dist = [float('inf')] * N
	dist[s] = 0
	que = [(0, s)]
	heapq.heapify(que)
	while que:
		d, v = heapq.heappop(que)
		if d > dist[v]:
			continue
		for u, l in neighbor[v]:
			tmp_d = d + l
			if tmp_d < dist[u]:
				dist[u] = tmp_d
				heapq.heappush(que, (tmp_d, u))
	return dist
 
N, M, s, t = map(int, input().split())
yen = [[] for _ in range(N)]
snuuk = [[] for _ in range(N)]
for _ in range(M):
	u, v, a, b = map(int, input().split())
	yen[u-1].append((v-1, a))
	yen[v-1].append((u-1, a))
	snuuk[u-1].append((v-1, b))
	snuuk[v-1].append((u-1, b))
 
dist_s = dijkstra(s-1, yen)
dist_t = dijkstra(t-1, snuuk)
ans = [-1] * N
tmp = float('inf')
for i in range(N-1, -1, -1):
	if dist_s[i] + dist_t[i] < tmp:
		tmp = dist_s[i] + dist_t[i]
	ans[i] = 10 ** 15 - tmp
print(*ans, sep='\n')
### BUGGY CODE ###

n = int(input())
s = input() + '_'
    
dp = [[0]*(n+1) for i in range(n+1)]
for i in range(n-2, -1, -1):
    for j in range(n-1, i,-1):
        if i + dp[i+1][j+1] >= j:
            break
        if s[i] == s[j]:
            dp[i][j] = dp[i+1][j+1] + 1
print(max(list(map(lambda x: max(x), dp))))

### FIXED CODE ###

n = int(input())
s = input() + '_'
    
dp = [[0]*(n+1) for i in range(n+1)]
for i in range(n-2, -1, -1):
    for j in range(n-1, i,-1):
        if i + dp[i+1][j+1] >= j:
            break
        if s[i] == s[j]:
            dp[i][j] = dp[i+1][j+1] + 1
print(max(list(map(lambda x: max(x), dp))))
### BUGGY CODE ###

n,a,b=map(int,input().split())
x=a
y=b
ct=0
while n>0:
  while n>0 and x>0:
    x=x-1
    n=n-1
    ct=ct+1
  while n>0 and y>0:
    y=y-1
    n=n-1
  x=a
  y=b
print(ct)

### FIXED CODE ###

n,a,b=map(int,input().split())
ct=a+b
num=(n//ct)*a
s=n%ct
result=num
result += min(s,a)
print(int(result))
### BUGGY CODE ###

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

import sys
from math import sqrt
from functools import reduce
if sys.version_info.minor >= 5: from math import gcd
else: from fractions import gcd

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for k in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for k in range(c)] for k in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def gcd_list(li): return reduce(gcd, li, 0)

N = INT()
A = LIST()

# 平方分割
D = ceil(sqrt(N))
bucket = [[] for i in range(D)]
gcds = [0] * D
for i in range(N):
    bucket[i//D].append(A[i])
# 各バケットで全体のGCDを予め取っておく
for i in range(D):
    gcds[i] = gcd_list(bucket[i])

ans = 0
for i in range(D):
    for j in range(len(bucket[i])):
        tmp = 0
        # バケット内でa以外全ての要素とGCD
        for k, a in enumerate(bucket[i]):
            if j == k:
                continue
            tmp = gcd(tmp, a)
        # aを含むバケット以外の全てのバケットとGCD
        for k in range(D):
            if i == k:
                continue
            tmp = gcd(tmp, gcds[k])
        ans = max(ans, tmp)
print(ans)


### FIXED CODE ###

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

import sys
if sys.version_info.minor >= 5: from math import gcd
else: from fractions import gcd
from functools import reduce

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def gcd_list(nums): return reduce(gcd, nums, nums[0])
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N=INT()
A=LIST()

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

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

K = int(input())
count = 1
an = 7

if K%2 == 0 or K%2 ==0:
    print("-1")
    exit(0)
while True:
  if an % K == 0:
    print(count)
    exit(0)
  an = 10*an + 7
  count +=1


### FIXED CODE ###

def calc(k):
    cur = 0
    for i in range(1, 10 ** 7):
        cur *= 10
        cur += 7
        cur %= k
        if cur == 0:
            return i

    return -1


k = int(input())
print(calc(k))
### BUGGY CODE ###

S=raw_input()
judge=["dream","dreamer","erase","eraser"]

S_pointer=0

V=set()
V.add(0)

cnt=0
while cnt<len(S):
	tmp=set()
	for i in V:
		for j in judge:
			if S[i:i+7].find(j)==0:	
				tmp.add(i+len(j))

	V=V|tmp
	cnt+=1

#print V

print "YES" if max(V)==len(S) else "NO"

### FIXED CODE ###

import sys
S=raw_input()
judge=["dream","dreamer","erase","eraser"]

V=set()
V.add(0)

cnt=0
while cnt<len(S):
	tmp=set()
	for i in V:
		for j in judge:
			if S[i:i+7].find(j)==0:
				tmp.add(i+len(j))
				if i+len(j)==len(S):
					print "YES"
					sys.exit()
	V=tmp
	cnt+=1
else:
	print "NO"
### BUGGY CODE ###

a=input()
n=len(a)
dupli=0
from itertools import combinations
for i,j in combinations(range(n),2):
    if a[i]==a[j]:
        dupli+=1
print(n*(n-1)//2-dupli+1)

### FIXED CODE ###

a=input()
n=len(a)
dupli=0
from collections import Counter
c=Counter(a)
for word,num in c.most_common():
    dupli+=num*(num-1)//2
print(n*(n-1)//2-dupli+1)
### BUGGY CODE ###

import sys
import fractions
input = sys.stdin.readline
N = int(input())
list_A = list(map(int, input().split()))
ans = 1
sum = 0
for i in range(N):
    ans = ans * list_A[i] // fractions.gcd(ans, list_A[i])
for a in list_A:
    sum += ans//a
print(sum%(7+10**9))

### FIXED CODE ###

import sys
import fractions
input = sys.stdin.readline
N = int(input())
list_A = list(map(int, input().split()))
ans = list_A[0]
sum = 0
for i in range(1, N):
  ans = ans * list_A[i] // fractions.gcd(ans, list_A[i])
for a in list_A:
  sum += ans//a
print(sum%(7+10**9))