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

N,M = map(int, input().split())
if M == 0:
    print(-1)
    exit()
pqcs = [list(map(int, input().split())) for _ in range(M)]
c_max = max(list(map(lambda x: x[2],pqcs)))
node_num = (c_max+1)*N
unsearched_nodes = [c*10**6+s+1 for s in range(N) for c in range(c_max+1)]
#opt_nodes = [-1]*node_num
distance = {1:0}
#辺へ重み付け
edges = {}
for p,q,c in pqcs:
	edge = {}
	edge[c*10**6+q] = 0
	edge[p] = 0
	edges.setdefault(c*10**6+p, {})
	edges[c*10**6+p].update(edge)
	edge = {}
	edge[c*10**6+p] = 0
	edge[q] = 0
	edges.setdefault(c*10**6+q, {})
	edges[c*10**6+q].update(edge)
	edge = {}
	edge[c*10**6+p] = 1
	edges.setdefault(p, {})
	edges[p].update(edge)
	edge = {}
	edge[c*10**6+q] = 1
	edges.setdefault(q, {})
	edges[q].update(edge)

while not (distance.get(N)):
    temp_min_dist = float('inf')
    for unsearched_ind in unsearched_nodes:
    	if (distance.get(unsearched_ind) != None):
    		if temp_min_dist > distance[unsearched_ind]:
    			temp_min_dist = distance[unsearched_ind]
    			target_min_ind = unsearched_ind
    unsearched_nodes.remove(target_min_ind)
    target_node = edges[target_min_ind]
   
    for key, value in target_node.items():
    	distance.setdefault(key, float('inf'))
    	if distance[key] > distance[target_min_ind] + value:
    		distance[key] = distance[target_min_ind] + value
    	if key == N:
    		print(distance[N] if distance[N] != float('inf') else -1)
    		exit()

### FIXED CODE ###

from collections import deque
N, M = map(int, input().split())
F_C_of_S = [{} for i in range(N)]
#Companies of Station
C_of_S = {}

#def Union-find
parent = [-1]*M
def root(x):
	if (parent[x] < 0): return x
	else:
		parent[x] = y = root(parent[x])
		return y

def unite(x, y):
	px = root(x)
	py = root(y)
	if (px == py): return False
	if (parent[px] > parent[py]):
		px = root(y)
		py = root(x)
	parent[px] += parent[py]
	parent[py] = px
	return True


#Union-find
pqcs = []
for i in range(M):
	p, q, c = map(int, input().split())
	p -= 1; q -= 1;
	pqcs += [(p, q, c)]
	
	#The first
	if not c in F_C_of_S[p]: F_C_of_S[p][c] = i
	#else
	else: unite(F_C_of_S[p][c], i)
	C_of_S.setdefault(p, set()).add(c)
	
	#The first
	if not (c in F_C_of_S[q]):F_C_of_S[q][c] = i
	#else
	else: unite(F_C_of_S[q][c], i)
	C_of_S.setdefault(q, set()).add(c)

#stations of company
S_of_C = {}
for i in range(M):
	p, q, c = pqcs[i]
	c_set = S_of_C.setdefault(root(i), set())
	c_set.add(p)
	c_set.add(q)


Q = deque([(0, 0, 0)])
#cost to go to the stations from station_0
dist = [float('inf')]*N
dist[0] = 0

gdist = [float('inf')]*M

while Q:
	cost, v, flag = Q.popleft()
	
	if not (flag):#(flag == 0) then gdist_update
		if (dist[v] < cost) or (v not in C_of_S):
			continue
		for l in F_C_of_S[v].values():
			l = root(l)
			if (cost < gdist[l]):
				gdist[l] = cost
				Q.appendleft((cost, l, 1))
	
	else:#(flag == 1) then dist_update
		if (gdist[v] < cost) or (v not in S_of_C):
			continue
		for s in S_of_C[v]:
			if (cost+1 < dist[s]):
				dist[s] = cost+1
				Q.append((cost+1, s, 0))

print(dist[N - 1] if dist[N - 1] < float('inf') else -1)
### BUGGY CODE ###

n=int(input())
alpha=[chr(i) for i in range(97, 97+26)]
d={i:[] for i in alpha}
ans=0
for _ in range(n):
    s=input()
    if s not in d[s[0]]:
        d[s[0]].append(s)
        ans+=1
print(ans)

### FIXED CODE ###

n=int(input())
alpha=[chr(i) for i in range(97, 97+26)]
d={i:[{0},{0},{0},{0},{0},{0},{0},{0},{0},{0}] for i in alpha}
ans=0
for _ in range(n):
    s=input()
    if s not in d[s[0]][len(s)-1]:
        d[s[0]][len(s)-1]|={s}
        ans+=1
print(ans)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=1
for i in a:
  ans*=i
if ans>10**18:
  ans=-1
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=1
flag=True
if 0 in a:
  ans=0
  flag=False
if flag:
  for i in a:
    #print(ans)
    ans*=i
    if ans>10**18:
      ans=-1
      break
print(ans)
### BUGGY CODE ###

def main():
    import sys
    sys.setrecursionlimit(10 ** 6)
    from bisect import bisect_left,bisect
    n = int(input())
    x = list(map(int,input().split()))
    t = n.bit_length()

    kprv = [[10**10 for i in range(t+1)] for j in range(n)]
    for i in range(t):
        for j in range(n):
            if j + pow(2,i) > n-1:
                break
            kprv[j][i] = x[j+pow(2,i)] - x[j]

    L = int(input())
    q = int(input())

    for _ in range(q):
        a , b = map(lambda x:int(x)-1,input().split())
        cou = 0
        if a > b:
            a , b = b , a
        now = a
        while now < b:
            cou += 1
            p = L
            while True:
                nex = bisect(kprv[now],p)
                if nex == 0:
                    break
                else:
                    p -= kprv[now][nex-1]
                    now += pow(2,nex-1)
        print(cou)

main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)  # 変更
from bisect import bisect_left,bisect

n = int(input())
x = list(map(int,input().split()))
L = int(input())
t = n.bit_length()
prv = [n-1] * n
for i in range(n):
    prv[i] = bisect(x,x[i]+L) - 1
kprv = [prv]
S = prv
for i in range(t-1):
    kar = [n-1] * n
    for j in range(n):
        kar[j] = S[S[j]]
    kprv.append(kar)
    S = kar

q = int(input())
for _ in range(q):
    a , b = map(lambda x:int(x)-1,input().split())
    if a > b:
        a , b = b , a
    lef = 0
    rig = n-1
    while rig - lef > 1:
        mid = (rig+lef)//2
        p = mid.bit_length()
        now = a
        for i in range(p):
            if (mid>>i) & 1 == 1:
                now = kprv[i][now]
        if now >= b:
            rig = mid
        elif now < b:
            lef = mid
    print(rig)
### BUGGY CODE ###

from collections import defaultdict
import sys
input = sys.stdin.readline

N = int(input())
# 例外処理
if (N == 1):
    print("First")
    quit()

tree = defaultdict(list)
nodes_len = defaultdict(list)
for i in range(N):
    nodes_len[i+1] = [0, 0]

for i in range(N-1):
    a, b = tuple(map(int, input().split()))
    tree[a].append(b)
    tree[b].append(a)

while len(tree) > 1:
    del_nodes = []
    for from_node, to_nodes in list(tree.items()):
        # dictのサイズが1なら
        if len(to_nodes) == 1:
            to_node = to_nodes[0]

            # そのノードが持つ隣接ノード長を追加する
            nodes_len[to_node].append(nodes_len[from_node][0]+1)

            # 長さが2以上のみ保持する
            nodes_len[to_node].sort(reverse=True)
            nodes_len[to_node] = nodes_len[to_node][:2]

            # treeのto_nodeの部分から削除する
            tree[to_node].remove(from_node)

            # 自分を削除する
            del tree[from_node]

n = list(tree.keys())[0]
print("Second" if (nodes_len[n][0] + nodes_len[n][1]+1) % 3 == 2 else "First")


### FIXED CODE ###

from collections import defaultdict
import sys
input = sys.stdin.readline


N = int(input())
# 例外処理
if (N == 1):
    print("First")
    quit()

tree = defaultdict(set)
tree_main = defaultdict(set)
for i in range(N-1):
    a, b = tuple(map(int, input().split()))
    tree[a].add(b)
    tree[b].add(a)
    tree_main[a].add(b)
    tree_main[b].add(a)

def longest_path(tree, from_node=1):
    cnt = 1

    nearest_nodes = list(tree[from_node])
    while len(nearest_nodes) > 0:
        for one_step_node in nearest_nodes:
            for two_step_node in tree[one_step_node]:
                if two_step_node != from_node:
                    tree[two_step_node].remove(one_step_node)
                    tree[two_step_node].add(from_node)
                    tree[from_node].add(two_step_node)
            tree[from_node].remove(one_step_node)
        cnt += 1
        nearest_nodes = list(tree[from_node])

    return one_step_node, cnt


far, _ = longest_path(tree)
_, n = longest_path(tree_main, far)
print("Second" if n % 3 == 2 else "First")
### BUGGY CODE ###

n = int(input())
a = [[] for i in range(n)]

for i in range(n):
    v = list(map(int, input().split()))
    u = v[0] - 1
    for j in v[2:]:
        a[u].append(j-1)

d = [0] * n
isDiscovered = [False] * n

def bfs(x):
    for i in a[x]:
        if not isDiscovered[i]:
            isDiscovered [i] = True
            d[i] = d[x] + 1

bfs(0)
d_ = 1
isDiscovered [0] = True
while not(isDiscovered == [True] * n):
    for i in range(n):
        if d[i] is d_ :
            bfs(i)
    d_ += 1

for i in range(n):
    print(i+1, d[i])

### FIXED CODE ###

n = int(input())
a = [[] for i in range(n)]

for i in range(n):
    v = list(map(int, input().split()))
    u = v[0] - 1
    for j in v[2:]:
        a[u].append(j-1)

d = [-1] * n
isDiscovered = [False] * n

def bfs(x):
    for i in a[x]:
        if not isDiscovered[i]:
            isDiscovered [i] = True
            d[i] = d[x] + 1

d_ = 0
isDiscovered [0] = True
d[0] = 0
bfs(0)

flag = True
while flag:
    flag = False
    for i in range(n):
        if d[i] is d_ :
            flag = True
            bfs(i)
    d_ += 1

for i in range(n):
    print(i+1, d[i])
### BUGGY CODE ###

import sys
from collections import defaultdict
from collections import deque
import numpy as np
import heapq
from heapq import heappush, heappop
import itertools


#read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

N = int(input())

PATH = []
COLOR = [[None for _ in range(N+1)] for _ in range(N+1)]
#COLOR = defaultdict(int)
PT = [[] for _ in range(N+1)]
cmax = 1
for i in range(N-1):
    a, b = map(int, input().split())
    PATH.append((a, b))
    PT[a].append(b)
    PT[b].append(a)

    la = len(PT[a])
    lb = len(PT[b])

    l = la if la > lb else lb
    if l > cmax:
        cmax = l


q = deque([(1, 0)])
while(q):
    a, ca = q.popleft()
    bs = PT[a]

    c = list(range(1, cmax+1))
    for b in bs:
        if b > a:
            na = a
            nb = b
        else:
            na = b
            nb = a

        if COLOR[na][nb] == None:
            clr = c.pop()
            if clr == ca:
                clr = c.pop()

            COLOR[na][nb] = clr
            q.append((b, clr))

print(cmax)

clr = []
for a, b in PATH:
    clr.append(COLOR[a][b])

print("\n".join(map(str, clr)))


### FIXED CODE ###

import sys
from collections import defaultdict
from collections import deque
import numpy as np
import heapq
from heapq import heappush, heappop
import itertools


#read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

N = int(input())

PATH = []
#COLOR = [[None for _ in range(N+1)] for _ in range(N+1)]
COLOR = defaultdict(int)
PT = [[] for _ in range(N+1)]
cmax = 1
for i in range(N-1):
    a, b = map(int, input().split())
    PATH.append((a, b))
    PT[a].append(b)
    PT[b].append(a)

    '''
    la = len(PT[a])
    lb = len(PT[b])

    l = la if la > lb else lb
    if l > cmax:
        cmax = l
    '''

q = deque([(1, -1)])
while(q):
    a, ng = q.popleft()
    bs = PT[a]

    c = 1
    for b in bs:
        if b > a:
            na = a
            nb = b
        else:
            na = b
            nb = a

        cab = COLOR[(na, nb)]

        if cab == ng:
            continue

        if cab == 0:
            if c == ng:
                c += 1
            clr = c
            COLOR[(na, nb)] = clr
            q.append((b, clr))
            c += 1

print(max(COLOR.values()))

clr = []
for a, b in PATH:
    clr.append(COLOR[(a, b)])

print("\n".join(map(str, clr)))
### BUGGY CODE ###

def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    m = 10**9 + 7

    ans = 0
    for i in range(N-1):
        for j in range(i+1, N):
            ans += A[i] * A[j]
    ans = ans % m
    print(ans)

if __name__ == "__main__":
    resolve()

### FIXED CODE ###

def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    x = [0] * N
    tot = 0
    for i in range(N-1, 0, -1):
        tot += A[i]
        x[i] = tot

    ans = 0
    for i in range(N-1):
        ans += A[i] * x[i+1]
    ans = ans % (10**9 + 7)
    print(ans)

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

N = int(input())
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]
total =  0
for i in range(1,N+1):
    a = i * len(make_divisors(i))
    total += a
print(total)


### FIXED CODE ###

n=int(input())
ans=0
for i in range(1,n+1): #各iについて、i*(1～n//iまでの総和)を足し合わせればよい
 k=n//i
 ans+=i*(k*(k+1)//2)
print(ans)
### BUGGY CODE ###

import sys
h, w, n = [int(i) for i in sys.stdin.readline().split()]
m = 1000000007
fact = [1, 1]
for i in range(2, 200002):
    fact.append(fact[-1] * i)
inv = [pow(i, m - 2, m) for i in fact]
f = lambda i: fact[i[0] + i[1]] * inv[i[0]] * inv[i[1]] % m
dp = [0] * (n + 1)
p = [[int(i) - 1 for i in sys.stdin.readline().split()] for j in range(n)]
p = sorted(p + [[h - 1, w - 1]])
for i in range(n + 1):
    h1, w1 = p[i]
    tot = f([h1, w1])
    for j in range(i):
        if p[j][1] > w1:
            continue
        tot = (tot - dp[j] * f([h1 - p[j][0], w1 - p[j][1]]) % m) % m
    dp[i] = tot
print(dp[-1])

### FIXED CODE ###

import sys
h, w, n = [int(i) for i in sys.stdin.readline().split()]
m = 1000000007
fact = [1, 1]
for i in range(2, 200002):
    fact.append(fact[-1] * i % m)
inv = [pow(i, m - 2, m) for i in fact]
f = lambda i: fact[i[0] + i[1]] * inv[i[0]] * inv[i[1]] % m
dp = [0] * (n + 1)
p = [[int(i) - 1 for i in sys.stdin.readline().split()] for j in range(n)]
p = sorted(p + [[h - 1, w - 1]])
for i in range(n + 1):
    h1, w1 = p[i]
    tot = f([h1, w1])
    for j in range(i):
        if p[j][1] > w1:
            continue
        tot = (tot - dp[j] * f([h1 - p[j][0], w1 - p[j][1]]) % m) % m
    dp[i] = tot
print(dp[-1])
### BUGGY CODE ###

#https://atcoder.jp/contests/dp/tasks/dp_d
#2019-01-13
N, W = map(int, input().split())
w, v = [], []
for i in range(N):
    a, b = map(int, input().split())
    w += [a]
    v += [b]

DP = [0] * (W+1)
# i 円以下で買える商品の最大価値
for i in range(N):
    for weight in range(W,-1,-1):
        if weight - w[i] < 0 :continue
        DP[weight] = max(DP[weight], DP[weight - w[i]] +v[i])
print(DP[-1])

### FIXED CODE ###

#https://atcoder.jp/contests/dp/tasks/dp_d
#2019-01-13
N, W = map(int, input().split())
w, v = [], []
for i in range(N):
    a, b = map(int, input().split())
    w += [a]
    v += [b]

DP = [0] * (W+1)
# i 円以下で買える商品の最大価値
for i in range(N):
    for weight in range(W,-1,-1):
        if weight - w[i] < 0 :continue
        DP[weight] = max(DP[weight], DP[weight - w[i]] +v[i])
print(DP[-1])
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
INF = float("inf")

MOD = 2  # type: int


import math
import collections


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    return divisors


def solve(N: int, a: "List[int]"):
    b = [0]*N
    for i in range(N-1, -1, -1):
        if b[i] % MOD == a[i]:
            b[i] = 0
        else:
            b[i] = 1
            for d in make_divisors(i+1):
                if d != i+1:
                    b[d-1] += 1
    c = [i+1 for i, val in enumerate(b) if val % 2 > 0]
    print(len(c))
    if len(c) != 0:
        print(*c, sep=" ")
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, a)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
INF = float("inf")

MOD = 2  # type: int


import math
import collections


def solve(N: int, a: "List[int]"):
    b = [0]*N
    for i in range(N-1, -1, -1):
        tmp = 0
        for j in range(2, N//(i+1)+1):
            tmp += b[j*(i+1)-1]
        if tmp % MOD == a[i]:
            b[i] = 0
        else:
            b[i] = 1

    c = [i+1 for i, val in enumerate(b) if val % 2 > 0]
    print(len(c))
    if len(c) != 0:
        print(*c, sep=" ")
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, a)


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

n, m = map(int, input().split())
ab = []
for i in range(m):
    ab.append(list(map(int, input().split())))

node = [[] for i in range(n)]
for i in range(m):
    node[ab[i][0] - 1].append(ab[i][1])
    node[ab[i][1] - 1].append(ab[i][0])

# print(node)
node_dic = [[] for i in range(n)]
now = [1]
while True:
    flag = True
    next_node = []
    for i in range(len(now)):
        # print('now: {}'.format(now))
        next_node.append(node[now[i] - 1])
        next_node_element = node[now[i] - 1]
        
        for j in range(len(next_node_element)):
            if not node_dic[next_node_element[j] - 1]:
                node_dic[next_node_element[j] - 1].append(now[i])
                flag = False
    next_node = sum(next_node, [])
    # print('next_node: {}'.format(next_node))
    # print(node_dic)
    now = next_node
    if flag:
        break

for i in range(n):
    if i == 0:
        print('Yes')
        continue
    print(node_dic[i][0])

### FIXED CODE ###

n, m = map(int, input().split())
ab = []
for i in range(m):
    ab.append(list(map(int, input().split())))

node = [[] for i in range(n)]
for i in range(m):
    node[ab[i][0] - 1].append(ab[i][1])
    node[ab[i][1] - 1].append(ab[i][0])

# print(node)
node_dic = [[] for i in range(n)]
now = [1]
while True:
    # print('now:{}'.format(now))
    flag = True
    next_node = []
    for i in range(len(now)):
        next_node_element = node[now[i] - 1]
        
        for j in range(len(next_node_element)):
            if not node_dic[next_node_element[j] - 1]:
                next_node.append(next_node_element[j])
                node_dic[next_node_element[j] - 1].append(now[i])
                flag = False
    # next_node = sum(next_node, [])
    # print('next_node: {}'.format(next_node))
    # print(node_dic)
    # print('next_node:{}'.format(next_node))
    now = []
    now = next_node
    if flag:
        break

for i in range(n):
    if i == 0:
        print('Yes')
        continue
    print(node_dic[i][0])
### BUGGY CODE ###

import sys
import heapq
input = sys.stdin.readline

def solve(N, K, a, f, num):
    cost = 0
    for i in range(N):
        cost += max(0, a[i] - (num//f[i]))
        if cost > K:
            return False
    return True


def main():
    N, K = map(int, input().split())
    a = sorted(list(map(int, input().split())))
    f = sorted(list(map(int, input().split())), reverse=True)

    l, r = 0, int(1e12)
    while l != r:
        # print(l, r)
        p = (l + r) // 2
        tmp = solve(N, K, a, f, p)
        # print(l, p, r, tmp)
        if tmp:
            r = p
        else:
            l = p + 1
        # break
    
    print(l)


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
import numpy as np
input = sys.stdin.readline

def main():
    N, K = map(int, input().split())
    a = np.array(sorted(list(map(int, input().split()))))
    f = np.array(sorted(list(map(int, input().split())), reverse=True))

    Asum = a.sum()

    l, r = 0, int(1e13)
    while l != r:
        p = (l + r) // 2
        tmp = Asum - np.minimum(a, p//f).sum() <= K
        # print(p, tmp)
        if tmp:
            r = p
        else:
            l = p + 1
    
    print(l)


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

N = int(input())

def make_divisors(n):
    divisors = 0
    for i in range(1, int(pow(n,0.5)+1)):
        if n%i==0:
            divisors += 1
            if i!=n//i: 
                divisors += 1
    return divisors

ans = 0
for i in range(1, N+1):
    ans += i * make_divisors(i)
print(ans)

### FIXED CODE ###

# D - Sum of Divisors

N = int(input())

ans = 0
D = [0] * (N+1)
for i in range(1, N+1):
    for j in range(i, N+1, i):
        D[j] += 1
    ans += i*D[i]
print(ans)
### BUGGY CODE ###

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

max_val = 0
for n in range(len(H) - 1):
    index = n

    tmp = 0
    while (index < len(H) - 1):
        if (H[index + 1] <= H[index]):
            tmp += 1
            index += 1
        else:
            index = len(H)

    if (tmp > max_val):
        max_val = tmp

print(max_val)

### FIXED CODE ###

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

max_val = 0

index = 0
while(index < len(H) - 1):
    index_boolean = index
    tmp = 0
    while (index_boolean < len(H) - 1):
        if (H[index + 1] <= H[index]):
            tmp += 1
            index += 1
            index_boolean += 1
        else:
            index_boolean = len(H)
            index += 1

    if (tmp > max_val):
        max_val = tmp

print(max_val)
### BUGGY CODE ###

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

N = int(input())
A = [i for i in map(int,input().split())]
g = []
for i in range(N):
    ans = 0
    for j in range(N):
        if ans == 0 and i != j:
            ans = A[j]
            continue
        if i != j:
            ans = gcd(A[j],ans)
    g.append(ans)
print(max(g))

### FIXED CODE ###

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

N = int(input())
A = [i for i in map(int,input().split())]
L = [0]
R = [0]
for i in range(N):
    L.append(gcd(L[-1],A[i]))
for i in range(N-1,-1,-1):
    R.append(gcd(R[-1],A[i]))
R.reverse()
g = []
for i in range(N):
    g.append(gcd(L[i],R[i+1]))
print(max(g))
### BUGGY CODE ###

# coding : utf-8

import numpy as np

N = int(input())

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


count = 0

#dist = [0 for i in range(N)]
dist = np.zeros(N)
suml = sum(A)

for i in range(N):
	dist += A[i]
	#print(dist)
	count += sum(dist[:i+1]==0)

#print(dist)

print(count)

### FIXED CODE ###

# coding : utf-8
 
import numpy as np
 
N = int(input())
 
A = [int(i) for i in input().split()]

S = [0 for i in range(N+1)]

for i in range(N):
	S[i+1] = S[i] + A[i]

S = sorted(S)
cnt = 0
block = 1
s = S[0]
for i in range(1,N+1):
	if s == S[i]:
		cnt += block
		block += 1
	else:
		s = S[i]
		block = 1

#print(S)
print(cnt)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = [0]*N
i=0
while i<N:
  j=0
  while j<N:
    if A[j]==i+1:
      ans[i]=j+1
    j+=1
  i+=1
print(*ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
Ad = {}
ans = [0]*N
i=0
for i in range(len(A)):
  Ad[i] = A[i]

i=0
for k, v in sorted(Ad.items(), key=lambda x: x[1]):
  ans[i] = k+1
  i+=1

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

import bisect

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

construction = [list(map(int, input().rstrip().split(' '))) for _ in range(N)]
D = [int(input()) for _ in range(Q)]
construction = sorted(construction, key=lambda x: -x[2])

dist = [-1] * Q
for c in construction:
    i1 = bisect.bisect_left(D, c[0] - c[2])
    i2 = bisect.bisect_left(D, c[1] - c[2])
    for i in range(i1, i2):
        dist[i] = c[2]
    
for d in dist:
    print(d)

### FIXED CODE ###

import sys
import bisect
input=sys.stdin.readline

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

construction = [list(map(int, input().split(' '))) for _ in range(N)]
D = [int(input()) for _ in range(Q)]
construction = sorted(construction, key=lambda x: x[2])

dist = [-1] * Q
jump = [-1] * Q
indices = list(range(Q))
for s, t, x in construction:
    i1 = bisect.bisect_left(D, s-x)
    i2 = bisect.bisect_left(D, t-x)
    i = i1
    while i < i2:
        k = jump[i]
        if k != -1:
            i = k
        else:
            jump[i] = i2
            dist[i] = x
            i += 1
    
for d in dist:
    print(d)