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

class BIT:
    def __init__(self, N):
        self.tree = [0] * (N + 1)  # 1-indexed
        self.N = N

    def add(self, i, x):
        """tree[i]と関連個所にxを加える"""
        tree = self.tree
        N = self.N
        while i <= N:
            tree[i] += x
            i += i & (-i)

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


def main():
    from string import ascii_lowercase
    import sys
    input = sys.stdin.readline

    N = int(input())
    s = input().rstrip()
    Q = int(input())

    conv = {c: i for i, c in enumerate(ascii_lowercase)}
    s = [conv[c] for c in s]

    bs = [BIT(N) for _ in range(26)]
    for i, c in enumerate(s, 1):
        bs[c].add(i, 1)

    ans = []
    for _ in range(Q):
        it = iter(input().split())
        if next(it) == '1':
            # change
            i = int(next(it))  # 1-indexed
            c = conv[next(it)]

            p = s[i - 1]
            bs[p].add(i, -1)

            s[i - 1] = c
            bs[c].add(i, 1)

        else:
            # count
            l, r = map(int, it)
            cnt = 0
            for b in bs:
                cnt += int(b.sum(r) - b.sum(l - 1) > 0)
            ans.append(cnt)
    print(*ans, sep='\n')


if __name__ == '__main__':
    main()


### FIXED CODE ###

class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0] * (n + 1)
        self.el = [0] * (n + 1)

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

    def add(self, i, x):
        # assert i > 0
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i

    def get(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)


def main():
    import sys

    input = sys.stdin.readline

    n = int(input())  # 5 * 10 ** 5
    s = input().rstrip()

    base = ord('a')
    *s, = (ord(c) - base for c in s)

    q = int(input())  # 2 * 10 ** 4

    bits = [BIT(n + 1) for _ in range(26)]
    for i, x in enumerate(s, 1):
        bits[x].add(i, 1)

    ret = []
    for _ in range(q):
        query = iter(input().split())
        if next(query) == '1':
            # 変更
            pos = int(next(query))

            bf = s[pos - 1]
            char = ord(next(query)) - base

            bits[bf].add(pos, -1)
            s[pos - 1] = char

            bits[char].add(pos, 1)

        else:
            # 返答
            l = int(next(query))
            r = int(next(query))

            tt = 0
            for x in range(26):
                if bits[x].get(l - 1, r) > 0:
                    tt += 1
            ret.append(tt)

    print(*ret, sep='\n')


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())
### BUGGY CODE ###

K = int(input())
A = "0123456789"
S = [i for i in range(1,10)]
Q = [str(i) for i in range(1,10)]
while Q:
    q = Q.pop(0)
    D = []
    if q[-1]=="0":
        D = [q+"0",q+"1"]
    elif q[-1]=="9":
        D = [q+"0",q+"1"]
    else:
        a = A.index(q[-1])
        D = [q+A[a-1],q+A[a],q+A[a+1]]
    for d in D:
        S.append(int(d))
        if len(d)<11:
            Q.append(d)
S.sort()
print(S[K-1])

### FIXED CODE ###

K = int(input())
A = "0123456789"
S = []
def f(n):
    global A,S
    if len(n)>10:return
    if n[-1]=="0":
        D=(n+"0",n+"1")
    elif n[-1]=="9":
        D=(n+"9",n+"8")
    else:
        a = A.index(n[-1])
        D=(n+A[a],n+A[a-1],n+A[a+1])
    for d in D:
        S.append(int(d))
        f(d)

for i in range(1,10):
    S.append(i)
    f(str(i))
S.sort()
print(S[K-1])
### BUGGY CODE ###

Sum = input().split()
while ('+' in Sum) or ('-' in Sum) or ('*' in Sum) :
    for che in 2, 3 :
        if Sum[che] == '+' : 
            Sum.insert((che - 2), (int(Sum.pop(che - 2)) + int(Sum.pop(che - 2))))
            del Sum[che - 1]
        elif Sum[che] == '-' :
            Sum.insert((che - 2), (int(Sum.pop(che - 2)) - int(Sum.pop(che - 2))))
            del Sum[che - 1]
        elif Sum[2] == '*' : 
            Sum.insert((che - 2), (int(Sum.pop(che - 2)) * int(Sum.pop(che - 2))))
            del Sum[che - 1]
        if ('+' not in Sum) and ('-' not in Sum) and ('*' not in Sum) : break
print(Sum[0])

### FIXED CODE ###

Sum = input().split()
cou = 1
while len(Sum) != 1 :
    cou += 1
    if Sum[cou] == '+' :
        del Sum[cou]
        Sum.insert((cou - 2) ,int(Sum.pop(cou - 2)) + int(Sum.pop(cou - 2)))
        cou -= 2
    elif Sum[cou] == '-' :
        del Sum[cou]
        Sum.insert((cou - 2) ,int(Sum.pop(cou - 2)) - int(Sum.pop(cou - 2)))
        cou -= 2
    elif Sum[cou] == '*' :
        del Sum[cou]
        Sum.insert((cou - 2) ,int(Sum.pop(cou - 2)) * int(Sum.pop(cou - 2)))
        cou -= 2

print(Sum[0])
### BUGGY CODE ###

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

lst=[]
for i in range(N-1):
    if S[i]=="A" and S[i+1]=="C":
        lst.append(i)

ans=[]
for j in range(Q):
    count=0
    l,r = lr[j][0]-1, lr[j][1]-1
    for p in lst:
        if l <= p and p+1 <= r:
            count += 1
    ans.append(count)

for a in ans:
    print(a)


### FIXED CODE ###

import bisect
N, Q = map(int, input().split())
S = list(input())
lr = [list(map(int, input().split())) for i in range(Q)]

alst,clst=[],[]
for i in range(N-1):
    if S[i]=="A" and S[i+1]=="C":
        alst.append(i)
        clst.append(i+1)

ans=[]
for j in range(Q):
    l,r = lr[j][0]-1, lr[j][1]-1
    ans.append(bisect.bisect_right(clst,r) - bisect.bisect_left(alst,l))

for a in ans:
    print(a)
### BUGGY CODE ###

def main():
    from itertools import accumulate, product

    def binary_search(a, x, lo, hi):
        while lo < hi:
            mid = (lo + hi) // 2
            if a[mid] < x:
                lo = mid + 1
            else:
                hi = mid
        return lo

    n = int(input())
    *a, = map(int, input().split())
    acc = (0,) + tuple(accumulate(a))

    # [0,i), [i,j), [j,k), [k, n)

    ret = acc[-1]
    for j in range(2, n - 1):
        left = acc[j]
        right = acc[-1] - left

        i = binary_search(acc, left // 2, 2, j + 2)
        k = binary_search(acc, left + (right // 2), j + 2, n + 1)

        li = i - 1, i
        rk = k - 1, k

        for i, k in product(li, rk):
            if i <= 0 or k <= j:
                continue
            pqrs = acc[i], left - acc[i], acc[k] - left, acc[-1] - acc[k]
            ret = min(
                ret,
                max(pqrs) - min(pqrs)
            )

    print(ret)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from bisect import bisect_left
from itertools import accumulate

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

cumsum = (0,) + tuple(accumulate(a))
# print(cumsum)

# PQ := [0, cut)
# RS = [cut, n)

ans = cumsum[-1]
for cut in range(2, n - 1):
    # cumsum[cut] : PQ区間和
    # cumsum[lc], cumsum[lc_1] : P区間和の候補
    # cumsum[n] - cumsum[cut] : RS区間和
    # cumsum[rc], cumsum[rc_1] : R区間和 + sPQの候補

    sPQ = cumsum[cut]
    sRS = cumsum[n] - cumsum[cut]

    lc = bisect_left(cumsum, sPQ // 2)
    # x以上で最小, 累積和のindexは、aの1-indexedに対応
    lc_1 = lc - 1
    # x未満で最大

    if abs((sPQ - cumsum[lc]) - cumsum[lc]) < abs((sPQ - cumsum[lc_1]) - cumsum[lc_1]):
        sP = cumsum[lc]
        # print('sP', sP, lc, cumsum)
    else:
        sP = cumsum[lc_1]
        # print('sP', sP, lc_1, cumsum)
    sQ = sPQ - sP
    # print('sQ', sQ)

    rc = bisect_left(cumsum, sPQ + (sRS // 2))
    # x以上で最小, 累積和のindexは、aの1-indexedに対応
    rc_1 = rc - 1
    # x未満で最大

    if abs((sRS - (cumsum[rc] - sPQ)) - (cumsum[rc] - sPQ)) < abs((sRS - (cumsum[rc_1] - sPQ)) - (cumsum[rc_1] - sPQ)):
        sR = cumsum[rc] - sPQ
        # print('sR', sR, rc, cumsum)
    else:
        sR = cumsum[rc_1] - sPQ
        # print('sR', sR, rc_1, cumsum)
    sS = sRS - sR
    # print('sS', sS)

    t = (sP, sQ, sR, sS)

    ans = min(ans, max(t) - min(t))
    # print(t)
print(ans)
### BUGGY CODE ###

a,b = list(map(int, input().split()))
ans = 0

if 3*a < b:
  print(ans)
else:
  for i in range(a+1):
    if i > b:
      continue
    else:
      for j in range(a+1):
        if i+j > b:
          continue
        else:
          if i+j+a < b:
            continue
          else:
            for k in range(a+1):
              if i+j+k == b:
                ans += 1
              
  print(ans)


### FIXED CODE ###

k,s = list(map(int, input().split()))
ans = 0
for x in range(k+1):
  mx = min(k, s-x)
  mn = max(0, s-x-k)
  ans += max(0, mx-mn+1)
print(ans)
### BUGGY CODE ###

from itertools import permutations, combinations, product
import numpy as np

N = int(input())
A = list(map(int, input().split()))
S = np.array(list(combinations(A,2)))
M = 10**9 + 7

cnt = sum(np.product(S, axis=1)) % M

print(cnt)

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
M = 10**9 + 7

S = sum(A)
S2 = sum(map(lambda x: x**2, A))
print(((S**2 - S2)// 2)%M)
### BUGGY CODE ###

def test(i, results):
    filled_num = str(i).zfill(3)
    target = list(filled_num)
    index = 0
    j = 0
    for k in range(index, len(S), 1):
        if S[k] == target[j]:
            index = k + 1
            j += 1
            if j == 3:
                results.add(filled_num)
                return


N = int(input())
S = list(input())

results = set()

for i in range(1000):
    test(i, results)

print(len(results))


### FIXED CODE ###

def test(original: list, nums: str, index: int,
         remain_count: int, results: set, results_1, results_2):
    # 3桁抽出したら終了
    if len(nums) == 1:
        if nums in results_1:
            return
        results_1.add(nums)
    if len(nums) == 2:
        if nums in results_2:
            return
        results_2.add(nums)
    if len(nums) == 3:
        # print("".join(array))
        results.add(nums)
        return
    # 最終桁に到達したら終了
    if index == len(original):
        return
    for i in range(index, len(original), 1):
        test(
            original,
            nums + original[i],
            i + 1,
            remain_count,
            results,
            results_1,
            results_2)

    # この桁を抽出対象としないパターン
    # test(original, array[:], index + 1, remain_count - 1, results)


N = int(input())
S = list(input())

results = set()
results_1 = set()
results_2 = set()

# N個の要素
# N-3個を削除
# 3個の組み合わせが何通りあるか？
test(S, "", 0, N - 3, results, results_1, results_2)

print(len(results))
### BUGGY CODE ###

n = int(input())
s = input()

cnt = []
cnt.append(s[1:].count("E"))
cnt.append(s[:n].count("W"))
for i in range(1, n-1):
    a = s[:i].count("W")
    b = s[i+1:].count("E")
    cnt.append(a+b)
print(min(cnt))

### FIXED CODE ###

import numpy as np

n = int(input())
s = input()
s_W = [0]
s_E = []

for i in range(n):
    if s[i] == "W":
        s_W.append(1)
        s_E.append(0)
    else:
        s_W.append(0)
        s_E.append(1)

W_l = np.cumsum(np.array(s_W))
E_l = np.cumsum(np.array(s_E))

ans = []
for j in range(n):
    num = W_l[j]-W_l[0]+E_l[-1]-E_l[j]
    ans.append(num)
print(min(ans))
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
c = 0
for i in range(N+1):
  for j in range(i, N):
    if sum(A[i:j+1])==0:
      c += 1
print(c)

### FIXED CODE ###

import collections
N = int(input())
A = list(map(int, input().split()))
S = [0]
for i in range(len(A)):
  S.append(A[i]+S[i])
L = list(collections.Counter(S).values())
s = 0
for l in L:
  s += int((l-1)*l//2)
print(s)
### BUGGY CODE ###

from operator import itemgetter

n, m = map(int, input().split())
a = list(map(int, input().split()))
bc = [list(map(int, input().split())) for _ in range(m)]
bc.sort(key=itemgetter(1), reverse=True)

changed = []

for b, c in bc:
    changed = changed + [c] * b
    if len(changed) > n:
        break

a = a + changed
a.sort(reverse=True)
ans = sum(a[:n])

print(ans)

### FIXED CODE ###

import heapq

n, m = map(int, input().split())
a = list(map(int, input().split()))
heapq.heapify(a)
bc = sorted(
    [list(map(int, input().split())) for _ in range(m)],
    reverse=True,
    key=lambda x: x[1],
)

for i in bc:
    b, c = i
    for _ in range(b):
        mn = heapq.heappop(a)
        if mn < c:
            heapq.heappush(a, c)
        else:
            heapq.heappush(a, mn)
            break

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

n = int(input())
a = 1
for i in range(1,n+1):
    a = i*a
a = a%(10**9+7)
print(a)

### FIXED CODE ###

import math
n = int(input())
a = math.factorial(n)
print(a%(10**9+7))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(4100000)
N = int(input())
tree = [[] for _ in range(N+1) ]
already_make = [-1]*(N+1)
for i in range(1,N):
    a,b = map(int,input().split(' '))
    tree[a].append([b,i])

last_color = 0
bfs_use_coler = [[] for _ in range(N+1)]

def solve(n,last_color):
    '''
    use_colers =[]
    for val in bfs_use_coler[0:n-2]:
        use_colers = use_colers + val
    '''
    for val in tree[n]:
        if already_make[val[1]] != -1:
            continue
        use_coloer = -1
        length = last_color+1
        a_tree = list(set(list(range(1,length))) - set(bfs_use_coler[val[0]]) )
        b_tree = list(set(list(range(1,length)))  - set(bfs_use_coler[n])) 
        ab_tree = list(set(a_tree)& set(b_tree))
        '''
        for i in range(1,length):
            if i in bfs_use_coler[val[0]] or i in bfs_use_coler[n]:
                continue
            else:
                use_coloer = i
                break
        if use_coloer == -1:
            last_color +=1
            use_coloer = last_color
        '''
        if len(ab_tree) > 0:
            use_coloer = ab_tree[0]
        else:
            last_color +=1
            use_coloer = last_color
        bfs_use_coler[val[0]].append(use_coloer)
        bfs_use_coler[n].append(use_coloer)
        already_make[val[1]] = use_coloer
    return last_color

for i in range(1,N+1):
    last_color = solve(i,last_color)
print(last_color)
for val in already_make[1:N]:
    print(val)



### FIXED CODE ###

import sys
sys.setrecursionlimit(4100000)
N = int(input())
tree = [[] for _ in range(N+1) ]
already_make = [-1]*(N+1)
for i in range(1,N):
    a,b = map(int,input().split(' '))
    tree[a].append([b,i])

last_color = 0
#bfs_use_coler = [[ -1 for _ in range(N+1) ] for _ in range(N+1) ] 

def solve_bfs(previous_colors,n_list,last_color):
    '''
    use_colers =[]
    for val in bfs_use_coler[0:n-2]:
        use_colers = use_colers + val
    '''
    next_colors = []
    next_n_list =[]
    for idx1,n in enumerate(n_list):
        use_color_num = 1
        for idx2,val in enumerate(tree[n]):
            if use_color_num == previous_colors[idx1]:
                use_color_num += 1
            already_make[val[1]] = use_color_num
            next_colors.append(use_color_num)
            next_n_list.append(val[0])
            last_color = max(use_color_num,last_color)
            use_color_num += 1
    if len(next_colors) > 0:
        return solve_bfs(next_colors,next_n_list,last_color)
    else:
        return last_color

last_color = solve_bfs([0],[1],last_color)
print(last_color)
for val in already_make[1:N]:
    print(val)
### BUGGY CODE ###

from bisect import bisect
inf=float("inf")
a,b,q=map(int,input().split())
s=[int(input()) for _ in range(a)]
t=[int(input()) for _ in range(b)]
x=[int(input()) for _ in range(q)]
for i in range(q):
    west=inf
    east=inf
    c=inf
    d=inf
    j=bisect(s,x[i])
    k=bisect(t,x[i])
    if j!=a and k!=0:
        c=s[j]-t[k-1]+min(s[j]-x[i],x[i]-t[k-1])
    if k!=b and j!=0:
        d=t[k]-s[j-1]+min(x[i]-s[j-1],t[k]-x[i])
    if j!=0 and k!=0:
        west=max(x[i]-s[j-1],x[i]-t[k-1])
    if j!=a and k!=b:
        east=max(s[j]-x[i],t[k]-x[i])
    print(min(west,east,c,d))

### FIXED CODE ###

from bisect import bisect
inf=float("inf")
a,b,q=map(int,input().split())
s=[int(input()) for _ in range(a)]
t=[int(input()) for _ in range(b)]
x=[int(input()) for _ in range(q)]
for i in range(q):
    west=inf
    east=inf
    c=inf
    d=inf
    j=bisect(s,x[i])
    k=bisect(t,x[i])
    if j!=a and k!=0:
        c=s[j]-t[k-1]+min(s[j]-x[i],x[i]-t[k-1])
    if k!=b and j!=0:
        d=t[k]-s[j-1]+min(x[i]-s[j-1],t[k]-x[i])
    if j!=0 and k!=0:
        west=max(x[i]-s[j-1],x[i]-t[k-1])
    if j!=a and k!=b:
        east=max(s[j]-x[i],t[k]-x[i])
    print(min(west,east,c,d))
### BUGGY CODE ###

k = int(input())
i = 0
s = 0

if k % 2 == 0:
    print('-1')
    exit()

while True:
    i += 1
    s = 7 + 10*s
    if s % k == 0:
        break

print(i)

### FIXED CODE ###

K = int(input())
 
num = 0
cnt = 0
ans = -1
 
for i in range(K):
    num = num*10 +7
    cnt += 1
    if num%K != 0:
        num = num%K
    else:
        ans = cnt
        break
    
print(ans)
### BUGGY CODE ###

import collections
s = input()
dp = [0 for i in range(len(s)+1)]
for i in range(1,len(s)+1):
    k = len(s) - i
    dp[i] = (dp[i-1] + int(s[k])*(10**(i-1)))%2019

count_d = collections.defaultdict(int)
for mod in dp:
    count_d[mod] += 1

cnt = 0
for v in count_d.values():
    if v >= 2:
        cnt += v*(v-1)//2
print(cnt)

### FIXED CODE ###

mods = [0]*2019
mods[0] = 1
s = input()
t = 0
u = 1
for i in range(1,len(s)+1):
    t = (t + int(s[-i])*u)%2019
    u = u*10%2019
    mods[t] += 1


cnt = 0
for x in mods:
    if x >= 2:
        cnt += x*(x-1)/2
print(int(cnt))
### BUGGY CODE ###

n,m=map(int,input().split())
t=[]
s=list(map(int,input().split()))
for i in list(set(s)):
    t.append(s.count(i))
print(sum(sorted(t)[:len(t)-m]))  


### FIXED CODE ###

N,K=map(int,input().split())
d,ans={},0
for i in list(map(int,input().split())):
    d[i]=d.get(i,0)+1
s=sorted(d.values())
for i in range(len(s)-K):
    ans+=s[i]
print(ans)
### BUGGY CODE ###

s,_,*q=open(0)
a=['',s[:-1]]
p=1
for q in q:p^=q<'2';a[(q<'2 2')^p]+=q[-2]*(q>'2')
print(a[p^1][::-1]+a[p])

### FIXED CODE ###

from collections import*
s,_,*q=open(0)
d=deque(s[:-1])
p=1
for q in q:
  try:
    q,f,c=q.split()
    if(f<'2')^p:d+=c,
    else:d.appendleft(c)
  except:p^=1
print(''.join(d)[::p or-1])
### BUGGY CODE ###

N, M = map(int, input().split())
P = list(map(int, input().split()))

class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

res = 0
uf = UnionFind(N)
for _ in range(M):
    x, y = map(int, input().split())
    uf.union(x-1, y-1)

for g in uf.all_group_members().values():
    e = []
    for i in g:
        e.append(P[i]-1)
    res += len(set(g) & set(e))

print(res)


### FIXED CODE ###

N, M = map(int, input().split())
P = list(map(int, input().split()))

class UnionFind:
    def __init__(self, n):
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)

res = 0
uf = UnionFind(N)
for _ in range(M):
    x, y = map(int, input().split())
    uf.union(x-1, y-1)

for i, e in enumerate(P):
    if uf.same(i, e-1):
        res += 1

print(res)
### BUGGY CODE ###

N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
j=0
for i in range(M):
    A[A.index(max(A[:j+1]))]=A[A.index(max(A[:j+1]))]//2
    j=j+1
    if j==440:
        A.sort(reverse=True)    
        j=0
print(sum(A))

### FIXED CODE ###

import heapq
N,M=map(int,input().split())
A=list(map(lambda x: x*(-1),list(map(int,input().split()))))
A.sort()
B=[]
for i in range(N):
    heapq.heappush(B,A[i])
for i in range(M):
    heapq.heappush(B,(((heapq.heappop(B))*(-1))//2)*(-1))
print((sum(B))*(-1))
### BUGGY CODE ###

import fractions
from functools import reduce
import copy
def gcd(numbers):
    return reduce(fractions.gcd, numbers)
a = int(input())
b = list(map(int, input().split()))
c = []
d = copy.deepcopy(b)
for i in range(a):
  b = copy.deepcopy(d)
  if a == 2:
    c.append(max(b))
  elif a >= 3:
    b.pop(i)
    c.append(gcd(b))
if a <= 3:
  print(max(c))
elif a > 3:
  if max(c) == 1:
    print(1)
  else:
    print(max(c))

### FIXED CODE ###

import fractions
from functools import reduce
n = int(input())
a = list(map(int,input().split()))
left = [0] * (n + 1)
right = [0] * (n + 1)
for i in range(n):
    left[i + 1] = (fractions.gcd(left[i],a[i]))
    right[n - i - 1] = (fractions.gcd(right[n - i],a[n - 1 - i]))
ans = 0
for i in range(n):
    ans = max(ans,fractions.gcd(left[i],right[i + 1]))
print(ans)
### BUGGY CODE ###

from collections import deque
import copy

def main():
    h,w = map(int, input().split())
    field = [[j == "#" for j in input()] for _ in range(h)]
    # dy = [1,-1,0,0]
    # dx = [0,0,1,-1]
    que = deque([(i, j) for i in range(h) for j in range(w) if field[i][j]])

    count = 0
    while True:
        count += 1
        nque = deque()
        while que:
            y,x = que.popleft()
            if x >0 and not field[y][x-1]:
                field[y][x-1] = True
                nque.append([y,x-1])
            if x <w-1 and not field[y][x+1]:
                field[y][x+1] = True
                nque.append([y,x+1])
            if y >0 and not field[y-1][x]:
                field[y-1][x] = True
                nque.append([y-1,x])
            if y < h-1 and not field[y+1][x]:
                field[y+1][x] = True
                nque.append([y+1,x])
            # for i in range(4):
            #     nh = h + dy[i]
            #     nw = w + dx[i]
            #     if (0<=nh<H) and (0<=nw<W):
            #         if field[nh][nw] == False:
            #             field[nh][nw] = True
            #             nqueue.append((nh,nw))
        if nque:
            que = copy.copy(nque)
        else:
            break
    print(count-1)
if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import deque
import copy

def main():
    h, w = map(int, input().split())
    a = [[j == "#" for j in input()] for _ in range(h)]


    # スタート地点をqueueに追加
    que = deque([(i, j) for i in range(h) for j in range(w) if a[i][j]])

    count = 0
    while True:
        count += 1
        nque = deque()
        while que:
            y, x = que.popleft()
            if x > 0 and not a[y][x-1]:
                a[y][x-1] = True
                nque.append((y,x-1))
            if x < w-1 and not a[y][x+1]:
                a[y][x+1] = True
                nque.append((y,x+1))
            if y > 0 and not a[y-1][x]:
                a[y-1][x] = True
                nque.append((y-1,x))
            if y < h-1 and not a[y+1][x]:
                a[y+1][x] = True
                nque.append((y+1,x))

        if nque:
            que = copy.copy(nque)
        else:
            break

    print(count - 1)

if __name__ == '__main__':
    main()