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

N = int(input())
import sys
sys.setrecursionlimit(1000000)
MOD = 10**9+7
E = {}
for i in range(0,N+1):
    E[i] = []
for i in range(N-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    E[a].append(b)
    E[b].append(a)

dp = [ [0 for i in range(2)] for j in range(100100)]

def dfs(c,p):
    dp[c][0],dp[c][1] = 1,1
    for to in E[c]:
        if to != p:
            dfs(to,c)
            dp[c][0] *= dp[to][0] + dp[to][1]
            dp[c][1] *= dp[to][0]


dfs(0,-1)

ans = (dp[0][0] + dp[0][1]) % MOD
print(ans)


### FIXED CODE ###

from heapq import heappush, heappop
import collections
import math
import heapq
from collections import defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7
inf = float("inf")


def main():
    N = int(input())
    E = {}
    for i in range(0, N+1):
        E[i] = []
    for i in range(N-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        E[a].append(b)
        E[b].append(a)

    dp = [[0 for i in range(2)] for j in range(100100)]

    def dfs(c, p):
        dp[c][0], dp[c][1] = 1, 1
        for to in E[c]:
            if to != p:
                dfs(to, c)
                dp[c][0] *= dp[to][0] + dp[to][1]
                dp[c][1] *= dp[to][0]

    dfs(0, -1)

    ans = (dp[0][0] + dp[0][1]) % MOD
    print(ans)


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

import sys
import numpy as np
sys.setrecursionlimit(200000)

n,w = (int(x) for x in input().split())
a = [tuple(map(int, input().split())) for _ in range(n)]
dp = np.full((n+1, w+1), -1)

def rec(i, j):
  if dp[i][j] != -1:
    return dp[i][j]
  if i == n:
    res = 0
    dp[i][j] = res
    return dp[i][j]
  elif j < a[i][0]:
    res = rec(i+1, j)
    dp[i][j] = res
    return dp[i][j]
  else:
    res = max(rec(i+1, j), rec(i+1, j - a[i][0]) + a[i][1], 0)
    dp[i][j] = res
    return dp[i][j]

print(int(rec(0, w)))


### FIXED CODE ###

import sys
sys.setrecursionlimit(200000)

n,w = (int(x) for x in input().split())
a = [tuple(map(int, input().split())) for _ in range(n)]
dp = [[0] * (w+1) for _ in range(n+1)]

def rec(i, j):
  if dp[i][j] != 0:
    return dp[i][j]
  if i == n:
    res = 0
  elif j < a[i][0]:
    res = rec(i+1, j)
  else:
    res = max(rec(i+1, j), rec(i+1, j - a[i][0]) + a[i][1])
  dp[i][j] = res
  return dp[i][j]

print(int(rec(0, w)))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

"""
(駅、会社)を頂点にグラフを持つ。頂点数O(M)。
そのまま辺を貼ると辺が多くなりすぎる。
(駅、会社) -> (駅、無属性) -> (駅、会社)
"""

N,M = map(int,input().split())
PQC = [[int(x) for x in input().split()] for _ in range(M)]

V = set((x,0) for x in range(1,N+1))
V |= set((p,c) for p,q,c in PQC)
V |= set((q,c) for p,q,c in PQC)
V = list(V)
v_to_i = {v:i for i,v in enumerate(V)}

# グラフを作成
rows, cols = [],[]
rows += [i for i,(p,c) in enumerate(V) if c != 0]
cols += [v_to_i[(p,0)] for i,(p,c) in enumerate(V) if c != 0]
wt = [1] * len(rows)
rows += [v_to_i[(p,c)] for p,q,c in PQC]
cols += [v_to_i[(q,c)] for p,q,c in PQC]
wt += [0] * M

graph = csr_matrix((wt, (rows, cols)), (len(V), len(V)))

start = v_to_i[(1,0)]
goal = v_to_i[(N,0)]

dist = dijkstra(graph, directed = False, indices = start)[goal]

answer = -1 if dist == float('inf') else int((dist + 1)//2)
print(answer)





### FIXED CODE ###

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

"""
(駅、会社)を頂点にグラフを持つ。頂点数O(M)。
そのまま辺を貼ると辺が多くなりすぎる。
(駅、会社) -> (駅、無属性) -> (駅、会社)
"""

L = 32
mask = (1 << L) - 1
N,M = map(int,input().split())
graph = defaultdict(list)
for _ in range(M):
    p,q,c = map(int,input().split())
    p <<= L
    q <<= L
    graph[p].append(p+c)
    graph[p+c].append(p)
    graph[q].append(q+c)
    graph[q+c].append(q)
    graph[p+c].append(q+c)
    graph[q+c].append(p+c)

INF = 10 ** 9
dist = defaultdict(lambda: INF)

start = 1 << L
goal = N << L

q = [start] # 0 が会社に属していない状態
dist[start] = 0
d = 0
while q:
    qq = []
    while q:
        x = q.pop()
        if x & mask == 0:
            for y in graph[x]:
                if dist[y] <= d + 1:
                    continue
                dist[y] = d + 1
                qq.append(y)
        else:
            for y in graph[x]:
                if dist[y] <= d:
                    continue
                dist[y] = d
                q.append(y)
    d += 1
    q = qq

answer = dist[goal]
if answer == INF:
    answer = -1
print(answer)
### BUGGY CODE ###

import math
def comb(x,y):
    f = 1
    for i in range(y):
        f *= (x-i)
        f //= (i+1)

    return f

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

cnt = [0]
for i in range(2,m+1):
    while m!=i:
        if m%i==0:
            m //=i
            cnt[-1]+=1
        else:
            cnt.append(0)
            break
    if m==i:
        cnt[-1]+=1
        break
cnt = [item for item in cnt if cnt != 0]


res = 1

for item in cnt:
    res *= comb(item+n-1,item)

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


### FIXED CODE ###

import math
def comb(x,y):
    f = 1
    for i in range(y):
        f *= (x-i)
        f //= (i+1)

    return f

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

i = 2
cnt = []
while i*i<=m:
    c = 0
    while m%i == 0:
        m //= i
        c += 1
    if c>0:
        cnt.append(c)
    i+=1
if m>1:
    cnt.append(1)
        

res = 1
r = 10**9 +7
for item in cnt:
    res = (res* comb(item+n-1,item))%r

print(res%r)
### BUGGY CODE ###

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

maxIndex = [i for i, x in enumerate(a) if x == max(a)]
if len(maxIndex)>=2:
    for i in range(n):
        print(max(a))
else:
    z = maxIndex[0]
    s = max(a[0:z],a[z+1:n+1])
    maxa=max(a)
    for k in range(z):
            print(maxa)
    print(s[0])
    for k2 in range (n-z-1):
        print(maxa)



### FIXED CODE ###

import sys
n= int(input())
a =[int(input()) for i in range (n)]
b=max(a)
c=sorted(a)[-2]
for i in (a):
    if i == b:
        print(c)
    else:
        print(b)
### BUGGY CODE ###

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



### FIXED CODE ###

import bisect
n=int(input())
l=list(map(int,input().split()))
l.sort()
ans=0
for i in range(0,n-2):
    for j in range(i+1,n-1):
        x=l[i]+l[j]
        y=bisect.bisect_left(l,x)-j-1        
        ans+=y
print(ans)
### BUGGY CODE ###

n = int(input())
A = list(map(int,input().split()))
for a in A:
  if A.count(a) != 1:
    print('NO')
    break
else:
  print('YES')


### FIXED CODE ###

n = int(input())
A = list(map(int,input().split()))
A.sort()
for i in range(n-1):
    if A[i] == A[i+1]:
        print('NO')
        break
else:
    print('YES')
### BUGGY CODE ###

import fractions

data = [i for i in range(2, 10**12)]
for d in data:
	data = [x for x in data if (x == d or x % d != 0)]
A, B =list(map(int, input().split()))
D = fractions.gcd(A,B)
x = 1
for d in data:
  if D%d == 0:
    x = x+1
  else:
    pass
print(x)

### FIXED CODE ###

import fractions

A, B =list(map(int, input().split()))
D = fractions.gcd(A,B)
arr = []
temp = D
if D == 1:
  pass
else:
  for i in range(2, int(-(-D**0.5//1)+1)):
    if temp%i == 0:
      while temp%i == 0:
        temp //= i
      arr.append(i)
  if temp != 1:
    arr.append(D)
print(len(arr)+1)
### BUGGY CODE ###

# E - Handshake

N, M = map(int, input().split())
A = list(int(x) for x in input().split())

A.sort(reverse=True)

S = []
S.append(A[0])
for i in range(N-1):
    S.append(S[i]+A[i+1])
S.append(0)

# 幸福度がX以上となる握手がM以上になることを考える
# つまり、幸福度がXより大きい(X+1以上)の握手と
# 幸福度がXの握手を足すとM以上

def CheckHappy(x):
    X = list(map(lambda y: x - y, A))
    cnt = 0
    happy = 0
    for i in range(N):
        l = -1
        r = N
        while l+1 < r:
            m = (l+r)//2
            if A[m] >= X[i]:
                l = m
            else:
                r = m 
        cnt += l+1
        if l>=0:
            #print(A[i], S[l])
            happy += A[i]*(l+1)+S[l]
    #print('cnt, happy', cnt, happy)
    return cnt, happy

def isGreaterThanM(x):
    X = list(map(lambda y: x - y, A))
    #print('X',X)
    cnt = 0
    for i in range(N):
        l = -1
        r = N
        #print('l, r', l, r)
        while l+1 < r:
            m = (l+r)//2
            if A[m] >= X[i]:
                l = m
            else:
                r = m 
        cnt += l+1
        #print('cnt',cnt)
        if cnt >= M:
            return True
    return False


# 2分探索
left = min(A)*2-1
right = max(A)*2+1

while left+1 < right:
    mid = (left+right)//2
    if isGreaterThanM(mid):
        left = mid
    else:
        right = mid

#print('left, right', left, right)

tmp, ans = CheckHappy(right)
ans += (M-tmp)*left
print(ans)




### FIXED CODE ###

# E - Handshake

N, M = map(int, input().split())
A = list(int(x) for x in input().split())

A.sort(reverse=True)

S = []
S.append(A[0])
for i in range(N-1):
    S.append(S[i]+A[i+1])
S.append(0)

# 幸福度がX以上となる握手がM以上になることを考える
# つまり、幸福度がXより大きい(X+1以上)の握手と
# 幸福度がXの握手を足すとM以上

def CheckHappy(x):
    X = list(map(lambda y: x - y, A))
    cnt = 0
    happy = 0
    for i in range(N):
        l = -1
        r = N
        while l+1 < r:
            m = (l+r)//2
            if A[m] >= X[i]:
                l = m
            else:
                r = m 
        cnt += l+1
        if l>=0:
            #print(A[i], S[l])
            happy += A[i]*(l+1)+S[l]
    #print('cnt, happy', cnt, happy)
    return cnt, happy

def isGreaterThanM(x):
    X = list(map(lambda y: x - y, A))
    #print('X',X)
    cnt = 0
    for i in range(N):
        l = -1
        r = N
        #print('l, r', l, r)
        while l+1 < r:
            m = (l+r)//2
            if A[m] >= X[i]:
                l = m
            else:
                r = m 
        cnt += l+1
        #print('cnt',cnt)
        if cnt >= M:
            return True
    return False


# 2分探索
left = min(A)*2-1
right = max(A)*2+1

while left+1 < right:
    mid = (left+right)//2
    if isGreaterThanM(mid):
        left = mid
    else:
        right = mid

#print('left, right', left, right)

tmp, ans = CheckHappy(right)
ans += (M-tmp)*left
print(ans)
### BUGGY CODE ###

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

for i in range(n):
    if i == 0:
        l.append(a[i])
        continue
    for j in range(len(l)):
        if l[j] < a[i]:
            l[j]=(a[i])
            break
    else:
        l.append(a[i])

print(len(l))

### FIXED CODE ###

from bisect import bisect_left
from collections import deque

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

D = deque([])

for a in A:
    i = bisect_left(D, a)
    if i == 0:
        D.appendleft(a)
    else:
        D[i-1] = a

print(len(D))
### BUGGY CODE ###

import fractions
from functools import reduce
import copy

def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)
  
n = int(input())
A = list(int(i) for i in (input().split()))

ans = 0
tmp = 0
for i in range(n):
  list = copy.copy(A)
  list.remove(A[i])
  tmp = gcd_list(list)
  if(ans < tmp):
    ans = tmp

print(ans)

### FIXED CODE ###

import fractions
from functools import reduce

def gcd(*numbers):
    return reduce(fractions.gcd, numbers)
  
n = int(input())
A = list(int(i) for i in (input().split()))

front = []
end = []
for i in range(n):
  if(i == 0):
    front.append(gcd(*[A[0]]))
    end.append(gcd(*[A[n-1]]))
  else:
    front.append(gcd(*[front[i - 1],A[i]]))
    end.append(gcd(*[end[i - 1],A[n-1-i]]))

ans = 0
for i in range(n):
  if(i == 0):
    tmp = end[n-2]
  elif(i == n-1):
    tmp = front[n-2]
  else:
    tmp = gcd(*[front[i-1],end[n-2-i]])
  if(ans < tmp):
    ans = tmp
print(ans)
### BUGGY CODE ###

N=int(input())
A=[i for i in map(int,input().split())]
A.sort()
k=0
while k!=len(A):
    k=0
    for i in range(len(A)):
        if A[i]%min(A)!=0:
            A[i]=A[i]%min(A)
        else:
            k+=1  
    A.sort() 
print(min(A))

### FIXED CODE ###

N = int(input())
A = [int(_) for _ in input().split()]
m = min(A)
while m > 0:
    for i in range(0,len(A)):
        if A[i] != m:
            A[i] = A[i]%m
    z = A.count(0)
    A = sorted(A)[z:]
    m = A[0]
    if m == 1:
        break
    else:
        if [_%m for _ in A] == [0]*len(A):
            break
print(m)
### BUGGY CODE ###

H, W, D = [int(i) for i in input().split()]
B = [(-1, -1) for _ in range(H * W)]
for h in range(H):
    A = [int(i) - 1 for i in input().split()]
    for w in range(W):
        B[A[w]] = (h, w)

Q = int(input())
for l, r in [[int(i) - 1 for i in input().split()] for _ in range(Q)]:
    su = 0
    C = B[l:r + 1:D]
    h, w = C[0]
    for nh, nw in C[1:]:
        su += abs(nh - h) + abs(nw - w)
        h, w = nh, nw
    print(su)


### FIXED CODE ###

H, W, D = [int(i) for i in input().split()]
B = [(-1, -1) for _ in range(H * W)]
for h in range(H):
    A = [int(i) - 1 for i in input().split()]
    for w in range(W):
        B[A[w]] = (h, w)

C = [0] * (H * W)
for i in range(D, H * W):
    h, w = B[i - D]
    nh, nw = B[i]
    C[i] = C[i - D] + abs(nh - h) + abs(nw - w)

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

import sys
input = sys.stdin.readline
from heapq import nlargest
N = int(input())
A = list(map(int, input().split()))
f = [[a] for a in A]
for i in range(N):
    bit = 1<<i
    for j in range(1<<N):
        if j & bit:
            f[j] = nlargest(2, f[j]+f[j^bit])
Ans = [sum(f[1])]
for a, b in f[2:]:
    Ans.append(max(Ans[-1], a+b))
print("\n".join(map(str, Ans)))


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
f = [[a] for a in A]
for i in range(N):
    for j in range(1<<N):
        if j & 1<<i:
            f[j] = sorted(f[j]+f[j^1<<i], reverse=True)[:2]
Ans = [sum(f[1])]
for a, b in f[2:]:
    Ans.append(max(Ans[-1], a+b))
print("\n".join(map(str, Ans)))
### BUGGY CODE ###

from scipy.misc import comb
from collections import deque
N, K = map(int, input().split())
A = [int(x) for x in input().split()]
A = sorted(A)
B = deque()
C = deque()
for h in range(N):
    B.append(A[h])
    C.append(A[h])
mod = (10**9)+7
ans = 0
for i in range(N):
    if N - i >= K:
        kari = comb((N - i - 1), K-1, exact=True) % mod
        # print(kari)
        ans += (kari * B.pop()) % mod
        ans -= (kari * C.popleft()) % mod
        ans = ans % mod
print(ans)


### FIXED CODE ###

from collections import deque
N, K = map(int, input().split())
A = [int(x) for x in input().split()]
A = sorted(A)
B = deque()
C = deque()
mod = (10**9)+7
for h in range(N):
    B.append(A[h])
    C.append(A[h])


def cmb(n, r):  # 【Python】組み合わせ(nCr) 計算の高速化より引用
    if (r < 0 or r > n):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod


N_cmb = 10**5
g1 = [1, 1]  # 元テーブル
g2 = [1, 1]  # 逆元テーブル
inverse = [0, 1]  # 逆元テーブル計算用テーブル

for ZZZ in range(2, N_cmb + 1):
    g1.append((g1[-1] * ZZZ) % mod)
    inverse.append((-inverse[mod % ZZZ] * (mod//ZZZ)) % mod)
    g2.append((g2[-1] * inverse[-1]) % mod)


ans = 0
for i in range(N):
    if N - i >= K:
        kari = cmb(N - i - 1, K-1) % mod
        # print(kari)
        ans += (kari * B.pop()) % mod
        ans -= (kari * C.popleft()) % mod
        ans = ans % mod
print(ans)
### BUGGY CODE ###

a,b,c,d,e,f = map(int, input().split())
mx=0
swmx=0
smx=0

for i in range(0,31):
    for j in range(0,31):
        for k in range(0,1000):
            for l in range(0,1000):
                w=0
                s=0
                w+=100*a*i+100*b*j
                s+=c*k+d*l
                if w+s<=f and s<=e*w/100 and w!=0 and mx<100*s/(w+s):
                    mx=100*s/(w+s)
                    swmx=w+s
                    smx=s
print(swmx,smx)


### FIXED CODE ###

a,b,c,d,e,f = map(int, input().split())
mx=0
swmx=100*a
smx=0
 
for i in range(0,31):
    for j in range(0,31):
        for k in range(0,51):
            for l in range(0,51):
                w=0
                s=0
                w+=100*a*i+100*b*j
                s+=c*k+d*l
                if w+s<=f and s<=e*w/100 and w!=0 and mx<100*s/(w+s):
                    mx=100*s/(w+s)
                    swmx=w+s
                    smx=s
print(swmx,smx)
### BUGGY CODE ###

from bisect import bisect_left, bisect_right
N = int(input())
S = list(input())
Q = int(input())
 
D = {chr(ord('a') + i): [] for i in range(26)}
 
for i, s in enumerate(S):
    D[s].append(i)
 
for q in range(Q):
    query = list(input().split())
    if query[0] == '1':
        i, x = int(query[1]), query[2]
        i -= 1
        s = S[i]
        if s == x:
            continue
 
        D[s].remove(i)
        next_i = bisect_left(D[x], i)
        D[x].insert(next_i, i)
        S[i] = x
 
    if query[0] == '2':
        l, r = int(query[1]), int(query[2])
        l, r = l - 1, r - 1
        ans = 0
        for i in range(26):
            s = chr(ord('a') + i)
 
            li = bisect_left(D[s], l)
            ri = bisect_right(D[s], r)
 
            if ri - li > 0:
                ans += 1
 
        print(ans)

### FIXED CODE ###

from bisect import bisect_left, bisect_right
N = int(input())
S = list(input())
Q = int(input())

D = {chr(ord('a') + i): [] for i in range(26)}

for i, s in enumerate(S):
    D[s].append(i)

for q in range(Q):
    query = list(input().split())
    if query[0] == '1':
        i, x = int(query[1]), query[2]
        i -= 1
        s = S[i]
        if s == x:
            continue

        D[s].remove(i)
        next_i = bisect_left(D[x], i)
        D[x].insert(next_i, i)
        S[i] = x

    if query[0] == '2':
        l, r = int(query[1]), int(query[2])
        l, r = l - 1, r - 1
        ans = 0
        for i in range(26):
            s = chr(ord('a') + i)

            li = bisect_left(D[s], l)
            ri = bisect_right(D[s], r)

            if ri - li > 0:
                ans += 1

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

N = int(input())
Ai = list(map(int, input().split()))
p = 1
for i in range(N):
  if 0 in Ai:
    p = 0
    break
  p = p * Ai[i]
  if p > 10 **18:
    break
if p <= 10 ** 18:
    print(p)
else:
    print("-1")



### FIXED CODE ###

N = int(input())
Ai = list(map(int, input().split()))
p = 1
i = 0
if 0 in Ai:
    print("0")
else:
    while i <= N - 1:
        p = p * Ai[i]
        if p > 10 ** 18:
            print("-1")
            break
        if i == N - 1:
            print(p)
            break
        i += 1
### BUGGY CODE ###

a, b, q = [int(i) for i in input().split()]
s = []
for i in range(a):
	s.append(int(input()))
t = []
for i in range(b):
	t.append(int(input()))
x = []
for i in range(q):
	x.append(int(input()))

for xx in x:
  s_l = float('inf')
  s_r = float('inf')
  for ss in s:
    tmp = ss-xx
    if tmp <= 0:
      if abs(tmp) < s_l:
        s_l = abs(tmp)
    else:
      s_r = tmp
      break

  t_l = float('inf')
  t_r = float('inf')      
  for tt in t:
    tmp = tt-xx
    if tmp <= 0:
      if abs(tmp) < t_l:
        t_l = abs(tmp)
    else:
      t_r = tmp
      break
  
  l = max(s_l,t_l)
  r = max(s_r,t_r)
  lr_st = s_l*2 + t_r
  lr_ts = t_l*2 + s_r
  rl_st = t_l + s_r*2
  rl_ts = s_l + t_r*2
  ans = min(l,r,lr_st,lr_ts,rl_st,rl_ts)
  print(ans)
  

### FIXED CODE ###

from bisect import bisect

a, b, q = [int(i) for i in input().split()]
s = []
for i in range(a):
	s.append(int(input()))
s = [-float('inf')] + s + [float('inf')]
t = []
for i in range(b):
	t.append(int(input()))
t = [-float('inf')] + t + [float('inf')]
x = []
for i in range(q):
	x.append(int(input()))

for xx in x:
  
  s_i = bisect(s,xx)
  s_r = abs(xx - s[s_i])
  s_l = abs(xx - s[s_i-1])
  t_i = bisect(t,xx)
  t_r = abs(xx - t[t_i])
  t_l = abs(xx - t[t_i-1])

  
  #print(s_l,s_r,t_l,t_r)
  
  #l = max(s_l,t_l)
  #r = max(s_r,t_r)
  if s_l <= t_l:
    l = t_l
    lr = s_l*2 + t_r
  else:
    l = s_l
    lr = t_l*2 + s_r
  if s_r <= t_r:
    r = t_r
    rl = s_r*2 + t_l
  else:
    r = s_r
    rl = t_r*2 + s_l
 
  ans = min(l,r,lr,rl)
  print(ans)
### BUGGY CODE ###

# given an array of Heights, jump from 1 to N with at most K sized jump to N
# each jump incurs abs(H[j] - H[i]) cost
# minimize cost of jumps from 1 to N
#
import collections

def frog(H, k):
    if k > len(H):
        k = len(H)
    K = collections.deque([0] * (k + 1))
    n = len(H)
    klen = len(K)
    inf = float("inf")
    for i in range(n):
        cost = 0
        if i > 0:
            maxjump = i if i < k else k # min(i, k)
            cost = inf
            hi = H[i]
            for j in range(1, maxjump + 1):
                jcost = abs(hi - H[i - j]) + K[klen - j]
                if jcost < cost:
                    cost = jcost
        K.popleft()
        K.append(cost)
    return cost

assert frog([40, 10, 20, 70, 80, 10, 20, 70, 80, 60], 4) == 40
assert frog([10, 10], 100) == 0
assert frog([10, 20, 10], 1) == 20

if __name__ == "__main__":
    import sys
    s = sys.stdin.read()
    N, k, *H = map(int, s.split())
    ans = frog(H, k)
    print(ans)


### FIXED CODE ###

# given an array of Heights, jump from 1 to N with at most K sized jump to N
# each jump incurs abs(H[j] - H[i]) cost
# minimize cost of jumps from 1 to N
#
def frog(H, k):
    if k > len(H):
        k = len(H)
    n = len(H)
    K = [0] * n
    inf = float("inf")
    for i in range(n):
        cost = 0
        if i > 0:
            maxjump = i if i < k else k # min(i, k)
            cost = inf
            hi = H[i]
            # jump source going backwards from i-1 (smallest 1 sized jump) to i - maxjumps
            for j in range(i - 1, i - maxjump - 1, -1):
                jcost = abs(hi - H[j]) + K[j]
                if jcost < cost:
                    cost = jcost
        K[i] = cost
    return cost

assert frog([40, 10, 20, 70, 80, 10, 20, 70, 80, 60], 4) == 40
assert frog([10, 10], 100) == 0
assert frog([10, 20, 10], 1) == 20

if __name__ == "__main__":
    import sys
    s = sys.stdin.read()
    N, k, *H = map(int, s.split())
    ans = frog(H, k)
    print(ans)
### BUGGY CODE ###

import fractions

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

l_gcd = [0]
for i in range(n):
    l_gcd = l_gcd + [fractions.gcd(l_gcd[-1], a[i])]
# print(l_gcd)

r_gcd = [0]
for i in range(n):
    r_gcd = [fractions.gcd(r_gcd[0], a[-(i+1)])] + r_gcd
# print(r_gcd)

for i in range(n):
    ans = max(ans, fractions.gcd(l_gcd[i], r_gcd[i+1]))
print(ans)

### FIXED CODE ###

import fractions

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

l_gcd = [0]
for i in range(n):
    l_gcd.append(fractions.gcd(l_gcd[-1], a[i]))
# print(l_gcd)

r_gcd = [0]
for i in range(n):
    r_gcd.append(fractions.gcd(r_gcd[-1], a[-(i+1)]))
r_gcd.reverse()
# print(r_gcd)

for i in range(n):
    ans = max(ans, fractions.gcd(l_gcd[i], r_gcd[i+1]))
print(ans)