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

import fractions
from functools import reduce

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

ans=1
for i in range(N):
    b=A[:i]+A[i+1:]
    c=reduce(fractions.gcd, b)
    ans=max(ans,c)

print(ans)

### FIXED CODE ###

import sys

sys.setrecursionlimit(1000000)

import fractions
from functools import reduce

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

def mygcd(a,b):
    if a==0:
        return b
    elif b==0:
        return a
    else:
        return fractions.gcd(a,b)

L=[0]*N
for i in range(1,N):
    L[i]=mygcd(L[i-1],A[i-1])

R=[0]*N
for i in range(N-2,-1,-1):
    R[i]=mygcd(R[i+1],A[i+1])

ans=1
for i in range(N):
    c=mygcd(L[i],R[i])
    ans=max(ans,c)

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

from collections import deque
S=input()
S_list=deque()
for k in range(len(S)):
    S_list.append(S[k])
Q=int(input())
kouho=deque()
for i in range(Q):
    kari=input().split()
    kouho.append(kari)
for j in range(len(kouho)):
    if kouho[j][0]=="1":
        S_list.reverse()
    else:
        if kouho[j][1]=="1":
            S_list.appendleft(kouho[j][2])
        else:
            S_list.append(kouho[j][2])
print(*S_list,sep="")

### FIXED CODE ###

from collections import deque
S=input()
S_list=deque()
for k in range(len(S)):
    S_list.append(S[k])
Q=int(input())
kouho=[input().split() for i in range(Q)]
"""for i in range(Q):
    kari=input().split()
    kouho.append(kari)"""
hanten=[]
count=0
flaag=["sonomama","hantai"]

for j in range(Q):
    flag=flaag[count%2]
    if kouho[j][0]=="1":
        count+=1
    else:
        if flag=="sonomama":
            if kouho[j][1]=="1":
                S_list.appendleft(kouho[j][2])
            else:
                S_list.append(kouho[j][2])
        else:
            if kouho[j][1]!="1":
                S_list.appendleft(kouho[j][2])
            else:
                S_list.append(kouho[j][2])
for k in range(count%2):
    S_list.reverse()
print(*S_list,sep="")
### BUGGY CODE ###

(N,T)=map(int,input().split())
a=list(map(int,input().split()))
counter=0
max=0
for i in range(len(a)-1,-1,-1):
    for j in range(0,i):
        if a[i]-a[j] > max:
            max=a[i]-a[j]
for i in range(len(a)-1,-1,-1):
    for j in range(0,i):
        if a[i]-a[j] == max:
            counter+=1
print(counter)


### FIXED CODE ###

(N,T)=map(int,input().split())
a=list(map(int,input().split()))
x=10**9
d=0
counter=0
for i in a:
    if i<x:
        x=i
    elif i-x>d:
        d=i-x
        counter=1
    elif i-x==d:
        counter+=1
print(counter)
### BUGGY CODE ###

s = input()
q = int(input())
t1 = 1
for i in range(q):
    t = input()
    if t == '1':
        t1 *= -1
    else:
        if t1 == 1:
            if t[2] == '1':
                s = t[4] + s
            else:
                s = s + t[4]
        else:
            if t[2] == '2':
                s = t[4] + s
            else:
                s = s + t[4]

ans = ''
if t1 == -1:
    ans = ''.join(list(reversed(s)))
else:
    ans = s

print(ans)
    

### FIXED CODE ###

from collections import deque
s = deque(list(input()))
q = int(input())
t1 = 1
for i in range(q):
    t = input()
    if t == '1':
        t1 *= -1
    else:
        if t1 == 1:
            if t[2] == '1':
                s.appendleft(t[4])
            else:
                s.append(t[4])
        else:
            if t[2] == '2':
                s.appendleft(t[4])
            else:
                 s.append(t[4])

ans = ''
if t1 == -1:
    ans = ''.join(reversed(s))
else:
    ans = ''.join(s)

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

from collections import defaultdict
 
n, p = map(int, input().split())
s = input()
 
if p in (2, 5):
    if p == 2:
        ok_list = [i for i in range(10)][::2]
    else:
        ok_list = [0, 5]
    ans = 0
    for i in range(n):
        if int(s[i]) in ok_list:
            ans += i+1
    print(ans)
else:
    dd = defaultdict(int)
    dd[0] = 1
    for i in range(n):
        dd[int(s[i:]) % p] += 1
 
    ans = sum(v*(v-1)//2 for v in dd.values())
    print(ans)

### FIXED CODE ###

from collections import defaultdict

n, p = map(int, input().split())
s = input()

if p in (2, 5):
    if p == 2:
        ok_list = [i for i in range(10)][::2]
    else:
        ok_list = [0, 5]
    ans = 0
    for i in range(n):
        if int(s[i]) in ok_list:
            ans += i+1
    print(ans)
else:
    dd = defaultdict(int)
    dd[0] = 1
    prev = 0

    for i in range(n-1, -1, -1):
        d = int(s[i]) * pow(10, n-i, p)
        prev = (prev + d) % p
        dd[prev] += 1

    print(sum(v*(v-1)//2 for v in dd.values()))
### BUGGY CODE ###

N,K= map(int,input().split())
h=[1000000000]+list(map(int,input().split()))
dp=[0]*(N+1)

dp[1]=0
dp[2]=abs(h[2]-h[1])

if N>=3:
  for i in range(3,N+1):
    mini=1000000000
    for j in range(1,K+1):
      if i-j <1:
        pass
      else:
        mini=min(mini, dp[i-j] + abs(h[i]-h[i-j]) )
    dp[i]=mini
    
#print(dp)
print(dp[-1])

### FIXED CODE ###

N,K= map(int,input().split())
h=[1000000000]+list(map(int,input().split()))
dp=[0]*(N+1)

dp[1]=0
dp[2]=abs(h[2]-h[1])

if N>=3:
  for i in range(3,N+1):
    mini=1000000000
    for j in range(1,K+1):
      if i-j <1:
        pass
      else:
        mini=min(mini, dp[i-j] + abs(h[i]-h[i-j]) )
    dp[i]=mini
    
#print(dp)
print(dp[-1])
### BUGGY CODE ###

import heapq
def dijkstra(x,route):
    n=len(route)
    d=[float('inf')]*n
    d[x]=0
    Visited=[False]*n
    hq=[(0,x)]
    while hq:
        u=heapq.heappop(hq)[1]
        Visited[u]=True
        for v,cost in route[u]:
            if (not Visited[v]) and d[v]>d[u]+cost:
                d[v]=d[u]+cost
                heapq.heappush(hq,(d[v],v))
    return d

def dist(V1,V2):
    dx=V2[0]-V1[0]; dy=V2[1]-V1[1]
    sum_r=V1[2]+V2[2]
    return max(0,(dx**2+dy**2)**0.5-sum_r)

import sys
input=sys.stdin.readline
sx,sy,gx,gy=map(int,input().split())
n=int(input())
V=[(sx,sy,0)]+[tuple(map(int,input().split())) for _ in range(n)]+[(gx,gy,0)]
Edges=[[] for _ in range(n+2)]
for i in range(n+1):
    for j in range(i,n+2):
        d=dist(V[i],V[j])
        Edges[i].append((j,d))
        Edges[j].append((i,d))
print(dijkstra(0,Edges)[-1])

### FIXED CODE ###

import sys
input=sys.stdin.readline

def dijkstra(s,n,Cost):
    D=[float('inf')]*n
    Visited=[False]*n
    D[s]=0
    while True:
        v=-1
        for i in range(n):
            if (not Visited[i]) and v==-1:
                v=i
            elif (not Visited[i]) and D[i]<D[v]:
                v=i
        if v==-1:
            break
        Visited[v]=True
        for j in range(n):
            D[j]=min(D[j],D[v]+Cost[v][j])
    return D

def dist(V1,V2):
    return max(0,((V2[0]-V1[0])**2+(V2[1]-V1[1])**2)**0.5-(V1[2]+V2[2]))

sx,sy,gx,gy=map(int,input().split())
n=int(input())
V=[(sx,sy,0)]+[tuple(map(int,input().split())) for _ in range(n)]+[(gx,gy,0)]
Cost=[[float('inf')]*(n+2)for _ in range(n+2)]
for i in range(n+1):
    for j in range(i,n+2):
        d=dist(V[i],V[j])
        Cost[i][j]=d; Cost[j][i]=d
print(dijkstra(0,n+2,Cost)[-1])
### BUGGY CODE ###

n,q = list(map(int,input().split()))
from collections import defaultdict
import sys
sys.setrecursionlimit(100000)

dd_ab = defaultdict(list)
for i in range(n-1):
    a,b = tuple(map(int,input().split()))
    dd_ab[a].append(b)

dd_px = defaultdict(int)
for i in range(q):
    p,x = tuple(map(int,input().split()))
    dd_px[p] += x

ret = [0] * (n+1)
def add_tree(node,value):
    retn = value
    if dd_px[node]:
        retn += dd_px.pop(node)
    ret[node] += retn
    if dd_ab[node]:
        for n in dd_ab.pop(node):
            add_tree(n,retn)
add_tree(1,0)
for i in ret[1::]:
    print(i)

### FIXED CODE ###

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

def main():
    N, Q = map(int, input().split())
    edges = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        edges[b-1].append(a-1)
        edges[a-1].append(b-1)

    counts = [0]*N
    for _ in range(Q):
        p, x = map(int, input().split())
        counts[p-1] += x

    parent_nodes = deque()
    parent_nodes.append(0)
    visited_nodes = set()
    while parent_nodes:
        parent = parent_nodes.popleft()
        if parent in visited_nodes:
            continue
        visited_nodes.add(parent)
        for child in edges[parent]:
            if child in visited_nodes:
                continue
            counts[child] += counts[parent]
            parent_nodes.append(child)

    print(' '.join(list(map(str, counts))))

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

N = int(input())
P = list(map(int, input().split()))
Q = []

ans = 0

for i in range(N):
    Q.append(P[i])
    if all([P[i] <= j for j in Q]):
        ans += 1

print(ans)

### FIXED CODE ###

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

tmp = P[0]
ans = 0

for i in P:
    if i <= tmp:
        ans += 1
        tmp = i
        
print(ans)
### BUGGY CODE ###


import sys
input = sys.stdin.readline
#区間の管理は　[a, b)で管理していることに注意

# INT_MIN = -10 ** 18
# MAX_N = 4 * 10 ** 5
# MAX_N = 20


def init(n_):
    #簡単にするために2のべき乗に揃える
    n = 1
    while n <= n_:
        n *= 2
    return n

#初期化
N = int(input())
n = init(N)
data = [0] * (2 * n - 1)

def update(k, a):
    k += n - 1
    data[k] = a
    while k > 0:
        k = (k - 1) // 2
        data[k] = max(data[2 * k + 1], data[2 * k + 2])

def query(a, b, k = 0, l = 0, r = n):
    if r <= a or b <= l:
        return 0
    elif a <= l and r <= b:
        return data[k]
    else:
        v1 = query(a, b, 2 * k + 1, l, (l + r)//2)
        v2 = query(a, b, 2 * k + 2, (l + r)//2, r)
        return max(v1, v2)

H = tuple(map(int, input().split()))
A = tuple(map(int, input().split()))

# ans = 0
for i in range(N):
    # h = int(input())
    # a = int(input())
    h = H[i]
    a = A[i]
    tmp = query(1, h + 1) #[1, h)での最大値
    # print (h, tmp)
    update(h, tmp + a)
    # ans = max(ans, tmp + a)
    # print (data)

print (query(1, N + 1))

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    #区間の管理は　[a, b)で管理していることに注意

    # INT_MIN = -10 ** 18
    # MAX_N = 4 * 10 ** 5
    # MAX_N = 20


    # def init(n_):
    #     #簡単にするために2のべき乗に揃える
    #     n = 1
    #     while n <= n_:
    #         n *= 2
    #     return n

    #初期化
    N = int(input())
    # n = 1
    # while n <= N:
    #     n *= 2

    n = 262144
    data = [0] * (2 * n - 1)

    def update(k, a):
        k = k + n - 1
        # data[k] = a
        while k >= 0:
            data[k] = max(a, data[k])
            k = (k - 1) // 2
            # data[k] = max(data[2 * k + 1], data[2 * k + 2])

    def query(a, b, k, l, r):
        if r <= a or b <= l:
            return 0
        elif a <= l and r <= b:
            return data[k]
        else:
            return max(query(a, b, 2 * k + 1, l, (l + r)//2), query(a, b, 2 * k + 2, (l + r)//2, r))

    H = tuple(map(int, input().split()))
    A = tuple(map(int, input().split()))

    # ans = 0

    dp = [A[0]] + [0] * (N - 1)
    update(H[0] - 1, A[0])
    for i in range(1, N):
        # h = int(input())
        # a = int(input())
        dp[i] = query(0, H[i] - 1, 0, 0, n) + A[i]
        # h = H[i]
        # a = A[i]
        # tmp = query(1, h + 1) #[1, h)での最大値
        # print (h, tmp)
        update(H[i] - 1, dp[i])
        # ans = max(ans, tmp + a)
        # print (data)

    print (query(0, N, 0, 0, n))

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

N = int(input())
S = [s for s in input()]
ans = 0
for i in range(1000):
    v = str(i).zfill(3)
    idx = 0
    for j, s in enumerate(S):
        if v[idx] in S[j:]:
            if v[idx] == s:
                idx += 1
            if idx == 3:
                ans += 1
                break
        else:
            break
print(ans)

### FIXED CODE ###

N = int(input())
S = input()
ans = 0
for i in range(1000):
    v = str(i).zfill(3)
    idx = 0
    c = 0
    idx_now = 0
    for j in range(3):
        idx = S[idx_now:].find(v[j])
        if idx == -1:
            break
        else:
            idx_now += idx + 1
            c += 1
    if c == 3:
        ans += 1
print(ans)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
import collections

def main():
    N = int(input())
    Q = [collections.deque(map(int, input().split())) for _ in range(N)]
    games = N*(N-1)//2

    days = 0
    while 1:
        gamed = [0 for _ in range(N)]
        for i in range(N-1):
            if gamed[i] or not len(Q[i]):
                continue
            j = Q[i][0] - 1
            if gamed[j] or not len(Q[j]):
                continue
            if Q[j][0] == i+1:
#                print("game:", j+1, i+1, days)
                Q[i].popleft()
                Q[j].popleft()
                gamed[i] = gamed[j] = 1
                games -= 1
        days += 1
        if not 1 in gamed:
            print(-1)
            return
        if games == 0:
            break

    print(days)
if __name__ == '__main__':
    main()


### FIXED CODE ###

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

def main():
    N = int(input())
    Q = [deque(map(int, input().split())) for _ in range(N)]
    games = N*(N-1)//2

    days = 0
    nxt = [i for i in range(N)] # 翌日に対戦相手を更新する選手のリスト
    opp = [0]*N # 選手毎の、次の対戦相手のリスト
    while 1:
        days += 1
        for i in nxt:
            opp[i] = Q[i].popleft() - 1 if Q[i] else -1

        tmp = set() # 次の日の更新のため、試合をした選手をメモ
        for i in nxt:
            if i not in tmp and i == opp[opp[i]]:
#                print("game:", i+1, opp[i]+1, days)
                tmp.add(i)
                tmp.add(opp[i])
                games -= 1
        if games == 0:
            break
        elif not tmp:
            print(-1)
            return
        nxt = tmp
    print(days)

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

N, K = map(int, input().split())
MOD = 998244353
S = set()
for i in range(K):
    l, r = map(int, input().split())
    for j in range(l, r + 1):
        S.add(j)

dp = [0] * N
dp[0] = 1
for i in range(1, N):
    for s in S:
        if s > i:
            continue
        dp[i] += dp[i - s]
print(dp[-1] % MOD)


### FIXED CODE ###

N, K = map(int, input().split())
MOD = 998244353

L = []
R = []
for i in range(K):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)

dp = [0] * (N + 1)
dp[1] = 1
dp_sum = [0] * (N + 1)
dp_sum[1] = 1
for i in range(2, N + 1):
    for j in range(K):
        li = max(i - R[j], 1)
        ri = i - L[j]
        if ri < 1:
            continue
        dp[i] += (dp_sum[ri] - dp_sum[li - 1]) % MOD
    dp_sum[i] = (dp_sum[i - 1] + dp[i]) % MOD

print(dp[-1] % MOD)
### BUGGY CODE ###





def LI():
    return list(map(int,input().split()))
    
def OPEN():
    return map(int,open(0).read().split())
import numpy   
h,w,m=LI()
S=[[0]*w for i in range(h)]
for i in range(m):
    h,w=LI()
    S[h-1][w-1]=1
S=numpy.array(S)
now=0
ind_x=[]
ind_y=[]
Ssumx=[sum(i) for i in S]
SS=S.T
Ssumy=[sum(i) for i in SS]



mx=max(Ssumx)-1
for i,j in enumerate(Ssumx):
    if j>=mx:
        ind_x.append((i,j))
my=max(Ssumy)-1
for i,j in enumerate(Ssumy):
    if j>=my:
        ind_y.append((i,j))
ans=0
for x,numx in ind_x:
    for y,numy in ind_y:
        if S[x][y]==0:
            tmp=numx+numy
        else:
            tmp=numx+numy-1

            
        ans=max(ans,tmp)
        
print(ans)


### FIXED CODE ###

h,w,m=map(int,input().split())
a=[0]*h
b=[0]*w
hw=[]
for _ in range(m):
    hh,ww=map(int,input().split())
    hw+=((hh-1,ww-1)),
    a[hh-1]+=1
    b[ww-1]+=1
    
ma=max(a)
mb=max(b)

# x_ind=[i for i,j in enumerate(a) if j==ma]
# y_ind=[i for i,j in enumerate(b) if j==mb]



cnt=0
# sonzai suru

for i,j in hw:
    if a[i]==ma and b[j]==mb:cnt+=1

if cnt==a.count(ma)*b.count(mb):
    print(ma+mb-1)
else:
    print(ma+mb)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
s = 0
mod = 10**9+7
for i in range(len(a)-1):
    for j in range(i+1, len(a)):
        s += a[i]*a[j]
        if s > mod:
            s%=mod
print(s)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
mod = 10**9+7
k = 0
b = [0]*len(a)
ans = 0
for i in range(len(a)-1, 0, -1):
    k += a[i]
    k %= mod
    b[i] = k
for i in range(len(a)-1):
    ans += a[i] * b[i+1]
    ans %= mod

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

x,y,num = map(int, input().split())
gaiz = []
zen_gaiz = [[] for _ in range(x)]
kaisu = x
for _ in range(num):
    xg,yg = map(int,input().split())
    if xg >= yg:
        zen_gaiz[xg-1].append(yg)
        if xg != yg:
            gaiz.append((xg,yg))

if len(gaiz) ==0:
    print(kaisu)
else:
    finish = False
    for gai in sorted(gaiz, key=lambda x: x[0]):
        hidari = [gai[0]-1, gai[1]]
        while True:
            if hidari[1]==1: 
                kaisu = gai[0]-1
                finish=True
                break
            for g in zen_gaiz:
                if hidari[1] in zen_gaiz[hidari[0]-1]:
                    break
            else:
                hidari[0]-=1
                hidari[1]-=1
                continue
            break
        if finish:
            break
    print(kaisu) 
                

### FIXED CODE ###

x,y,num = map(int, input().split())
gaiz = [x]*x
kaisu = x
for _ in range(num):
    xg,yg = map(int,input().split())
    if xg >= yg:
        sa = xg-yg
        if yg < gaiz[sa]:
            gaiz[sa]=(yg)
 
if len(gaiz) ==0:
    print(kaisu)
else:
    for num,(maegai,gai) in enumerate(zip(gaiz[:-1],gaiz[1:])):
        if maegai>gai and num+gai < kaisu:
            kaisu = num+gai
    print(kaisu)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
c = 0
for i in range(N):
    ans = A.count(i+1)
    # c+= ans
    print(ans)


### FIXED CODE ###

N=int(input())
A=[int(x) for x in input().split()]
d=[0]*(N+1)
for i in range(N-1):
    d[A[i]]+=1
for i in range(1,len(d)):
    print(d[i])
### BUGGY CODE ###

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

maxL = 0

for i in range(1, N-1):
    cnt = 0
    left = 0
    for j in range(0, N-i):
        if S[j]==S[j+i]:
            cnt+=1
            if maxL < cnt:
                maxL = cnt
            if cnt == i:
                break
        else:
            cnt = 0
            left = j + 1

print(maxL)

### FIXED CODE ###

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

maxL = 0

for i in range(1, N-1):
    cnt = 0
    left = 0
    for j in range(0, N-i):
        if S[j]==S[j+i]:
            cnt+=1
            if maxL < cnt:
                maxL = cnt
            if cnt == i:
                break
        else:
            cnt = 0
            left = j + 1

print(maxL)
### BUGGY CODE ###

h,n=map(int,input().split())
a=[]
b=[]
for i in range(n):
    x,y=map(int,input().split())
    a.append(x)
    b.append(y)

cost=[float("inf")]*(h+1)
cost[0]=0
for i in range(1,h+1):
    for j in range(0,n):
        cost[i]=min(cost[i],cost[max(i-a[j],0)]+b[j])

print(cost[-1])

### FIXED CODE ###

h,n=map(int,input().split())
a=[]
b=[]
for i in range(n):
    x,y=map(int,input().split())
    a.append(x)
    b.append(y)

cost=[float("inf")]*(h+1)
cost[0]=0
for i in range(1,h+1):
    for j in range(0,n):
        cost[i]=min(cost[i],cost[max(i-a[j],0)]+b[j])

print(cost[-1])
### BUGGY CODE ###

a, b, k = map(int,input().split())
xs = [x for x in range(a,b+1)]
xs = sorted(list(set(xs[:k] + xs[-k:])))
for x in xs:
    print(x)

### FIXED CODE ###

a, b, k = map(int, input().split())
if b-a+1 < 2*k:
    for i in range(a,b+1):
        print(i)
    exit(0)
for i in range(a,a+k):
    print(i)
for i in range(b-k+1,b+1):
    print(i)
### BUGGY CODE ###

from heapq import heappush, heappop
from math import sqrt
readline = open(0).readline
xs, ys, xt, yt = map(int, readline().split())
N = int(readline())
C = [list(map(int, readline().split())) for i in range(N)]
C.append((xt, yt, 0))

que = []
dist = [10**18]*(N+1)
rest = set(range(N+1))
for i in range(N+1):
    x, y, r = C[i]
    d0 = (xs - x)**2 + (ys - y)**2
    r0 = sqrt(d0) - r if d0 > r**2 else 0
    dist[i] = r0
    heappush(que, (r0, i))

remove = rest.remove
while que:
    c, i = heappop(que)
    if i not in rest:
        continue
    if i == N:
        break
    xi, yi, ri = C[i]
    remove(i)
    d = dist[i]
    e = dist[N]-d
    for j in rest:
        x, y, r = C[j]
        d0 = (xi - x)**2 + (yi - y)**2
        r0 = sqrt(d0) - ri - r if d0 > (ri + r)**2 else 0
        if e > r0 < dist[j]-d:
            dist[j] = v = d + r0
            heappush(que, (v, j))
print("%.016f" % dist[N])

### FIXED CODE ###

from heapq import heappush, heappop
from math import sqrt
xs, ys, xt, yt = map(int, raw_input().split())
n = input()
ps = [map(int, raw_input().split()) for i in xrange(n)]
cant = [0]*n
for i in xrange(n):
    x0, y0, r0 = ps[i]
    for j in xrange(n):
        x1, y1, r1 = ps[j]
        if i == j or r0 > r1: continue
        if (x0 - x1)**2 + (y0 - y1)**2 <= (r1 - r0)**2:
            cant[i] = 1
            break

EPS = 1e-10
que = []
dist = [10**18+7]*n
def calc(x0, y0, r0, x1, y1, r1):
    v = (x0 - x1)**2 + (y0 - y1)**2
    if v <= (r0+r1)**2:
        return 0.
    return sqrt(v) - r0 - r1
for i in xrange(n):
    if cant[i]: continue
    x, y, r = ps[i]
    d = dist[i] = calc(xs, ys, 0, x, y, r)
    heappush(que, (d, i))
while que:
    d, v = heappop(que)
    if dist[v] < d:
        continue
    x0, y0, r0 = ps[v]
    for t in xrange(n):
        if v == t or cant[t]: continue
        x1, y1, r1 = ps[t]
        nd = calc(x0, y0, r0, x1, y1, r1)
        if d+nd < dist[t]:
            dist[t] = d+nd
            heappush(que, (d+nd, t))
ans = sqrt((xs - xt)**2 + (ys - yt)**2)
for i in xrange(n):
    if cant[i]: continue
    x, y, r = ps[i]
    d = calc(xt, yt, 0, x, y, r) + dist[i]
    ans = min(ans, d)
print "%.010f" % ans
### BUGGY CODE ###

a,b,x=map(int,input().split())
count=0
for i in range(a,b+1):
    if i%x==0:
        count+=1
print(count)
        

### FIXED CODE ###

a,b,x=map(int,input().split())
print(b//x-(a-1)//x)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from math import sqrt

N,K=map(int,input().split())
M=[tuple(map(int,input().split())) for i in range(N)]

def calcdismax(x,y):
    TIME=[]
    for mx,my,c in M:
        TIME.append(c*sqrt((mx-x)**2+(my-y)**2))

    TIME.sort()

    #print(TIME)

    return TIME[K-1]

def div100(xmin,xmax,ymin,ymax):

    xh=(xmax-xmin)/150
    yh=(ymax-ymin)/150

    MIN=1<<30
    MINx=0
    MINy=0

    for i in range(151):
        xk=xmin+xh*i
        for j in range(151):
            yk=ymin+yh*j
            cd=calcdismax(xk,yk)

            #print(xk,yk,cd)

            if MIN>cd:
                MIN=cd
                MINx=xk
                MINy=yk

    #print(MINx,MINy,MIN)

    return MINx,MINy

now=1010
k=0
l=0
while now>10**(-10):
    k,l=div100(k-now,k+now,l-now,l+now)
    now/=2

print(calcdismax(k,l))


### FIXED CODE ###

import sys
input = sys.stdin.readline
from math import sqrt

N,K=map(int,input().split())
M=[tuple(map(int,input().split())) for i in range(N)]

def cross_coor(x0,y0,c0,x1,y1,c1): # 二円の交点
    if (c1-c0)**2<=(x1-x0)**2+(y1-y0)**2<=(c0+c1)**2:
        x2,y2=x1-x0,y1-y0
        a=(x2**2+y2**2+c0**2-c1**2)/2

        xa=(a*x2+y2*sqrt((x2**2+y2**2)*(c0**2)-a**2))/(x2**2+y2**2)+x0
        ya=(a*y2-x2*sqrt((x2**2+y2**2)*(c0**2)-a**2))/(x2**2+y2**2)+y0

        xb=(a*x2-y2*sqrt((x2**2+y2**2)*(c0**2)-a**2))/(x2**2+y2**2)+x0
        yb=(a*y2+x2*sqrt((x2**2+y2**2)*(c0**2)-a**2))/(x2**2+y2**2)+y0

        return [(xa,ya),(xb,yb)]
    else:
        return False

OK=1<<31
NG=0

while OK-NG>10**(-8):
    mid=(OK+NG)/2
    
    CANDI=[]
    for i in range(N):
        x0,y0,c0=M[i]
        CANDI.append((x0,y0))
        for j in range(i+1,N):
            x1,y1,c1=M[j]
            CR=cross_coor(x0,y0,mid/c0,x1,y1,mid/c1)
            if CR:
                CANDI.extend(CR)

    for z,w in CANDI:
        count=0
        for x,y,c in M:
            if (c**2)*((x-z)**2+(y-w)**2)<=(mid+10**(-8))**2:
                count+=1
            
        if count>=K:
            OK=mid
            break
    else:
        NG=mid

print((OK+NG)/2)