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

import queue
import copy
import sys
sys.setrecursionlimit(1000000)

h, w = map(int, input().split())
s = [list(input()) for i in range(h)]

que = queue.Queue()
class stgo:
    def __init__(self):
        self.x = 0
        self.y = 0
        self.depth = 0
y_dist = (0, 0, -1, +1)
x_dist = (-1, +1, 0, 0)
g_y = 0
g_x = 0

def bfs():
    dist = copy.deepcopy(s)
    maxdepth = 0
    while not que.empty():
        now = que.get()
        y = now.y
        x = now.x
        depth = now.depth
        dist[y][x] = depth

        for z in range(4):
            next = stgo()
            next.y = y + y_dist[z]
            next.x = x + x_dist[z]
            next.depth = depth + 1

            if next.y >= 0 and next.y <= h - 1 and next.x >= 0 and next.x <= w - 1 and dist[next.y][next.x] == "." and dist[next.y][next.x] != "#":
                que.put(next)
        maxdepth = max(dist[y][x],maxdepth)
    return maxdepth

ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] != "#":
            start = stgo()
            start.x = j
            start.y = i
            start.depth = 0
            que.put(start)
            ans = max(ans,bfs())
print(ans)

### FIXED CODE ###

import queue

H, W = map(int, input().split())
S = [input() for i in range(H)]
q = queue.Queue()
longest_path = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '.':
            g = [[0 if S[k][l] == '.' else -1 for l in range(W)] for k in range(H)]
            q.put((i,j))
            g[i][j] = 0
            while not(q.empty()):
                x, y = q.get()
                for nx, ny in [(x+1, y),(x-1, y),(x, y+1),(x, y-1)]:
                    if nx < 0 or nx > H-1 or ny < 0 or ny > W-1: continue
                    if g[nx][ny] != 0: continue
                    if nx == i and ny == j: continue
                    g[nx][ny] = g[x][y] + 1
                    q.put((nx,ny))
            longest_path = max(longest_path, max(map(max, g)))
print(longest_path)
### BUGGY CODE ###

x = int(input())
min_dt = 1001001001
min_i = 0
for i in range(1, x+1):
    dt = abs(x - (i+1)*i//2)
    if dt<min_dt:
        min_dt = dt
        min_i = i
    if min_dt == 0:
        print(i)
        break
else:
    print(min_i+min_dt)


### FIXED CODE ###

x = int(input())
i = 1
while True:
    if (i+1)*i//2 >= x:
        print(i)
        break
    i += 1
### BUGGY CODE ###

import sys,math,collections,itertools
input = sys.stdin.readline

s = input().rstrip()[::-1]
DP=[0 for _ in range(13)]

DP[0]=1
m = 10**9+7
mul = 1
for i in range(len(s)):
    dig = s[i]
    nextDP = [0 for _ in range(13)]
    if dig == '?':
        for j in range(10):
            for k in range(13):
                nextDP[(k+mul*j)%13] += DP[k]
                
    else:
        j = int(dig)
        for k in range(13):
            nextDP[(k+mul*j)%13] += DP[k]

    mul *= 10
    DP = nextDP

print(DP[5]%m)
        


### FIXED CODE ###

import sys,math,collections,itertools
input = sys.stdin.readline

s = input().rstrip()[::-1]
DP=[0 for _ in range(13)]

DP[0]=1
m = 10**9+7
mul = 1
for i in range(len(s)):
    dig = s[i]
    nextDP = [0 for _ in range(13)]
    if dig == '?':
        for j in range(10):
            for k in range(13):
                nextDP[(k+mul*j)%13] += DP[k]
                nextDP[(k+mul*j)%13]%=m
    else:
        j = int(dig)
        for k in range(13):
            nextDP[(k+mul*j)%13] += DP[k]
            nextDP[(k+mul*j)%13]%=m

    mul *= 10
    mul%=13
    DP = nextDP

print(DP[5]%m)
### BUGGY CODE ###

mod = 7+10**9
def ncr(n,c,mod):
  x = 1
  y = 1
  for i in range(n-c+1,n+1):
    x = x*i%mod
  for j in range(1,c+1):
    y = y*j%mod
  return (x * pow(y, mod-2, mod)) % mod

a = int(input())
A = list(map(int, input().split()))  
d = {}
for k in A:
  if k in d:
    d[k] += 1
  else:
    d[k] = 1
 
res = 0
for k in d.values():
    if k >= 2:
      res += ncr(k, 2, mod)

for k in A:
  temp = res
  m = d[k]
  if m >= 2:
    temp -= ncr(m, 2, mod)

  d[k] -= 1
  if d[k] >= 2:
    temp += ncr(d[k], 2, mod)
  print(temp)
  d[k] += 1


### FIXED CODE ###

from operator import mul
from functools import reduce

def ncr(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

a = int(input())
A = list(map(int, input().split()))  
d = {}
for k in A:
  if k in d:
    d[k] += 1
  else:
    d[k] = 1
 
res = 0
for k in d:
    if d[k] >= 2:
      res += ncr(d[k], 2)

for k in A:
  temp = res
  m = d[k]
  d[k] -= 1
  if m >= 2:
    temp -= ncr(m, 2)

  if d[k] >= 2:
    temp += ncr(d[k], 2)
  print(temp)
  d[k] += 1
### BUGGY CODE ###

n = int(input())
array = input().split()
b_list = list()
i = 0

while i < n:
    if i % 2 == 0:
        b_list.append(array[i])
    else:
        b_list.insert(0, array[i])
    i += 1

if len(b_list) % 2 != 0:
    i = len(b_list)-1
    while i >= 0:
        print(b_list[i], end = ' ')
        i -= 1
else:
    i = 0
    while i < len(b_list):
        print(b_list[i], end = ' ')
        i += 1

### FIXED CODE ###

import collections

N = int(input())
a = list(map(int, input().split()))
b = collections.deque()

for i in range(N):
    if i % 2 == 0:
        b.appendleft(a[i])
    else:
        b.append(a[i])
    
if N % 2 == 0:
    i = N-1
    while i >= 0:
        print(b[i], end = ' ')
        i -= 1
else:
    for i in range(N):
        print(b[i], end = ' ')
### BUGGY CODE ###

import sys
input=sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
n,q=map(int,input().split())
edges=[[] for i in range(n)]
for i in range(n-1):
    a,s=map(int,input().split());a-=1;s-=1
    edges[a].append(s)
    edges[s].append(a)
cnt=[-1]*n
add=[0]*n
for _ in range(q):
    a,s=map(int,input().split())
    add[a-1]+=s


def f(x):
    if cnt[x]!=-1:return 
    ret=add[x]
    fd=0
    for to in edges[x]:
        if cnt[to]!=-1:ret+=cnt[to];fd=to;break
    cnt[x]=ret
    for to in edges[x]:
        if to!=fd:f(to)
    
    
f(0)
print(*cnt,sep=" ")

### FIXED CODE ###

import sys
input=sys.stdin.buffer.readline
sys.setrecursionlimit(10**9)
n,q=map(int,input().split())
cnt=[0]*(n)
edges=[0]*n
for i in range(n):
    edges[i]=[]
for i in range(n-1):
    a,s=map(int,input().split())
    edges[a-1].append(s-1);edges[s-1].append(a-1)

from collections import deque
dq=deque([])
#pop/append/(append,pop)_left/in/len/count/[]/index/rotate()(右へnずらす)
for i in range(q):
    p,x=map(int,input().split())
    cnt[p-1]+=x

for i in edges[0]:
    dq.append((0,i))
while dq:
    f,t=dq.popleft()
    cnt[t]+=cnt[f]
    for to in edges[t]:
        if to!=f:dq.append((t,to))
    
print(*cnt)
### BUGGY CODE ###

def gcd(m, n):
    while n:
        m, n = n, m % n
    return m


def lcm(x, y):
        return (x*y) // gcd(x, y)


N = int(input())
A = list(map(int, input().split()))
A.sort()
lcm_value = A[0]
for i in range(1, N):
    lcm_value = lcm(lcm_value, A[i])

# print(lcm_value)
mod = 10**9+7
ans = 0
for i in range(N):
    ans += (lcm_value // A[i]) % mod

print(ans % mod)


### FIXED CODE ###

def gcd(m, n):
    while n:
        m, n = n, m % n
    return m


def lcm(x, y):
        return (x*y) // gcd(x, y)


N = int(input())
A = list(map(int, input().split()))
A.sort()
lcm_value = A[0]
for i in range(1, N):
    lcm_value = lcm(lcm_value, A[i])

# print(lcm_value)
mod = 10**9+7
ans = 0
for i in range(N):
    ans += (lcm_value // A[i])

print(ans % mod)
### BUGGY CODE ###

N, K = map(int, input().split())
S = input()
l = []
a = 0
if S[0] == '1':
	a += 1
else:
	l.append(a)
	a += 1
for i in range(1, N, 1):
	if S[i] == S[i - 1]:
		a += 1
	else:
		l.append(a)
		a = 1
l.append(a)
if S[N - 1] == '0':
	l.append(0)
if (len(l) - 1) // 2 + 1 - K < 1:
	print(N)
else:
	m = []
	for k in range((len(l) - 1) // 2 + 1 - K):
		x = l[2 * k]
		for j in range(2 * K):
			x += l[2 * k + j + 1]
		m.append(x)
	print(max(m))


### FIXED CODE ###

N, K = map(int, input().split())
S = input()
l = []
a = 0
if S[0] == '1':
	a += 1
else:
	l.append(a)
	a += 1
for i in range(1, N, 1):
	if S[i] == S[i - 1]:
		a += 1
	else:
		l.append(a)
		a = 1
l.append(a)
if S[N - 1] == '0':
	l.append(0)
if (len(l) + 1) // 2 - K < 1:
	print(N)
else:
	ans = sum(l[0:2 * K + 1])
	n_ans = ans
	for k in range((len(l) - 1) // 2 - K):
		n_ans += l[2 * k + 2 * K + 1] + l[2 * k + 2 * K + 2] - l[2 * k] - l[2 * k + 1]
		ans = max(ans, n_ans)
	print(ans)
### BUGGY CODE ###

h, w = map(int, input().split())
s = [input() for _ in range(h)]

l = [[0 for _ in range(w)] for _ in range(h)]
r = [[0 for _ in range(w)] for _ in range(h)]
u = [[0 for _ in range(w)] for _ in range(h)]
d = [[0 for _ in range(w)] for _ in range(h)]

for i in range(h):
    for j in range(w):
        l[i][j] = 0 if s[i][j] == '#' else (1 if j == 0 else l[i][j-1] + 1)
    for j in range(w-1, -1, -1):
        r[i][j] = 0 if s[i][j] == '#' else (1 if j == w-1 else r[i][j+1] + 1)
for j in range(w):
    for i in range(h):
        u[i][j] = 0 if s[i][j] == '#' else (1 if i == 0 else u[i-1][j] + 1)
    for i in range(h-1, -1, -1):
        d[i][j] = 0 if s[i][j] == '#' else (1 if i == h-1 else d[i+1][j] + 1)

m = 0
for i in range(h):
    for j in range(w):
        k = l[i][j] + r[i][j] + u[i][j] + d[i][j] - 3
        if k > m:
            m = k

print(m)

### FIXED CODE ###

h, w = map(int, input().split())
s = [input() for _ in range(h)]

l = [[0 for _ in range(w)] for _ in range(h)]
r = [[0 for _ in range(w)] for _ in range(h)]
u = [[0 for _ in range(w)] for _ in range(h)]
d = [[0 for _ in range(w)] for _ in range(h)]

for i in range(h):
    for j in range(w):
        l[i][j] = 0 if s[i][j] == '#' else (1 if j == 0 else l[i][j-1] + 1)
    for j in range(w-1, -1, -1):
        r[i][j] = 0 if s[i][j] == '#' else (1 if j == w-1 else r[i][j+1] + 1)
for j in range(w):
    for i in range(h):
        u[i][j] = 0 if s[i][j] == '#' else (1 if i == 0 else u[i-1][j] + 1)
    for i in range(h-1, -1, -1):
        d[i][j] = 0 if s[i][j] == '#' else (1 if i == h-1 else d[i+1][j] + 1)

m = 0
for i in range(h):
    for j in range(w):
        k = l[i][j] + r[i][j] + u[i][j] + d[i][j] - 3
        if k > m:
            m = k

print(m)
### BUGGY CODE ###

from bisect import*
def main():
    class BTreeNode:
        def __init__(self):self.key,self.child=[],[]
    root=BTreeNode()
    def search_higher(key):
        ptr=root
        ret=None
        while ptr.child:
            i=bisect(ptr.key,key)
            if i!=len(ptr.key):ret=ptr.key[i]
            ptr=ptr.child[i]
        i=bisect(ptr.key,key)
        if i!=len(ptr.key):ret=ptr.key[i]
        return ret
    def search_lower(key):
        ptr=root
        ret=None
        while ptr.child:
            i=bisect_left(ptr.key,key)
            if i!=0:ret=ptr.key[i-1]
            ptr=ptr.child[i]
        i=bisect_left(ptr.key,key)
        if i!=0:ret=ptr.key[i-1]
        return ret
    def insert_rec(ptr,key):
        b_size=1024
        if not ptr.child:
            insort(ptr.key,key)
            if len(ptr.key)==b_size*2-1:
                    ret=BTreeNode()
                    ret.key=ptr.key[:b_size]
                    ptr.key=ptr.key[b_size:]
                    return ret
        else:
            i=bisect(ptr.key,key)
            tmp=insert_rec(ptr.child[i],key)
            if tmp:
                ptr.key.insert(i,tmp.key.pop())
                ptr.child.insert(i,tmp)
                if len(ptr.child)==b_size*2:
                    ret=BTreeNode()
                    ret.child=ptr.child[:b_size]
                    ptr.child=ptr.child[b_size:]
                    ret.key=ptr.key[:b_size]
                    ptr.key=ptr.key[b_size:]
                    return ret
    def insert(key):
        tmp=insert_rec(root,key)
        if tmp:root.key,root.child=[tmp.key.pop()],[tmp,root]
    n,*a=map(int,open(0).read().split())
    l=[0]*n
    for i,v in enumerate(a,1):l[v-1]=i
    insert(0)
    insert(n+1)
    c=0
    for i,v in enumerate(l,1):
        c+=(search_higher(v)-v)*(v-search_lower(v))*i
        insert(v)
    print(c)
main()

### FIXED CODE ###

root=lambda x:x if par[x]==x else root(par[x])
same=lambda x,y:root(x)==root(y)
def unite(*z):
  x,y=map(root,z)
  if x!=y:
    if rank[x]<rank[y]:
      par[x]=y
      size[y]+=size[x]
    else:
      par[y]=x
      size[x]+=size[y]
      if rank[x]==rank[y]:rank[x]+=1
n,*a=map(int,open(0).read().split())
*par,=range(n)
rank=[1]*n
size=[1]*n
b=[0]*n
for i,t in enumerate(a):b[t-1]=i
c=0
for k in b[::-1]:
  l=r=1
  if k>0 and a[k-1]>a[k]:
    l+=size[root(k-1)]
    unite(k-1,k)
  if k+1<n and a[k+1]>a[k]:
    r+=size[root(k+1)]
    unite(k+1,k)
  c+=l*r*a[k]
print(c)
### BUGGY CODE ###

from collections import Counter
n,m=map(int,input().split())
l=[]
for _ in range(m):
  a,b=map(int,input().split())
  if a>b:a,b=b,a
  l.extend([(i,i+1) for i in range(a,b)])
c=Counter(l)
*v,=filter(lambda x:x%2,c.values())
if v:
  print("NO")
else:
  print("YES")

### FIXED CODE ###

from itertools import accumulate as ac
n,m=map(int,input().split())
l=[0]*(n+1)
for _ in range(m):
  a,b=map(int,input().split())
  if a>b:a,b=b,a
  l[a]+=1
  l[b]-=1

*l,=ac(l)
*l,=filter(lambda x:x%2,l)
if l:
  print("NO")
else:
  print("YES")
### BUGGY CODE ###

import math
S = input()
Q = int(input())

def reverse_list(S):
    if len(S) == 1:
        return S
    else:
        return S[::-1]

def moji_tuika(S, f, c):
    if f == 1:
        return c + S
    else:
        return S + c

q = []
for i in range(Q):
    temp = input().split()
    if len(temp) == 1:
        q.append(1)
    else:
        t = int(temp[0])
        f = int(temp[1])
        c = temp[2]
        q.append((t,f,c))

for i in q:
    if type(i) == int:
        S = reverse_list(S)
    elif i[0] == 2:
        S = moji_tuika(S,i[1],i[2])

print(S)


### FIXED CODE ###

from collections import deque

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

lr = 'left'

def reverse_list(lr):
    if lr == 'right':
        return 'left'
    else:
        return 'right'

def moji_tuika(S, f, c, lr):
    if f == 1 and lr == 'left':
        S.appendleft(c)
    elif f == 1 and lr == 'right':
        S.append(c)
    elif f == 2 and lr == 'left':
        S.append(c)
    else:
        S.appendleft(c)
    return S

q = []
for i in range(Q):
    temp = input().split()
    if len(temp) == 1:
        q.append(1)
    else:
        q.append(temp)

S = deque(list(S))
for i in q:

    if type(i) == int:
        lr = reverse_list(lr)
    elif int(i[0]) == 2:
        S = moji_tuika(S,int(i[1]),i[2],lr)
if lr == 'right':
    S.reverse()

S = ''.join(S)
print(S)
### BUGGY CODE ###

dic = []
n = int(input())
for i in range(n):
    a = input()
    t=a.split()
    if t[0] == "insert":
        dic.append(t[1])
    else:
        if t[1] in dic:
            print("yes")
        else:
            print("no")
    

### FIXED CODE ###

dic=dict()
n = int(input())
for i in range(n):
    a = input()
    t=a.split()
    if t[0] == "insert":
        dic[t[1]] = True
    else:
        if t[1] in dic:
            print("yes")
        else:
            print("no")
### BUGGY CODE ###

def main():
    n=int(input())
    nn=2*n
    s=[input() for _ in [0]*n]
    s=[i+i[:-1] for i in s]+[i+i[:-1] for i in s][:-1]
    ans=[[0]*n for _ in [0]*n]
    for i in range(1,nn-1):
        m=min(i+1,n)
        for j in range(nn-2):
            for k in range(1,min(m,nn-1-j)):
                ii=i-k
                if s[i][j]!=s[ii][j+k]:
                    l=min(n-k+1,ii,j)
                    width=l-max(-1,ii-n,j-n)
                    if width<1:
                        continue
                    ans[ii-l][j-l]=max(ans[ii-l][j-l],width)
    for i in range(n-1):
        for j in range(n-1):
            ans[i+1][j+1]=max(ans[i+1][j+1],ans[i][j]-1)
    print(sum([sum([i==0 for i in a]) for a in ans]))
main()

### FIXED CODE ###

def main():
    n=int(input())
    nn=2*n-1
    s=[input() for _ in [0]*n]
    s=[i+i[:-1] for i in s]+[i+i[:-1] for i in s][:-1]
    ans=[[0]*n for _ in [0]*n]
    for i in range(1,nn):
        m=min(i+1,n)
        for j in range(nn-1):
            for k in range(max(i-j-n,0)+1,min(m,nn-j,i-j+n)):
                ii=i-k
                if s[i][j]!=s[ii][j+k]:
                    l=min(n-k+1,ii,j)
                    width=l-max(-1,ii-n,j-n)
                    ans[ii-l][j-l]=max(ans[ii-l][j-l],width)
    for i in range(1,n):
        for j in range(1,n):
            ans[i][j]=max(ans[i][j],ans[i-1][j-1]-1)
    print(sum([sum([i==0 for i in a]) for a in ans]))
main()
### BUGGY CODE ###

# coding: utf-8
N = int(input())
A = list(map(int, input().split()))

for i in range(N):
    print(A.count(i+1))

### FIXED CODE ###

# coding: utf-8
N = int(input())
A = list(map(int, input().split()))
C = [0 for i in range(N)]
A.sort()
i = 0
while i < N - 1:
    C[A[i] - 1] = C[A[i] - 1] + 1
    i += 1

for i in C:
    print(i)
### BUGGY CODE ###

def main():
    S = input()
    l = []
    l2 = []
    mod = (10 ** 9) + 7
    for i in range(6):
        d = [0] * 13
        d2 = [0] * 10
        for j in range(0, 10):
            t = (j *(10 ** i)) % 13
            d[t] += 1
            d2[j] = t
        l.append(d)
        l2.append(d2)
    r = 0
    c = [0] * 13
    c[0] = 1
    n = [0] * 13
    i = 0
    for v in reversed(S):
        if v == '?':
            k = 0
            for j in range(13):
                for k in range(13):
                    if l[i][j]:
                        kk = (j+k) % 13
                        n[kk] += c[k]
                        n[kk] %= mod
            c = n
            n = [0] * 13
        else:
            r += (l2[i][int(v)])
            r %= 13
        i += 1
        i %= 6
    r = (5 - r) % 13
    print(c[r] % mod)
main()



### FIXED CODE ###

def main():
    S = input()
    l = []
    l2 = []
    mod = (10 ** 9) + 7
    for i in range(6):
        d = [0] * 13
        d2 = [0] * 10
        for j in range(0, 10):
            t = (j *(10 ** i)) % 13
            d[t] += 1
            d2[j] = t
        l.append(d)
        l2.append(d2)
    r = 0
    c = [0] * 13
    c[0] = 1
    n = [0] * 13
    i = 0
    for v in reversed(S):
        if v == '?':
            k = 0
            for j in range(13):
                for k in range(13):
                    if l[i][j]:
                        kk = (j+k) % 13
                        n[kk] += c[k]
                        n[kk] %= mod
            c = n
            n = [0] * 13
        else:
            r += (l2[i][int(v)])
            r %= 13
        i += 1
        i %= 6
    r = (5 - r) % 13
    print(c[r] % mod)
main()
### BUGGY CODE ###

P=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101]
n=int(input())
A=[1]*n

for i in range(n):
	s=input()
	for j in range(10):
		A[i] *= P[ord(s[j])-97]

res=0
for i in range(n):
	for j in range(i+1,n):
		if A[i]==A[j]:
			res += 1
print(res)

### FIXED CODE ###

P=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101]
n=int(input())
A=[1]*n

for i in range(n):
	s=input()
	for j in range(10):
		A[i] *= P[ord(s[j])-97]

res=0
A.sort()
cnt=0

for i in range(n-1):
		if A[i]==A[i+1]:
			cnt += 1
		else:
			res += cnt*(cnt+1)//2
			cnt=0
if cnt != 0:
	res += cnt*(cnt+1)//2
print(res)
### BUGGY CODE ###

from math import factorial

def pff(m):
    pf = {}
    for i in range(2, int(m ** 0.5) + 1):
        while m % i == 0:
            pf[i] = pf.get(i, 0) + 1
            m //= i
    if m > 1: pf[m] = 1
    return pf



def comb(n, r):
    return factorial(n) // (factorial(n - r) * factorial(r))


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

anst = int(1)
for i in L.values():
    anst *= comb(i+N-1, i)
    anst = anst%1000000007

ans = anst
print(ans)

### FIXED CODE ###

from math import factorial
from operator import mul
from functools import reduce

def comb2(n,r):
    r = min(n - r, r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under

def pff(m):
    pf = {}
    for i in range(2, int(m ** 0.5) + 1):
        while m % i == 0:
            pf[i] = pf.get(i, 0) + 1
            m //= i
    if m > 1: pf[m] = 1
    return pf

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


anst = int(1)
for i in L.values():
    anst *= comb2(i+N-1, i)
    anst = anst%1000000007

ans = anst
print(ans)
### BUGGY CODE ###

from fractions import gcd
N = int(input())
A = list(map(int, input().split()))
class SegTree:
  def segfunc(self, x, y):
    return gcd(x, y) #ここ判定関数（ただし結合則があるもの）
  def __init__(self, n, ide_ele, init_val):
    #####単位元######
    self.ide_ele = ide_ele
    #num:n以上の最小の2のべき乗
    self.num = 2 ** (n - 1).bit_length()
    self.seg = [self.ide_ele] * 2 * self.num
    #set_val
    for i in range(N):
      self.seg[i + self.num - 1] = init_val[i]    
    #built
    for i in range(self.num - 2, -1, -1) :
      self.seg[i] = self.segfunc(self.seg[2 * i + 1], self.seg[2 * i + 2]) 
  def update(self, k, x):
    k += self.num - 1
    self.seg[k] = x
    while k + 1:
      k = (k - 1) // 2
      self.seg[k] = self.segfunc(self.seg[k * 2 + 1], self.seg[k * 2 + 2]) 
  def query(self, p, q):
    if q <= p:
      return self.ide_ele
    p += self.num - 1
    q += self.num - 2
    res = self.ide_ele
    while q - p > 1:
      if p & 1 == 0:
        res = self.segfunc(res, self.seg[p])
      if q & 1 == 1:
        res = self.segfunc(res, self.seg[q])
        q -= 1
      p = p // 2
      q = (q - 1) // 2
    if p == q:
      res = self.segfunc(res, self.seg[p])
    else:
      res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
    return res
sg = SegTree(N, 0, A)
res = 0
for i in range(N):
  res = max(res, gcd(sg.query(0, i), sg.query(i + 1, N)))
print(res)

### FIXED CODE ###

from fractions import gcd
n = int(input())
A = list(map(int, input().split()))
#####単位元######
ide_ele = 0

#num:n以上の最小の2のべき乗
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num

#####segfunc######
def segfunc(x,y):
    return gcd(x, y) 

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]    
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x):
    k += num-1
    seg[k] = x
    while k+1:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res
  
init(A)
result = 0
for i in range(n):
  temp = gcd(query(0, i), query(i + 1, n))
  result = max(result, temp)
print(result)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(500000)

N, Q = map(int, input().split())
G = [set() for _ in range(N)]
cnt = [0]*N
visited = [0]*N

def dfs(start_node):
    for i in G[start_node]:
        if visited[i]==0:
            visited[i]=1
            cnt[i] += cnt[start_node]
            dfs(i)

for _ in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    G[a].add(b)
    G[b].add(a)

for i in range(Q):
    node, x = map(int, input().split())
    node -= 1
    cnt[node] += x

visited[0]=1
dfs(0)
print(*cnt)


### FIXED CODE ###

import sys
sys.setrecursionlimit(500000)

N, Q = map(int, input().split())
G = [set() for _ in range(N)]
cnt = [0]*N
visited = [0]*N

def dfs(start_node):
    for i in G[start_node]:
        if visited[i]==0:
            visited[i]=1
            cnt[i] += cnt[start_node]
            dfs(i)

for _ in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    G[a].add(b)
    G[b].add(a)

for i in range(Q):
    node, x = map(int, input().split())
    node -= 1
    cnt[node] += x

visited[0]=1
#dfs(0)
st = [0]
while st:
    v = st.pop()
    for u in G[v]:
        if visited[u]: continue
        visited[u] = 1
        cnt[u] += cnt[v]
        st.append(u)    

ans = map(str, cnt)
print(' '.join(ans))