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

import itertools,copy

from typing import re
T = input()
TC = list(T)
N = [i for i, x in enumerate(TC) if x == '?']
B = list(itertools.product(['P','D'], repeat=len(N)))
point = [0]*len(B)
strs = [0]*len(B)
for b,i in zip(B,range(len(B))):
    TC = list(T)
    for n,j in zip(N,range(len(N))):
        TC[n] = b[j]
    TC = ''.join(TC)
    strs[i] = TC
    point[i] = TC.count('PD') + TC.count('D')
maxin = max(point)

print(strs[point.index(maxin)])


### FIXED CODE ###

#BBBBBBBBBBB

import sys
import math
import itertools
import collections
import heapq
import numpy as np

rl = sys.stdin.readline

t = rl()
li = []
for i in range(len(t)):
    if t[i] == '?':
        li.append('D')
    else:
        li.append(t[i])
print(''.join(li))
### BUGGY CODE ###

n = int(input())
a = []
b = []
for i in range(n):
    c,d = map(int,input().split())
    a.append(c)
    b.append(d)
t = 0
while(1):
    if len(a)==0:
        break
    maxa = -1
    ai = -1
    if b.count(max(b)) == len(b):
        ai = a.index(max(a))
    else:
        for k in [i for i, x in enumerate(b) if x == max(b)]:
            if maxa <= a[k]:
                maxa = a[k]
                ai = k
    t += a[ai]
    del a[ai]
    del b[ai]

    if len(b)==0:
        break
    maxb = -1
    bi = -1
    if a.count(max(a)) == len(a):
        bi = b.index(max(b))
    else:
        for k in [i for i, x in enumerate(a) if x == max(a)]:
            if maxb <= b[k]:
                maxb = b[k]
                bi = k
    t -= b[bi]
    del a[bi]
    del b[bi]
print(t)

### FIXED CODE ###

n = int(input())
ab = []
x = 0
for i in range(n):
  a,b = map(int,input().split())
  x -= b
  ab.append(a+b)
ab.sort()
ab.reverse()
for i in range(n):
  if i%2==0:
      x+=ab[i]
print(x)
### BUGGY CODE ###

import bisect

n = int(input())
nums = [int(input()) for _ in range(n)]

colors = []
min_val = 10 ** 10
for num in nums:
	if num <= min_val:
		colors.insert(0, num)
		min_val = num
	else:
		idx_r = bisect.bisect_right(colors, num - 0.5) - 1
		colors[idx_r] = num
		min_val = max(colors[0], min_val)

print(len(colors))


### FIXED CODE ###

import bisect

n = int(input())
nums = [-int(input()) for _ in range(n)]

colors = []
max_val = -1 * (10 ** 10)
for num in nums:
	if num >= max_val:
		colors.append(num)
		max_val = num
	else:
		idx_r = bisect.bisect_right(colors, num)
		colors[idx_r] = num
		max_val = min(colors[-1], max_val)

print(len(colors))
### BUGGY CODE ###

from sys import stdin
from sys import setrecursionlimit
from itertools import accumulate

setrecursionlimit(10 ** 7)

n = int(stdin.readline().rstrip())
a = list(map(int,stdin.readline().rstrip().split()))
point = 0

for i in range(2,n):
    for j in range(n-i):
        if a[j]+a[j+i] == i:
            point += 1

print(point)

### FIXED CODE ###

from sys import stdin
from sys import setrecursionlimit

setrecursionlimit(10 ** 7)

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

dic = {}
point = 0

for i,j in enumerate(a):
    if i+j in dic:
        dic[i+j] += 1
    else:
        dic[i+j] = 1

for i,j in enumerate(a):
    if i-j in dic:
        point += dic[i-j]

print(point)
### BUGGY CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))
h.insert(0, float("inf"))

dp = [float("inf")] * (N + 1)
dp[1] = 0

for i in range(2, N + 1):
    for k in range(1, K + 1):
        if i - k >= 0:
            dp[i] = min(dp[i], dp[i - k] + abs(h[i - k] - h[i]))
        else:
            break

print(dp[N])

### FIXED CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))
h.insert(0, float("inf"))

dp = [float("inf")] * (N + 1)
dp[1] = 0

for i in range(2, N + 1):
    for k in range(1, K + 1):
        if i - k >= 0:
            dp[i] = min(dp[i], dp[i - k] + abs(h[i - k] - h[i]))
        else:
            break

print(dp[N])
### BUGGY CODE ###

N = int(input())
power = 1
for i in range(1, N + 1):
    power *= i

print(power % (10 ** 9 + 7))


### FIXED CODE ###

N = int(input())
power = 1
for i in range(1, N + 1):
    power = (i*power)%(10**9+7)

print(power)
### BUGGY CODE ###

S = input()
slist = S.split("LR")
res = [[0] * len(s) for s in slist]
for i in range(len(slist)):
  if i < len(slist) - 1:
    slist[i] = slist[i] + "L"
    res[i].append(0)
    slist[i + 1] = "R" + slist[i + 1]
    res[i + 1].append(0)
  Rc = slist[i].count("R")
  Lc = slist[i].count("L")
  #print(slist[i], Rc, Lc)
  res[i][Rc - 1] = Lc // 2 + (Rc - Rc // 2)
  res[i][Rc] = Rc // 2 + (Lc - Lc // 2)
res2 = ""
#print(res)
for i in range(len(slist)):
  #print(res[i])
  res2 = res2 + " ".join(map(str, res[i]))
  if i < len(slist) -1:
    res2 = res2 + " "
print(res2)

### FIXED CODE ###

S = input()
slist = S.split("LR")
res = [["0"] * len(s) for s in slist]
for i in range(len(slist)):
  if i < len(slist) - 1:
    slist[i] = slist[i] + "L"
    res[i].append("0")
    slist[i + 1] = "R" + slist[i + 1]
    res[i + 1].append("0")
  Rc = slist[i].count("R")
  Lc = slist[i].count("L")
  #print(slist[i], Rc, Lc)
  res[i][Rc - 1] = str(Lc // 2 + (Rc - Rc // 2))
  res[i][Rc] = str(Rc // 2 + (Lc - Lc // 2))
res2 = ""
#print(res)
for i in range(len(slist)):
  #print(res[i])
  res2 = res2 + " ".join(res[i])
  if i < len(slist) -1:
    res2 = res2 + " "
print(res2)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
from itertools import chain
import numpy as np
h,w=map(int,input().split())
s=[list(input())for i in range(h)]
a=[[float("inf")]*w for i in range(h)]
b=[[False]*w for i in range(h)]
d=set()
def f(x,y,t):
    if 0<=x<h and 0<=y<w:
        if s[x][y]=="#":
            if b[x][y]==False:
                a[x][y]=0
                b[x][y]=True
                f(x,y+1,1)
                f(x+1,y,1)
                f(x-1,y,1)
                f(x,y-1,1)
        else:
            if a[x][y]>t:
                a[x][y]=t
                f(x,y+1,t+1)
                f(x+1,y,t+1)
                f(x-1,y,t+1)
                f(x,y-1,t+1)
i,j=divmod(list(chain(*s)).index("#"), len(s[0]))
f(i,j,0)
print(np.array(a).max())

### FIXED CODE ###

import numpy as np
from scipy.ndimage import distance_transform_cdt as d
h,w=map(int,input().split())
s=[[1 if i=="." else 0 for i in input()]for i in range(h)]
a=d(s,metric='taxicab')
print(a.max())
### BUGGY CODE ###

import collections

def bfs(tree, s, distance):
    queue = [s]
    distance[s] = 0

    while queue:
        v = queue.pop(0)
        v_c = distance[v]
        for node, cost in tree[v]:
            if distance[node] == -1:
                distance[node] = v_c + cost
                queue.append(node)

N = int(input())

Tree = collections.defaultdict(list)

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

q, k = map(int, input().split())

distance = collections.defaultdict(lambda : -1)
bfs(Tree, k, distance)

for i in range(q):
    x, y = map(int, input().split())
    print(distance[x] + distance[y])


### FIXED CODE ###

import sys
import collections

sys.setrecursionlimit(int(1e7))

def dfs(node, parent, distance):
    depth[node] = distance
    for next_node, cost in Tree[node]:
        if next_node != parent:
            dfs(next_node, node, distance + cost)

N = int(input())

Tree = collections.defaultdict(list)

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

q, k = map(int, input().split())

depth = {}
dfs(k, -1, 0)

for i in range(q):
    x, y = map(int, input().split())
    print(depth[x] + depth[y])
### BUGGY CODE ###

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

    dp = [-1] * (W + 1)
    dp[0] = 0

    for _ in range(N):
        w, v = map(int, input().split())
        for i in range(W - w, -1, -1):
            pre_v = dp[i]
            if pre_v == -1: continue
            dp[i + w] = max(dp[i + w], pre_v + v)

    print(max(dp))

main()


### FIXED CODE ###

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

    dp = [-1] * (W + 1)
    dp[0] = 0

    for _ in range(N):
        w, v = map(int, input().split())
        for i in range(W - w, -1, -1):
            if dp[i] != -1 and dp[i + w] < dp[i] + v:
                dp[i + w] = dp[i] + v

    print(max(dp))

main()
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
from heapq import heappush, heappop, heapify
from bisect import bisect_left, bisect_right

N,Q=map(int, sys.stdin.readline().split())

S=[]
hq=[]	#x, xが答えになる開始時間, xが答えになる終了時間
for _ in range(N):
	s,t,x=map(int, sys.stdin.readline().split())
	heappush( hq, (x, max(0,s-x) , max(0,t-1-x)) )

D=[ int(sys.stdin.readline().strip()) for _ in range(Q) ]
ANS=[ float("inf") for _ in range(Q) ]

while hq:
	x,s,t=heappop(hq)

	start=bisect_left(D,s)
	end=bisect_right(D,t)

	for i in range(start,end):
		ANS[i]=min(ANS[i],x)


for x in ANS:
	if x==float("inf"):
		print -1
	else:
		print x


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right

N,Q=map(int, sys.stdin.readline().split())

S=[]
event=[]	#x, s, t
for _ in range(N):
	s,t,x=map(int, sys.stdin.readline().split())
	heappush( event, (x, max(0,s-x) , max(0,t-1-x)) )


D=[ int(sys.stdin.readline().strip()) for _ in range(Q) ]
D.sort()
ans=[ float("inf") for _ in range(Q) ]

Next=[ i+1 for i in range(Q) ]	#Next


while event:
	x,s,t=heappop(event)
	start=bisect_left(D,s)
	end=bisect_right(D,t)

	i=start
	while i<end:
		ans[i]=min(ans[i],x)
		next=Next[i]
		Next[i]=end
		i=next

for x in ans:
	if x==float("inf"):
		print -1
	else:
		print x
### BUGGY CODE ###

N,Y = map(int,input().split())
count = 0
for x in range(N+1):
    i = 10000 * x
    for y in range(N-x+1):
        j = 5000 * y
        for z in range(N-x-y+1):
            k = 1000 * z
            if(i+j+k == Y and x+y+z == N):
                count = 1
                f_x=x
                f_y=y
                f_z=z
                
if(count == 1):
    print(str(f_x)+" "+str(f_y)+" "+str(f_z))
if(count == 0):
    print("-1 -1 -1")

### FIXED CODE ###

N,Y = map(int,input().split())
count = 0
for x in range(N+1):
    i = 10000 * x
    for y in range(N-x+1):
        j = 5000 * y
        if((Y-i-j)/1000+x+y == N and i+j+(N-x-y)*1000 == Y):
            count = 1
            z = N - x - y
            f_x=x
            f_y=y
            f_z=z
                
if(count == 1):
    print(str(f_x)+" "+str(f_y)+" "+str(f_z))
if(count == 0):
    print("-1 -1 -1")
### BUGGY CODE ###

s = input().split()
n = int(s[0])
k = int(s[1])

p_n = input().split()

up_to = n - k + 1

result = 0.0

for i in range(up_to):
    sum_ex = 0.0
    for j in range(i,i+k):
        #print(p_n[j])
        sum_ex += (1 + int(p_n[j]))/2
    
    #print(sum_ex)
    if(result < sum_ex):
        result = sum_ex


print('{0:.6f}'.format(result))

### FIXED CODE ###

n,k = map(int,input().split())

pi = [0 for _ in range(n)]
si = [0 for _ in range(n)]

pi = [int(s) for s in input().split()]
pi = [(1+s)/2 for s in pi]

si[0] = pi[0]
for i in range(1,n):
    si[i] = si[i-1] + pi[i]

#print(pi)
#print(si)
#print(si[2]-si[0])

ans = 0
if not (n==k):
    for i in range(n-k):
        ans = max(si[i+k]-si[i],ans)
else:
    ans = si[n-1]

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

A, B = map(int, input().split())
for K in range(10 ** 9):
    if abs(A - K) == abs(B - K):
        print(K)
    else:
        print("IMPOSSIBLE")


### FIXED CODE ###

A, B = map(int, input().split())
if (A + B) % 2 != 0:
    print("IMPOSSIBLE")
else:
    print((A + B) // 2)
### BUGGY CODE ###

n = int(input())
p = list(map(int, input().split()))
cnt = 0
for i in range(n):
    for j in range(i + 1):
        if p[i] > p[j]:
            break
    else:
        cnt += 1
print(cnt)


### FIXED CODE ###

n = int(input())
p = list(map(int, input().split()))
cnt = 0
m = float('inf')
for i in range(n):
    m = min(p[i], m)
    if p[i] <= m:
        cnt += 1
print(cnt)
### BUGGY CODE ###

N=int(input())
S=input()
w=ans=9**9
for i in range(N):
    e=S[:i].count("W")
    w=S[i:].count("E")
    ans=min(ans,e+w)
    if w==0:break
print(ans)


### FIXED CODE ###

N=int(input())
S=input()
e=0
ans=w=S.count("E")
for i in S:
    if i=="E":w-=1
    else: e+=1
    ans=min(ans,e+w)
print(ans)
### BUGGY CODE ###

n, tracks = list(map(int, input().split()))
loads = []
for _ in range(n):
    loads.append(int(input()))

# print(loads)
slices = []
min_load = [99999999999999]


def slicing(rest, s):
    if not rest:
        # slices.append(s+[(len(s) and s[-1][1], len(loads))])
        s += [(len(s) and s[-1][1], len(loads))]
        min_load[0] = min(min_load[0], max(sum(loads[l[0]: l[1]]) for l in s))
        return

    first = len(s) and s[-1][1]
    for s1 in range(first+1, len(loads)-rest+1):
        total = sum(loads[first: s1])
        if total < min_load[0]:
            slicing(rest-1, s+[(first, s1)])


slicing(tracks-1, [])
print(min_load.pop())


### FIXED CODE ###

n, k = list(map(int, input().split()))


def check(p):
    i = 0
    for j in range(k):
        s = 0
        while s + T[i] <= p:
            s += T[i]
            i += 1
            if i == n:
                return n
    return i


def solve():
    left = 0
    right = 100000 * 10000
    while right - left > 1:
        mid = (left + right) // 2
        v = check(mid)
        if v >= n:
            right = mid
        else:
            left = mid
    return right


T = []
for _ in range(n):
    T.append(int(input()))
ans = solve()
print(ans)
### BUGGY CODE ###

N=int(input())
S=input()
ans=0
for j in range(1,N-1):
  s1=S[j]
  for i in range(0,j):
    s2=S[i]
    if s1==s2: continue
    jmi=j-i
    for k in range(j+1,N):
      if k-j==jmi: continue
      s3=S[k]
      if s1!=s3 and s2!=s3:
        ans+=1
print(ans)

### FIXED CODE ###

N=int(input())
S=input()
ans=0
RGB_dict={'R':0,'G':0,'B':0}
for s in S:
  RGB_dict[s]+=1
ans=RGB_dict['R']*RGB_dict['G']*RGB_dict['B']

for i in range(N-1):
  s1=S[i]
  for j in range(i+1,N):
    s2=S[j]
    if s1==s2: continue
    k=j+(j-i)
    if k>N-1: continue
    #print(k)
    s3=S[k]
    if s1!=s3 and s2!=s3:
      ans-=1
print(ans)
### BUGGY CODE ###

a = int(input())
b = list(map(int, input().split()))
b.sort()
r = 0
for i in range(a-2):
    for j in range(i+1, a-1):
        for k in range(1, a - j):
            if b[j + k] >= b[i] + b[j]:
                r += k - 1
                break
            if b[a - k] < b[i] + b[j]:
                r += a - k - j
                break
print(r)


### FIXED CODE ###

def binsearch(l, r, fn, i, j):
    while r - l > 1:
        m = (l + r) // 2
        if fn(m, i, j):
            l = m
        else:
            r = m
    return l

def main():
    N = int(input())
    L = list(map(int, input().split()))
    L.sort()
    def fn(m, i, j):
        a = L[m]
        b = L[i]
        c = L[j]
        if a < b + c and b < c + a and c < a + b:
            return True
        return False
    r = 0
    for i in range(N-2):
        for j in range(i+1, N-1):
            if fn(j+1, i, j):
                r += binsearch(j+1, N, fn, i, j) - j
    return r
print(main())
### BUGGY CODE ###

def main():
    n = input()
    a = input().split(" ")
    r = ""
    for i in range(len(a)):
        r += str(a.index(str(i+1)) + 1) + " "
    print(r[:-1])
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
#input = sys.stdin.readline

def main():
    n = input()
    a = input().split(" ")
    # r = ""
    # for i in range(int(n)):
    #     r += str(a.index(str(i+1)) + 1) + " "
    # print(r[:-1])
    a = [(a[i],str(i+1)) for i in range(len(a))]
    a = list(map(lambda x:x[1],sorted(a,key=lambda x:int(x[0]))))
    print(" ".join(a))

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

import sys
from collections import deque
def input():
	return sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**6)

n, m = map(int, input().split())
adj = [[] for _ in range(n)]
eff = [0 for _ in range(n)]
edges = []
is_reversed = [0 for _ in range(m)]

for i in range(m):
	a, b = map(int, input().split())
	adj[a-1].append([b-1, i])
	adj[b-1].append([a-1, i])
	edges.append([a, b])
	eff[a-1] += 1

if m%2 == 1:
	print(-1)
	sys.exit()

def bfs(start):
	prev = [(-1, -1) for _ in range(n)]
	prev[start] = (start, -1)
	q = deque([start])
	while q:
		l = q.pop()
		if l != start and eff[l]%2 == 1:
			eff[start] += 1
			eff[l] += 1
			break
		for v, i in adj[l]:
			if prev[v][0] < 0:
				prev[v] = (l, i)
				q.appendleft(v)
	s, t = l, prev[l][1]
	while t >= 0:
		is_reversed[t] ^= 1
		s = prev[s][0]
		t = prev[s][1]

odd = [i for i in range(n) if eff[i]%2 == 1]
for o in odd:
	if eff[o]%2 == 1:
		bfs(o)

for i in range(m):
	if is_reversed[i]:
		print(*edges[i][::-1])
	else:
		print(*edges[i])

### FIXED CODE ###

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

n, m = map(int, input().split())
adj = [[] for _ in range(n)]
eff = [0 for _ in range(n)]
edges = []
visited = [False for _ in range(n)]
is_reversed = [0 for _ in range(m)]

for i in range(m):
	a, b = map(int, input().split())
	adj[a-1].append([b-1, i])
	adj[b-1].append([a-1, i])
	edges.append([a, b])
	eff[a-1] ^= 1

if m%2 == 1:
	print(-1)
	sys.exit()

def dfs(x, e):
	for v, i in adj[x]:
		if not visited[v]:
			visited[v] = True
			dfs(v, i)
	if e == -1:
		return
	else:
		if eff[x] == 1:
			is_reversed[e] ^= 1
			eff[x] ^= 1
			eff[(edges[e][0]-1) * (edges[e][1]-1) // x] ^= 1
		return

visited[0] = True
dfs(0, -1)
for i in range(m):
	if is_reversed[i]:
		print(*edges[i][::-1])
	else:
		print(*edges[i])
### BUGGY CODE ###

MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)
from collections import deque

def main():
    h,w = map(int,input().split())
    grid = [input() for _ in range(h)]
    dist = [[-1] * w for _ in range(h)]
    
    q = deque()
    for i in range(h):
        for j in range(w):
            if grid[i][j] == '#':
                q.append((i,j))
                dist[i][j] = 0
    
    ans = 0
    while q:
        i,j = q.popleft()
        for k in range(4):
            y = i + dy[k]
            x = j + dx[k]
            if 0 <= y < h and 0 <= x < w and dist[y][x] == -1:
                dist[y][x] = dist[i][j] + 1
                ans = max(ans,dist[y][x])
                q.append((y,x))
    
    print(ans)

if __name__ =='__main__':
    main()  


### FIXED CODE ###

MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)
from collections import deque

def main():
    h,w = map(int,input().split())
    grid = [input() for _ in range(h)]
    dist = [[-1] * w for _ in range(h)]
    
    q = deque()
    for i in range(h):
        for j in range(w):
            if grid[i][j] == '#':
                q.append((i,j))
                dist[i][j] = 0
    
    ans = 0
    while q:
        i,j = q.popleft()
        for k in range(4):
            y = i + dy[k]
            x = j + dx[k]
            if 0 <= y < h and 0 <= x < w and dist[y][x] == -1:
                dist[y][x] = dist[i][j] + 1
                ans = max(ans,dist[y][x])
                q.append((y,x))
    
    print(ans)

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

#!/usr/bin/env python
# -*- coding: utf-8 -*-
n=int(input())
a=[int(x) for x in input().split()]
mod=10**9+7
lcm=1
from fractions import gcd
for ai in a:
    lcm=ai*lcm//gcd(ai,lcm)
ans=0
for ai in a:
    ans+=lcm//ai
    ans%=mod
print(ans)

### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
n=int(input())
a=[int(x) for x in input().split()]
mod=10**9+7
lcm=1
from fractions import gcd
for ai in a:
    lcm=ai*lcm//gcd(ai,lcm)
ans=0
for ai in a:
    ans+=lcm//ai
print(ans%mod)
### BUGGY CODE ###

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

	def getsum(self, k):
		ret = 0
		while k:
			ret += self.bit[k]
			k -= k & -k
		return ret

	def p_sum(self, i, j):
		return self.getsum(j) - self.getsum(i - 1)

	def add(self, k, x):
		while k <= self.n:
			self.bit[k] += x
			k += k & -k

	def bisect(self, x):
		i, m = 0, 1 << (self.n.bit_length() - 1)
		while m:
			t = i + m
			if t < self.n and self.bit[t] < x:
				i = t
				x -= self.bit[i]
			m //= 2
		return i + 1

import sys
input = sys.stdin.buffer.readline
from operator import itemgetter as get
def main():
	n, q = map(int, input().split())
	event = []
	Xs = []
	for _ in range(n):
		s, t, x = map(int, input().split())
		event.append((-2, s - x, x))
		event.append((-1, t - x, x))
		Xs.append(x)
	Xs.sort()
	for _ in range(q):
		d = int(input())
		event.append((0, d, None))
	event.sort(key=get(1))
	x_to_i = {x: i for i, x in enumerate(Xs)}
	bit = BIT(n)
	any = 0
	ans = []
	for flg, time, x in event:
		if flg == -2:
			bit.add(x_to_i[x], 1)
			any += 1
		elif flg == -1:
			bit.add(x_to_i[x], -1)
			any -= 1
		else:
			if not any:
				ans.append(-1)
			else:
				ans.append(Xs[bit.bisect(1)])
	print("\n".join(map(str, ans)))

if __name__ == '__main__':
	main()

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
from operator import itemgetter as get
from heapq import *


def main():
	n, q = map(int, input().split())
	event = []
	Xs = []
	for _ in range(n):
		s, t, x = map(int, input().split())
		event.append((-2, s - x, x))
		event.append((-1, t - x, x))
		Xs.append(x)
	for _ in range(q):
		d = int(input())
		event.append((0, d, None))
	event.sort(key=get(1))
	active = {x: 0 for x in Xs}
	candidate = []
	ans = []
	for flg, time, x in event:
		if flg == -2:
			active[x] = 1
			heappush(candidate, x)
		elif flg == -1:
			active[x] = 0
		else:
			res = -1
			while candidate:
				c = heappop(candidate)
				if active[c]:
					heappush(candidate, c)
					res = c
					break
			ans.append(res)
	print("\n".join(map(str, ans)))


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

from functools import reduce

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)
'''
def lcm(a, b):
    return a * b // gcd(a, b)
'''
n = int(input())
a_list = list(map(int, input().split()))
remove_list = a_list[:]
max_list = []

for i in range(len(a_list)):
    remove_list.pop(i)
    max_list.append(reduce(gcd, remove_list))
    remove_list = a_list[:]

print(reduce(max, max_list))


### FIXED CODE ###

from functools import reduce


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


def lcm(a, b):
    return a * b // gcd(a, b)


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

l = [0 for i in range(n)]
for i in range(0, n - 1, 1):
    l[i + 1] = gcd(l[i], a[i])

r = [0 for i in range(n)]
for i in range(n - 2, -1, -1):
    r[i] = gcd(r[i + 1], a[i + 1])

m = [gcd(l[i], r[i]) for i in range(n)]

print(reduce(max, m))