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

from heapq import heappush, heappop
sx,sy,gx,gy=map(int,input().split())
n=int(input())
g = [[] for i in range(n+2)]
data=[(sx+sy*1j,0)]
for i in range(n):
    a,b,c=map(int,input().split())
    data.append((a+b*1j,c))
data.append((gx+gy*1j,0))

for i in range(n+2):
    for j in range(i+1,n+2):
        tmp=abs(data[i][0]-data[j][0])-data[i][1]-data[j][1]
        g[i].append((tmp,j))
        g[j].append((tmp,i))

dist=[2828427127 for i in range(n+2)]
visited=[False for i in range(n+2)]
dist[0]=0
que=[]
heappush(que,(0,0))

while que:
    c,v=heappop(que)
    if visited[v]:
        continue
    visited[v]=True
    if v==n+1:
        break
    for x in g[v]:
        if visited[x[1]]:
            continue
        tmp=x[0]+c if not x[0]<0 else c
        if tmp<dist[x[1]]:
            dist[x[1]]=tmp
            heappush(que,(tmp,x[1]))
print(dist[n+1])


### FIXED CODE ###

from heapq import heappush, heappop
sx,sy,gx,gy=map(int,input().split())
n=int(input())
g = [[] for i in range(n+2)]
data=[(sx+sy*1j,0)]
for i in range(n):
    a,b,c=map(int,input().split())
    data.append((a+b*1j,c))
data.append((gx+gy*1j,0))

for i in range(n+2):
    for j in range(i+1,n+2):
        tmp=abs(data[i][0]-data[j][0])-data[i][1]-data[j][1]
        g[i].append((tmp,j))
        g[j].append((tmp,i))

dist=[2828427127 for i in range(n+2)]
visited=[False for i in range(n+2)]
dist[0]=0
que=[]
heappush(que,(0,0))

while que:
    c,v=heappop(que)
    if visited[v]:
        continue
    visited[v]=True
    for x in g[v]:
        if visited[x[1]]:
            continue
        tmp=x[0]+c if not x[0]<0 else c
        if tmp<dist[x[1]]:
            dist[x[1]]=tmp
            heappush(que,(tmp,x[1]))
print(dist[n+1])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**8)

N = int(input())
abc = [list(map(int, input().split())) for i in range(N)]
abc.append([0, 0, 0])

dp = [[-1] * 4 for i in range(N + 1)]


def happy(n, p):
    if n < 0:
        return 0
    if dp[n][p] >= 0:
        return dp[n][p]

    a = 0 if p == 0 else happy(n - 1, 0) + abc[n][0]
    b = 0 if p == 1 else happy(n - 1, 1) + abc[n][1]
    c = 0 if p == 2 else happy(n - 1, 2) + abc[n][2]
    dp[n][p] = max([a, b, c])

    return dp[n][p]


print(happy(N - 1, 3))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)

N = int(input())
abc = [list(map(int, input().split())) for i in range(N)]
abc.append([0, 0, 0])

dp = [[-1] * 4 for i in range(N + 1)]


def happy(n, p):
    if n < 0:
        return 0
    if dp[n][p] >= 0:
        return dp[n][p]

    a = 0 if p == 0 else happy(n - 1, 0) + abc[n][0]
    b = 0 if p == 1 else happy(n - 1, 1) + abc[n][1]
    c = 0 if p == 2 else happy(n - 1, 2) + abc[n][2]
    dp[n][p] = max([a, b, c])

    return dp[n][p]


print(happy(N - 1, 3))
### BUGGY CODE ###

class Edge:
  def __init__(self, starting_point, arrival_point, cost):
    self.starting_point = starting_point
    self.arrival_point = arrival_point
    self.cost = cost

def solve():
  N, M, P = map(int, input().split())
  edges = []
  dist = [float('inf') for _ in range(N + 10)]
  dist[1] = 0
  ans = 0
  for i in range(M):
    a, b, c = map(int, input().split())
    e = Edge(a, b, -c + P)
    edges.append(e)
  for i in range(2 * N):
    for e in edges:
      if dist[e.arrival_point] > e.cost + dist[e.starting_point]:
        dist[e.arrival_point] = e.cost + dist[e.starting_point]
        if e.arrival_point == N and i == 2 * N - 1:
          return -1
  return max((-1) * dist[N], 0)
print(solve())

### FIXED CODE ###

class Edge:
  def __init__(self, starting_point, arrival_point, cost):
    self.starting_point = starting_point
    self.arrival_point = arrival_point
    self.cost = cost

def solve():
  N, M, P = map(int, input().split())
  edges = []
  INF = float('inf')
  dist = [INF for _ in range(N + 10)]
  dist[1] = 0
  for i in range(M):
    a, b, c = map(int, input().split())
    e = Edge(a, b, -c + P)
    edges.append(e)
  for i in range(2 * N):
    for e in edges:
      if dist[e.arrival_point] > e.cost + dist[e.starting_point]:
        dist[e.arrival_point] = e.cost + dist[e.starting_point]
        if i == N - 1:
          dist[e.arrival_point] = -INF
  if dist[N] != -INF:
    return max(-dist[N], 0)
  else:
    return -1
print(solve())
### BUGGY CODE ###

A, B, K = map(int, input().split())

for _ in range(K):
    if A > 0:
        A -= 1
    elif B > 0:
        B -= 1
    else:
        continue
print(A, B)


### FIXED CODE ###

A, B, K = map(int, input().split())

C = max(0, A - K)
K -= A - C
print(C, max(0, B - K))
### BUGGY CODE ###

N = int(input())
A = int(input())
B = int(input())
C = int(input())
D = int(input())
E = int(input())

t = 0
a, b, c, d, e = 0, 0, 0, 0, 0
n = N

while(True):
    t += 1
    # calc minus
    x1 = A if n > A else n
    x2 = B if a > B else a
    x3 = C if b > C else b
    x4 = D if c > D else c
    x5 = E if d > E else d

    n -= x1
    a -= x2
    b -= x3
    c -= x4
    d -= x5

    # calc add
    a += x1
    b += x2
    c += x3
    d += x4
    e += x5

    if e >= N:
        break

print(t)


### FIXED CODE ###

import math

N = int(input())
A = int(input())
B = int(input())
C = int(input())
D = int(input())
E = int(input())

t = 0
a, b, c, d, e = 0, 0, 0, 0, 0
n = N

#while(True):
#    t += 1
#    # calc minus
#    x1 = A if n > A else n
#    x2 = B if a > B else a
#    x3 = C if b > C else b
#    x4 = D if c > D else c
#    x5 = E if d > E else d
#
#    n -= x1
#    a -= x2
#    b -= x3
#    c -= x4
#    d -= x5
#
#    # calc add
#    a += x1
#    b += x2
#    c += x3
#    d += x4
#    e += x5
#
#    if e >= N:
#        break
# print(t)

print(math.ceil(N / min([A, B, C, D, E])) + 4)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
import statistics

def comb(a, b):
  s = 1
  for i in range(a, b, -1):
    s *= i
  return s/2
import math

MA = max(A)
ans = (0, 0)
AL = 0
A.remove(MA)
upper = statistics.median_high(A)
lower = statistics.median_low(A)

r1 = math.factorial(MA) // (math.factorial(MA-upper) * math.factorial(upper))
r2 = math.factorial(MA) // (math.factorial(MA-lower) * math.factorial(lower))

if upper == lower:
  print(MA, upper)
  exit()
  
if r1 > r2:
  print(MA, upper)
else:
  print(MA, lower)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
import statistics

def comb(a, b):
  s = 1
  for i in range(a, b, -1):
    s *= i
  return s/2
import math

MA = max(A)
A.remove(MA)
SA = sorted(A)

h = MA // 2

da = 10**10
ans = 0
for a in SA:
  diff = abs(a-h)
  if da >= diff:
    da = diff
    ans = a
print(MA, ans)
### BUGGY CODE ###

def inN():
    return int(input())
def inL():
    return list(map(int,input().split()))

n,k = inL()
a = inL()
sum = 1
sum2 = 1
for i in range(k):
    sum2 *= a[i]
for i in range(k,n):
    #print(sum2)
    sum = 1
    for j in range(i-k+1,i+1):
        sum *= a[j]
    if sum > sum2:
        print('Yes')
    else:
        print('No')
    sum2 = sum

### FIXED CODE ###

def inN():
    return int(input())
def inL():
    return list(map(int,input().split()))

n,k = inL()
a = inL()

for i in range(k,n):
    if a[i] > a[i-k]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

def isPrime(n):
    for p in primes:
        if n%p == 0:
            return False
        elif n < p*p:
            return True

primes = [2,3,5,7]
for i in range(11,10**5,2):
    if isPrime(i):
        primes.append(i)
n2017s = [0]
for p in primes[1:]:
    if (p+1)//2 in primes:
        n2017s.append(p)

def binary_search(n):
    l=0
    r=len(n2017s)-1
    while l+1<r:
        i = (l+r)//2
        if n2017s[i] > n:
            r = i
        else:
            l = i
    return l

Q = int(input())
for i in range(Q):
    l,r = map(int,input().split())
    print(binary_search(r+1)-binary_search(l-1))

### FIXED CODE ###

def isPrime(n):
    for p in primes:
        if n%p == 0:
            return False
        elif n < p*p:
            return True

primes = [2,3,5,7]
for i in range(11,10**5,2):
    if isPrime(i):
        primes.append(i)
n2017s = [0]
for p in primes[1:]:
    if (p+1)//2 in primes:
        n2017s.append(p)
n2017s.append(10**6)
        
def binary_search(n):
    l=0
    r=len(n2017s)-1
    while l+1<r:
        i = (l+r)//2
        if n2017s[i] > n:
            r = i
        else:
            l = i
    return l

Q = int(input())
for i in range(Q):
    l,r = map(int,input().split())
    print(binary_search(r+1)-binary_search(l-1))
### BUGGY CODE ###

s=input()
q=int(input())
n=0
for i in range(q):
    li=input().split()
    if int(li[0])==1:
        n+=1
    elif int(li[0])==2:
        if (n%2==0 and int(li[1])==1) or (n%2==1 and int(li[1])==2):
            s=li[2]+s
        else:
            s=s+li[2]
if n%2==0:
    print(s)
else:
    st=list(s)
    st.reverse()
    print(''.join(st))


### FIXED CODE ###

from collections import deque
s=input()
q=int(input())
n=0
que=deque(s)
for i in range(q):
    l=input()
    if l[0]=='1':
        n+=1
    else:
        if (l[2]=='1' and n%2==0) or (l[2]=='2' and n%2==1):
            que.appendleft(l[4])
        else:
            que.append(l[4])

ans=''.join(que)
if n%2==0:
    print(ans)
else:
    print(ans[::-1])
### BUGGY CODE ###

import collections

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

lr = [list(map(int, input().split())) for i in range(m)]
lr_gate = []

for i in range(m):
    for j in range(lr[i][0], lr[i][1] + 1):
        lr_gate.append(j)

lr_gate = map(str, lr_gate)
lr_collect = collections.Counter(lr_gate)

count = 0
for v in lr_collect.values():
    if v == m:
        count += 1

print(count)

### FIXED CODE ###

n, m = list(map(int, input().split()))
lr = [list(map(int, input().split())) for i in range(m)]
lr.sort()
r_min = 100000
l_max = 0
lr_min = 100000

for i in range(m):
    l_max = max(lr[i][0], l_max)
    r_min = min(lr[i][1], r_min)

lr_min = [r_min - l_max + 1 if l_max <= r_min else 0]
print(lr_min[0])
### BUGGY CODE ###

def solve():
  L, R = map(int, input().split())
  ans = 2019
  for i in range(L, R):
    for j in range(i + 1, R + 1):
      v = i * j % 2019
      if v < ans: ans = v
  return ans

print(solve())


### FIXED CODE ###

def solve():
  L, R = map(int, input().split())
  ans = 2019
  for i in range(L, R):
    for j in range(i + 1, R + 1):
      v = i * j % 2019
      if v < ans: ans = v
      if ans == 0: return 0
  return ans

print(solve())
### BUGGY CODE ###

import math
from itertools import permutations
#from scipy.sparse import*

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    n=len(d[0])
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

N,M,R=[int(x) for x in input().split()]
r=[int(x)-1 for x in input().split()]

route_list=[[10*9]*N for i in range(N)]

for i in range(M):
    a,b,c=[int(x) for x in input().split()]
    route_list[a-1][b-1]=c
    route_list[b-1][a-1]=c

wa_list=warshall_floyd(route_list)
ans=30**9

for perm in permutations(r):
    #print(perm)
    cur = sum(wa_list[v][u] for v, u in zip(perm, perm[1:]))
    ans = min(ans, cur)

print(ans)

### FIXED CODE ###

import math
from itertools import permutations

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    n=len(d[0])
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

N,M,R=[int(x) for x in input().split()]
r=[int(x)-1 for x in input().split()]

route_list=[[10**9]*N for i in range(N)]

for i in range(M):
    a,b,c=[int(x) for x in input().split()]
    route_list[a-1][b-1]=c
    route_list[b-1][a-1]=c

wa_list=warshall_floyd(route_list)
ans=30**9

for perm in permutations(r):
    #print(perm)
    cur = sum(wa_list[v][u] for v, u in zip(perm, perm[1:]))
    ans = min(ans, cur)

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

import scipy as sp

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

tree = sp.array([], dtype = "int")
for i in range(N):
    tree = sp.append(tree, int(input()))

tree.sort()

print(int(min(tree[K-1:]-tree[:N-K+1])))


### FIXED CODE ###

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

tree = [int(input()) for i in range(N)]

tree.sort()

print(min(tree[i+K-1] - tree[i] for i in range(N-K+1)))
### BUGGY CODE ###

import math
N = int(input())


def calc(n):
    for x in range(1, math.ceil(math.sqrt(n))):
        for y in range(1, x+1):
            for z in range(1, y+1):
                ans = x ** 2 + y ** 2 + z ** 2 + x*y + y*z + z*x
                # print(x, y, z, ans)
                if ans == n:
                    if len({x, y, z}) == 1:
                        return 1
                    elif len({x, y, z}) == 2:
                        return 3
                    else:
                        return 6
                if ans > n:
                    break
    return 0

# print(calc(17))
for n in range(1, N + 1):
    res = calc(n)
    print(res)


### FIXED CODE ###

import math
N = int(input())

res = [0 for i in range(10 ** 4)]
for x in range(1, math.ceil(math.sqrt(10 ** 4))):
    for y in range(1, math.ceil(math.sqrt(10 ** 4))):
        for z in range(1, math.ceil(math.sqrt(10 ** 4))):
            ans = x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x
            if ans <= 10 ** 4:
                res[ans - 1] += 1

for n in range(N):
    print(res[n])
### BUGGY CODE ###

from scipy.sparse import lil_matrix

N = int(input())
edge = lil_matrix((N+1,N+1))

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

Q,K = map(int,input().split())

from scipy.sparse.csgraph import dijkstra
dist = dijkstra(edge,directed = False, indices = K).astype(int)

for _ in range(Q):
  x,y = map(int,input().split())
  print(dist[x] + dist[y])

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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

Q,K = map(int,input().split())

dist = [None]*(N+1)

def set_dist(x,d):
  dist[x] = d
  for y,dd in edge[x]:
    if dist[y] is not None:
      continue
    set_dist(y,d+dd)

set_dist(K,0)

for _ in range(Q):
  x,y = map(int,input().split())
  print(dist[x] + dist[y])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
from functools import lru_cache
sys.setrecursionlimit(10**6)
readline = sys.stdin.buffer.readline


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))



@lru_cache(maxsize=None)
def f(c1, c2, c3):
    if c1 == c2 == c3 == 0:
        return 0
    # if memo[c1][c2][c3] != -1:
    #     return memo[c1][c2][c3]
    c0 = N - (c1 + c2 + c3)
    p0 = c0 / N
    ip0 = 1 - p0
    ret = 1 / ip0
    if c1 > 0:
        p1 = c1 / N
        ret += f(c1-1, c2, c3) * p1 / ip0
    if c2 > 0:
        p2 = c2 / N
        ret += f(c1+1, c2-1, c3) * p2 / ip0
    if c3 > 0:
        p3 = c3 / N
        ret += f(c1, c2+1, c3-1) * p3 / ip0
    # memo[c1][c2][c3] = ret
    return ret


N = read_int()
A = read_int_n()
# memo = [[[-1] * (N + 1) for _ in range(N + 1)] for _ in range(N + 1)]
# memo[0][0][0] = 0
print(f(A.count(1), A.count(2), A.count(3)))


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.buffer.readline


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def f(c1, c2, c3):
    if memo[c1][c2][c3] != -1:
        return memo[c1][c2][c3]
    c0 = N - (c1 + c2 + c3)
    p0 = c0 / N
    ip0 = 1 - p0
    ret = 1 / ip0
    if c1 > 0:
        p1 = c1 / N
        ret += f(c1-1, c2, c3) * p1 / ip0
    if c2 > 0:
        p2 = c2 / N
        ret += f(c1+1, c2-1, c3) * p2 / ip0
    if c3 > 0:
        p3 = c3 / N
        ret += f(c1, c2+1, c3-1) * p3 / ip0
    memo[c1][c2][c3] = ret
    return ret


N = read_int()
A = read_int_n()
memo = [[[-1] * (N + 1) for _ in range(N + 1)] for _ in range(N + 1)]
memo[0][0][0] = 0
print(f(A.count(1), A.count(2), A.count(3)))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

s = input().rstrip()
n = int(input().rstrip())
q_list = [input().rstrip().split() for i in range(n)]
front = ''
back = ''
count = 1
for i in q_list:
    if i[0] == '1':
        count *= -1
    else:
        if i[1] == '1':
            if count == 1:
                front += i[2]
            else:
                back += i[2]
        else:
            if count == 1:
                back += i[2]
            else:
                front += i[2]
if count == 1:
    print(front[::-1] + s + back)
else:
    print(back[::-1] + s[::-1] + front)

### FIXED CODE ###

from collections import deque

s = deque(input())
n = int(input())
q_list = [input().split() for i in range(n)]
count = 1
for i in q_list:
    if i[0] == '1':
        count *= -1
    else:
        if i[1] == '1':
            if count == 1:
                s.appendleft(i[2])
            else:
                s.append(i[2])
        else:
            if count == 1:
                s.append(i[2])
            else:
                s.appendleft(i[2])
if count != 1:
    s.reverse()
print(*s, sep='')
### BUGGY CODE ###

from itertools import *
n=range(55555);a=list(n);a[1]=0
for i in range(2,233):a[i*2::i]=[0]*len(a[i*2::i])
p=list(compress(n,a))
for x in combinations(p,int(input())):
    for y in combinations(x,5):
        if sum(y)in p:break
    else:print(*x);exit()

### FIXED CODE ###

from itertools import *
n=range(55555);a=list(n);a[1]=0
for i in range(2,233):a[i*2::i]=[0]*len(a[i*2::i])
p=list(compress(n,a))

cnt = 0
ans = []
N = int(input())
for x in p:
    if x%5 == 2:
        ans += [x]
        cnt += 1
        if cnt == N: break
print(*ans)
### BUGGY CODE ###

import sys


def main():
    n = int(input())
    a = [int(i) for i in sys.stdin.readline().split()]
    ans = []
    ans_append = ans.append
    for i in range(n):
        ans_append(a.index(i + 1) + 1)
    print(*ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys


def main():
    n = int(input())
    a = [int(i) for i in sys.stdin.readline().split()]
    ans = [0] * n
    for i in range(n):
        ans[a[i] - 1] = i + 1
    print(*ans)


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

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

ans = 1
X = [-1]
for i in range(N):
    for j in range(ans):
        if X[j] < A[i]:
            X[j] = A[i]
            break
        elif j == ans - 1:
            X.append(A[i])
            ans += 1

print(ans)


### FIXED CODE ###

import bisect

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

ans = 1
X = [-A[0]]
for i in range(1,N):
    if -X[ans-1] >= A[i]:
        X.append(-A[i])
        ans += 1
    else:
        pos = bisect.bisect_right(X,-A[i])
        X[pos] = -A[i]

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

N = list(map(int, input().split()))[-1]
A = sorted(list(map(int, input().split())), reverse=True)[:N]
B = sorted(list(map(int, input().split())), reverse=True)[:N]
C = sorted(list(map(int, input().split())), reverse=True)[:N]

result = [A[i]+B[j]+C[k] 
          for i in range(len(A)) 
          for j in range(len(B)) 
          for k in range(len(C))
          if i+j+k <= N
         ]
  
result = sorted(result, reverse=True)
[print(result[i]) for i in range(N)]

### FIXED CODE ###

N = list(map(int, input().split()))[-1]
A = sorted(list(map(int, input().split())), reverse=True)[:N]
B = sorted(list(map(int, input().split())), reverse=True)[:N]
C = sorted(list(map(int, input().split())), reverse=True)[:N]

first = [i+j for i in A for j in B]
first = sorted(first, reverse=True)[:N]
second = [i+j for i in first for j in C]
result = sorted(second, reverse=True)[:N]

[print(i) for i in result]
### BUGGY CODE ###

N = int(input())
*A, = map(int, input().split())

d1 = [[0]*60 for _ in range(N+1)]
mod = 10**9+7

for i, n in enumerate(A, start=1):
    for j in range(60):
        d1[i][j] = d1[i-1][j] + ((n>>j)&1)

ans = 0
for i, n in enumerate(A, start=1):
    for j in range(60):
        a = d1[N][j]-d1[i][j] # 1
        if (n>>j)&1:
            a = N-a-i # 0

        ans += a*(1<<j)
        ans %= mod

print(ans)

### FIXED CODE ###

N = int(input())
*A, = map(int, input().split())

d1 = [[0]*60 for _ in range(N+1)]
mod = 10**9+7

for i, n in enumerate(A, start=1):
    for j in range(60):
        d1[i][j] = d1[i-1][j] + ((n>>j)&1)

ans = 0
for i, n in enumerate(A, start=1):
    for j in range(60):
        a = d1[N][j]-d1[i][j] # 1
        if (n>>j)&1:
            a = N-a-i # 0

        ans += a*(1<<j)
    ans %= mod

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

N, M = map(int, input().split())
ans = 1

S = M / N
S = int(S)
#print(S)
if N == 1:
    ans = M
else:
    for i in range(S, -1, -1):
        if M / i >= N:
            if M % i == 0:
                ans = i
                break


print(ans)


### FIXED CODE ###

N, M = map(int, input().split())
ans = 1

S = M / N
S = int(S)
#print(S)
import math
if N == 1:
    ans = M
else:
    not_sosu = -1
    for i in range(2, int(math.sqrt(M)) + 1):
        if M % i == 0:
            not_sosu = 1
            if M / i >= N and M % i == 0:
                ans = max(ans, i)
            j = M // i
            if M / j >= N and M % j == 0:
                ans = max(ans, j)
            #print(i)
    if not_sosu == -1:
        ans = 1


if N == 1:
    ans = M

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

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

while n>0:
    n=n-k
    
n1=abs(n)
n2=n+k
print(min(n1,n2))

### FIXED CODE ###

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


    
n1=n-(n//k)*k
n2=abs(n1-k)
print(min(n1,n2))
### BUGGY CODE ###

import copy
import time
import random

t1 = time.time()

def calc(T):
    res = 0
    L = [0]*26
    for i in range(D):
        res += S[i][T[i]-1]
        L[T[i]-1] = i+1
        for j in range(26):
            res -= C[j]*(i+1-L[j])
    return res
    
D = int(input())
C = [int(c) for c in input().split()]
S = [[int(s) for s in input().split()] for _ in range(D)]

T = [0]*D
for i in range(D):
    temp = -1
    for j in range(26):
        if temp < S[i][j]:
            temp = S[i][j]
            idx = j+1
    T[i] = idx

p = calc(T)

while time.time()-t1 < 1.9:
    i = random.randint(0, D-1)
    for j in range(26):
        temp = copy.deepcopy(T)
        temp[i] = j+1
        newp = calc(temp)
        if p < newp:
            T[i] = j+1
            p = newp

for t in T:
    print(t)

### FIXED CODE ###

D = int(input())
C = [int(c) for c in input().split()]
S = [[int(s) for s in input().split()] for _ in range(D)]

T = [0]*D
for i in range(D):
    temp = -1
    for j in range(26):
        if temp < S[i][j]:
            temp = S[i][j]
            idx = j+1
    T[i] = idx

for t in T:
    print(t)
### BUGGY CODE ###

import re
N, Q = map(int,input().split())
S = input()

for i in range(Q):
  l, r = map(int,input().split())
  Si = S[l-1:r]
  
  m = re.findall('AC',Si)
  if m != []:
    print(len(m))
  else:print(0)

### FIXED CODE ###

N, Q = map(int,input().split())
S = input()
t=[0]*(N+1)
for i in range(N):
  t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
for i in range(Q):
  l, r = map(int, input().split())
  print(t[r-1] - t[l-1])