Harryxun/stf_run huggingface dataset:
def lcs(x, y, pre_lcs, pre_lcs_len):
    rec = []
    idx = []
    for c in y:
        s = 0
        for i, k in enumerate(idx):
            t = x.find(c, s) + 1
            if t < 1:
                break
            if t < k:
                idx[i] = t
            s = k
        else:
            t = x.find(c, s) + 1
            if t:
                idx.append(t)
        rec.append(idx.copy())
    
    lcs_len = len(idx)
    if lcs_len > pre_lcs_len:
        lcs = ''
        pos = len(idx) - 1
        for line, yc in zip(rec[::-1], y[::-1]):
            i = line[pos] - 1
            xc = x[i]
            if xc == yc:
                lcs += xc
                if pos == 0:
                    return (lcs[::-1], lcs_len)
                pos -= 1
    else:
        return (pre_lcs, pre_lcs_len)

def solve():
    import sys
    file_input = sys.stdin
    ans_out = []
    for s in file_input:
        s = s.rstrip()
        if s == '#END':
            break
        s_len = len(s)
        sep = s_len // 2
        ans, ans_len = lcs(s[:sep], s[sep:], '', 0)
        sep = s_len - ans_len - 1
        while sep > ans_len:
            ans, ans_len = lcs(s[:sep], s[sep:], ans, ans_len)
            sep -= 1
        ans_out.append(ans)
    print(*ans_out, sep='\n')

solve()


### FIXED CODE ###

def lcs(x, y, pre_lcs, pre_lcs_len):
    pm = dict((zip('ABCDEFGHIJKLMNOPQRSTUVWXYZ', [0] * 26)))
    for c in pm:
        for i, xc in enumerate(x):
            if c == xc:
                pm[c] |= (1 << i)
    
    V = (1 << len(x)) - 1
    rec = []
    
    for yc in y:
        V = ((V + (V & pm[yc])) | (V & ~pm[yc]))
        rec.append(bin(V)[-len(x):])
    
    lcs_len = bin(V)[-len(x):].count('0')
    
    if lcs_len > pre_lcs_len:
        rx = x[::-1]
        lcs = ''
        idx = 0
        for v, yc in zip(rec[::-1], reversed(y)):
            idx = v.find('0', idx)
            if yc == rx[idx]:
                lcs += yc
                if len(lcs) == lcs_len:
                    return (lcs[::-1], lcs_len)
                idx += 1
    else:
        return (pre_lcs, pre_lcs_len)

from sys import stdin

def solve():
    file_input = stdin
    ans_out = []
    for s in file_input:
        s = s.rstrip()
        if s[0] == '#':
            break
        s_len = len(s)
        sep = s_len // 2
        ans, ans_len = lcs(s[:sep], s[sep:], '', 0)
        while sep > ans_len:
            ans, ans_len = lcs(s[:-sep], s[-sep:], ans, ans_len)
            sep -= 1
            ans, ans_len = lcs(s[:sep], s[sep:], ans, ans_len)
        ans_out.append(ans)
    print(*ans_out, sep='\n')

solve()
# -*- coding: utf-8 -*-

import sys
import math

def main():
  argNum = int(sys.argv[1])
  intRes = int(math.pow(argNum, 3))
  print(intRes)

if __name__ == '__main__':
  main()

### FIXED CODE ###

# -*- coding: utf-8 -*-

import math

def main():
  N = float(input())
  print(int(math.pow(N,3)))

if __name__ == '__main__':
  main()
n=int(input())
x=0
for i in range(n):
    a=int(input())
    cnt+=(a-1)%2
    cnt%=2
    x=max(a,x)
if x==1:
    print("first")
    if n%2==0:
        if cnt==0:
            print("second")
        else:
            print("first")
    else:
        if cnt==0:
            print("second")
        else:
            print("first")

### FIXED CODE ###

n=int(input())
cnt=0
for i in range(n):
    a=int(input())
    cnt+=(a%2)
if cnt==0:
    print("second")    
else:
    print("first")
import sys
import math
import functools
stdin = sys.stdin
mod = 10**9 + 7

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
sa = lambda h: [list(map(int, stdin.readline().split())) for i in range(h)]

h, n = na()
a, b = [], []
for _ in range(n):
    ai, bi = na()
    a.append(ai)
    b.append(bi)
inf = 10**9
dp = [[inf]* (10**4+1) for _ in range(n+1)]
for i in range(n):
    for j in range(1, 10**4+1):
        if j < a[i]:
            dp[i+1][j] = min(dp[i][j],((j-1)//a[i]+1)*b[i])
        else:
            dp[i+1][j] = min(dp[i][j],((j-1)//a[i]+1)*b[i], dp[i+1][j - a[i]] + b[i])
print(dp[n][h])



### FIXED CODE ###

import sys
import math
import functools
stdin = sys.stdin
mod = 10**9 + 7

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
sa = lambda h: [list(map(int, stdin.readline().split())) for i in range(h)]


h, a = na()
print((h-1)//a+1)
N, M = map(int, input().split(' '))

def fib(n):
    a, b = 0, 1
    for i in range(0, n):
        a, b = b, a + b
    return a

a_p = int(input())
sum = fib(a_p)
for i in range(M-1):
    a = int(input())
    diff = a - a_p
    if diff == 1:
        print('0')
        exit()
    sum *= fib((diff-1)%1000000007)
    sum %= 1000000007
    a_p = a

if (N - a_p == 1):
    print('0')
    exit()

sum *= fib(N - a_p)
sum %= 1000000007
print(sum)


### FIXED CODE ###

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

MOD = 1000000007

def fib(n):
    a, b = 0, 1
    for i in range(0, n):
        a, b = b, a + b
    return a

broken_step = []
p_a = -1
for i in range(M):
    a = int(input())
    if (a - p_a == 1):
        print("0")
        exit()
    else:
        p_a = a
    broken_step.append(a-1)

count_0 = 0
count_1 = 1
next_broken = 0
pre_is_broken = False
for i in range(N):
    if (next_broken >= len(broken_step) or i != broken_step[next_broken]):
        if (pre_is_broken):
            count_0 = 0
            pre_is_broken = False
        else:
            count_0, count_1 = count_1, count_0 + count_1
            count_0 %= MOD
            count_1 %= MOD
    else:
        next_broken+=1
        count_0 = 0
        pre_is_broken = True

print(count_1)
a, s, d, f = map(int, input().split())
print(min(a, s)+min(d, f))


### FIXED CODE ###

x = [int(input()) for i in range(4)]
print(min(x[0], x[1])+min(x[2], x[3]))
H, N = map(int, input().split())
A_list = list(map(int, input().split()))
A_list = quicksort(A_list)
#A_list.reverse()
for i in range(N):
    H -= A_list[i]
if H > 0:
    print("No")
else:
    print("Yes")

### FIXED CODE ###

H, N = map(int, input().split())
A_list = list(map(int, input().split()))
for i in range(N):
    H -= A_list[i]
if H > 0:
    print("No")
else:
    print("Yes")
S, T = map(int, input().split())
print(~-S*~-T)

### FIXED CODE ###

X, t = map(int, input().split())
print((X-1)*(t-1))
import math
def factorize(n):
    if n == 1:
        return [1]
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

def isPrime(n):
    if n == 1:
        return False
    else:
        for i in range(2, int(math.sqrt(n)) + 1):
           if n%i == 0:
               return False
        return True


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

if p == 1:
    print(1)
    exit()

if n == 1 or isPrime(p):
    print(p)
    exit()

f = factorize(p)
cnt = [0] * (max(f) + 1)
# print(f)

for _f in f:
    cnt[_f] += 1

ans = 1
# print(cnt)

for i in range(len(cnt)):
    if cnt[i] >= n:
        loop = cnt[i]//n
        for j in range(loop):
            ans *= i

print(ans)

### FIXED CODE ###

import math
# 素因数分解
def factorize(n):
    if n == 1:
        return [1]
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

def f(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 素数判定
def isPrime(n):
    if n == 1:
        return False
    else:
        for i in range(2, int(math.sqrt(n)) + 1):
           if n%i == 0:
               return False
        return True


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

if n == 1 or isPrime(p):
    print(p)
    exit()

# f = factorize(p)
# cnt = [0] * (max(f) + 1)
# # print(f)

# for _f in f:
#     cnt[_f] += 1

# ans = 1
# # print(cnt)

# for i in range(len(cnt)):
#     if cnt[i] >= n:
#         loop = cnt[i]//n
#         for j in range(loop):
#             ans *= i

# print(ans)

f = f(p)
ans = 1

for i in range(len(f)):
    ans *= f[i][0] ** (f[i][1] // n)

print(ans)
def margin0(n):
    if n < 10:
        return "00{}".format(n)
    elif n < 100:
        return "0{}".fomrat(n)
    elif n < 1000:
        return "".format(n%1000)
    else:
        return "{}".format(n%1000 - 1)
n = int(input())
# print(n)
name = ""
if n < 1000:
    name = "ABC{}".format(margin0(n))
else:
    name = "ABD{}".format(margin0(n))
print(name)

### FIXED CODE ###

# -*- coding: utf-8 -*-
def margin0(n):
    if n < 10:
        return "00{}".format(n)
    elif n < 100:
        return "0{}".format(n)
    elif n < 1000:
        return "".format(n%1000)
    else:
        return "{}".format(n%1000 - 1)
n = int(input())
# print(n)
name = ""
if n < 1000:
    name = "ABC{}".format(margin0(n))
else:
    name = "ABD{}".format(margin0(n))
print(name[:3])
s = input()
l = len(input())
print('x'*l)

### FIXED CODE ###

l = len(input())
print('x'*l)
a, b, c = map(int, input().split().split())
if  b−a=c−b:
  print ("YES")
elif print("NO")

### FIXED CODE ###

a,b,c = map(int,input().split())
if b-a == c-b:
    print("YES")
else:
    print("NO")
N = int(input())
le = [int(input()) for i in range(N)]
le.sort()#昇順
#３数以上の最小公倍数を求める問題
#a,b2数の最小公倍数とcの最小公倍数で求められる
#２数の最小公倍数はユークリッドの互除法を利用して再帰関数で求められる。

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


def LCM(a,b):
    return int(a*b/GCD(a,b))

def multi_LCM(le):
    if len(le)==1:
        return 
    mxle=le[-1]
    del(le[-1])
    le[-1]=LCM(le[-1],mxle)
    multi_LCM(le)

if(len(le)==2):
    le[0]=LCM(le[0],le[1])
if(len(le)>=2):
    multi_LCM(le)

print(le[0])


### FIXED CODE ###

N = int(input())
le = [int(input()) for i in range(N)]
le.sort()#昇順
#３数以上の最小公倍数を求める問題
#a,b2数の最小公倍数とcの最小公倍数で求められる
#２数の最小公倍数はユークリッドの互除法を利用して再帰関数で求められる。

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


def LCM(a,b):
    return int(a*b//GCD(a,b))

def multi_LCM(le):
    # print(le)
    if len(le)==1:
        return
    mxle=le[-1]
    del(le[-1])
    le[-1]=LCM(le[-1],mxle)
    multi_LCM(le)

if(len(le)==2):
    le[0]=LCM(le[0],le[1])
if(len(le)>=2):
    multi_LCM(le)

print(le[0])
h , a = map(int, input().split())

ans = h // a
if h % a == 0:
    print(ans)
esle:
    print(ans + 1)

### FIXED CODE ###

h , a = map(int, input().split())

ans = h // a
if h % a == 0:
    print(ans)
else:
    print(ans + 1)
n = int(input())
a = [int(aa) for aa in input().split()]

def add_entry(hist, aa):
    if aa in hist:
        hist[aa] += 1
    else:
        hist[aa] = 1


def make_hist(a):
    even_hist = {}
    odd_hist = {}

    for i in range(len(a)//2):
        add_entry(even_hist, a[2*i])
        add_entry(odd_hist, a[2*i+1])

    return even_hist, odd_hist


def get_sorted_hist(hist):
    return sorted(hist.items(), key=lambda x: -x[0])


eh, oh = make_hist(a)
seh = get_sorted_hist(eh)
soh = get_sorted_hist(oh)

if seh[0][0] != soh[0][0]
    print(len(a) - seh[0][1] - soh[0][1])
else:
    if seh[0][1] >= soh[0][1]:
        print(len(a) - seh[0][1] - soh[1][1])
    else:
        print(len(a) - seh[1][1] - soh[0][1])


### FIXED CODE ###

n = int(input())
a = [int(aa) for aa in input().split()]

def add_entry(hist, aa):
    if aa in hist:
        hist[aa] += 1
    else:
        hist[aa] = 1


def make_hist(a):
    even_hist = {}
    odd_hist = {}

    for i in range(len(a)//2):
        add_entry(even_hist, a[2*i])
        add_entry(odd_hist, a[2*i+1])

    return even_hist, odd_hist


def get_sorted_hist(hist):
    return sorted(hist.items(), key=lambda x: -x[1])

eh, oh = make_hist(a)
seh = get_sorted_hist(eh)
soh = get_sorted_hist(oh)


if seh[0][0] != soh[0][0]:
    print(len(a) - seh[0][1] - soh[0][1])
else:
    if len(seh) == 1 and len(soh) == 1:
        print(len(a)//2)
    elif len(seh) == 1:
        print(len(a) - seh[0][1] - soh[1][1])
    elif len(soh) == 1:
        print(len(a) - soh[0][1] - seh[1][1])
    else:
        print(min(len(a) - seh[0][1] - soh[1][1], len(a) - soh[0][1] - seh[1][1]))
import math
import collections
import fractions
import itertools
import functools
import operator

def ncr(n, r):
    r = min(r, n-r)
    numer = functools.reduce(operator.mul, range(n, n-r, -1), 1)
    denom = functools.reduce(operator.mul, range(1, r+1), 1)
    return numer / denom

def solve():
    n, k = map(int, input().split())
    for i in range(1,k+1):
        ans = ncr(k-1, i-1) * ncr((n-k)+1, i)
        print(int(ans))
    return 0

if __name__ == "__main__":
    solve()


### FIXED CODE ###

import math
import collections
import fractions
import itertools
import functools
import operator

def ncr(n, r):
    if n < r: return 0
    r = min(r, n-r)
    if r == 0:
        return 1
    numer = functools.reduce(operator.mul, range(n, n-r, -1), 1)
    denom = functools.reduce(operator.mul, range(1, r+1), 1)
    return numer // denom % (10 ** 9 + 7)

def solve():
    n, k = map(int, input().split())
    for i in range(1,k+1):
        ans = (ncr(k-1, i-1) * ncr(n-k+1, i)) % (10**9+7)
        print(int(ans))
    return 0

if __name__ == "__main__":
    solve()
n=int(input())
s=[input() for _ in range(n)]
m=int(input())
t=[input() for _ in range(m)]
l=list( set(s) )
maxbox=[]
for i in range( len(l) ):
    maxbox.append( int( s.count(l[i])-t.count(l[i]) ) ) 
print(max(maxbox,0))

### FIXED CODE ###

n=int(input())
s=[input() for _ in range(n)]
m=int(input())
t=[input() for _ in range(m)]
l=list( set(s) )
maxbox=[]
for i in range( len(l) ):
    maxbox.append( int( s.count(l[i])-t.count(l[i]) ) ) 
maxbox.append(0)
print(max(maxbox))
n = int(input())
tree = [[] for i in range(n + 1)]
for i in range(n - 1):
    a, b, c = map(int, input().split())
    tree[a].append((b, c))
    tree[b].append((a, c))

depth = [0] * (n + 1)
def dfs(v, p, d):
    depth[v] = d
    for to, cost in tree[v]:
        if to != p:
            dfs(to, v, d + cost)

q, k = map(int, input().split())
dfs(k, 0, 0)
xy = [tuple(map(int, input().split())) for i in range(q)]

for x, y in xy:
    print(depth[x] + depth[y])


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

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

depth = [0] * (n + 1)
def dfs(v, p, d):
    depth[v] = d
    for to, cost in tree[v]:
        if to != p:
            dfs(to, v, d + cost)

q, k = map(int, input().split())
dfs(k, 0, 0)
xy = [tuple(map(int, input().split())) for i in range(q)]

for x, y in xy:
    print(depth[x] + depth[y])
N, M = map(int, input().split())
a_n = list(map(int, input().split()))
a_n = [int(a_n[i]*1/2) for i in range(len(a_n))]
 
def lcm(lis):
    from fractions import gcd
    x = lis[0]
    for i in range(1, len(lis)):
        x = (x * lis[i]) // gcd(x, lis[i])
    return x
res = lcm(a_n)
count = 0
for i in range(len(M)):
  count += 1
  if res*(2*i + 1) > M:
    break
print(count)

### FIXED CODE ###

N,M = map(int, input().split())
a_n = list(map(int, input().split()))
g = a_n.copy()
 
while not any(x%2 for x in g): g = [x//2 for x in g]
if not all(x%2 for x in g): print(0); exit(0)
def gcd(a,b):
  while b: a,b = b,a%b
  return a
lcm = lambda a,b: a*b//gcd(a,b)
tot = 1
for x in a_n: tot = lcm(tot,x//2)
print((M//tot+1)//2)
#!/usr/bin/env python3
import sys
import collections

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, Y = map(int, readline().split())
assert Y % 1000 == 0
Y //= 1000


def solve2():
    for x1 in range(N + 1):
        for x2 in range(N - x1 + 1):
            x3 = N - x1 - x2
            if 10 * x1 + 5 * x2 + 1 * x3 == Y:
                print(x1, x2, x3)
                return
    print(-1, -1, -1)


def solve():
    path = [[None] * (Y + 1) for _ in range(N + 1)]
    path[0][0] = -1
    for i in range(1, N + 1):
        for y in range(Y + 1):
            if path[i - 1][y] is None:
                continue
            for b in [1, 5, 10]:
                if y + b > Y:
                    continue
                path[i][y + b] = b

    if path[N][Y] is None:
        print(-1, -1, -1)
        return
    res = collections.Counter()
    m = Y
    for i in range(N, 0, -1):
        b = path[i][m]
        # print(f"path[{i}][{m}] ={b}", file=sys.stderr)
        if b is None:
            raise ValueError(f"path[{i}][{m}] is None")
        res[b] += 1
        m -= b
    print(res[10], res[5], res[1])


if __name__ == "__main__":
    solve2()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import collections

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, Y = map(int, readline().split())
assert Y % 1000 == 0
Y //= 1000


def solve2():
    for x1 in range(N + 1):
        for x2 in range(N - x1 + 1):
            x3 = N - x1 - x2
            if 10 * x1 + 5 * x2 + 1 * x3 == Y:
                print(x1, x2, x3)
                return
    print(-1, -1, -1)



if __name__ == "__main__":
    solve2()
import math
from functools import reduce
import copy

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

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

ans = 0
for i in range(n-1):
    tmp_list = copy.copy(a_list)
    tmp_list.pop(i)
    #print(tmp_list)
    tmp = gcd(*tmp_list)
    #print(tmp)
    if tmp > ans:
        ans = tmp
    
print(ans)


### FIXED CODE ###

from fractions import gcd
import copy

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

ans_list = []
l_list = [0]*(n+1)
r_list = [0]*(n+1)

for i in range(n):
    l_list[i+1] = gcd(l_list[i], a_list[i])
    r_list[n-i-1] = gcd(r_list[n-i], a_list[n-i-1])

ans_list = []
for j in range(n):
    ans_list.append(gcd(l_list[j], r_list[j+1]))

#print(ans_list)

print(max(ans_list))
#!/usr/bin/env python
# coding: utf-8

# In[31]:


import sys
input = sys.stdin.readline
N, M = map(int, input().split())
A = list(map(int, input().split()))
bcs = [list(map(int, input().split())) for i in range(M)]
"""
3 2
5 1 4
2 3
1 5
"""


# In[32]:


#print(N, M)
#print(A)
#print(bcs)


# In[33]:


def binary_search(nbs, tar):
    ln = 0
    rn = len(nbs)-1
    t = int(len(nbs)/2)
    
    while ln<=rn:
        comp = nbs[t]
        if tar >= comp and tar<nbs[t+1]:
            break
        elif tar >= comp: # 今の値がtar以下であれば、
            ln = t + 1 # 左端をt+1に更新
        elif tar < comp: # 今の値が
            rn = t - 1 # 右端をt-1に更新
        t = int((ln+rn)/2)
    return t


# In[34]:


bcs = sorted(bcs, key=lambda x:x[1], reverse=True)
nb = 0
A = sorted(A)
#print(A)
#print(bcs)
for i in range(M):
    B, C = bcs[i]
    #print(B, C, nb)
    if A[nb] >= C:
        continue
    if A[nb+B-1] < C: #もしB個目が、Cより小さければ、B個目までをCにする
        A[nb:nb+B] = [C]*B
        nb += B
        continue
    t = binary_search(A[nb:nb+B], C)
    A[nb:nb+t] = [C]*t
    nb += t
#print(A)
print(sum(A))


# In[ ]:






### FIXED CODE ###

#!/usr/bin/env python
# coding: utf-8

# In[1]:


import sys
input = sys.stdin.readline
N, M = map(int, input().split())
A = list(map(int, input().split()))
bcs = [list(map(int, input().split())) for i in range(M)]


# In[14]:


"""
def binary_search(nbs, tar):
    #print(nbs, tar)
    ln = 0
    rn = len(nbs)-1
    t = int(len(nbs)/2)
    
    while ln < rn:
        comp = nbs[t]
        if tar >= comp and tar<nbs[t+1]:
            break
        elif tar >= comp: # 今の値がtar以下であれば、
            ln = t + 1 # 左端をt+1に更新
        elif tar < comp: # 今の値がtarより大きければ、
            rn = t - 1 # 右端をt-1に更新
        t = int((ln+rn)/2)
    return t
"""


# In[16]:


sbcs = sorted(bcs, key=lambda x:x[1], reverse=True)
sA = sorted(A)

nb = 0
ans = 0
is_finish = False

for i in range(M):
    B, C = sbcs[i]
    
    for j in range(B):
        if nb < N and sA[nb] < C:
            ans += C
            nb += 1
        else:
            is_finish = True
            break
    
    if is_finish:
        break

if nb < N:
    ans += sum(sA[nb:])

print(ans)
        
"""
    if nb >= N: # nbがN以上になれば、終了
        break
    
    B, C = sbcs[i]
    las = nb+B-1
    las = las if las <N else N-1
    if sA[nb] >= C: # もしnb個目がC以上であれば、終了
        break
    elif sA[nb+B-1] <= C: #もしB個目が、C以下なら、B個目までをCにする
        sA[nb:nb+B] = [C]*B
        nb += B
    else: #nb個目がC未満で、nb+B-1個目がCより大きければ
        t = binary_search(sA[nb:nb+B], C) 
        t = t if nb+t < N else N-nb-1
        sA[nb:nb+t+1] = [C]*(t+1)
        nb += t+1
    
print(sum(sA))
"""


# In[ ]:
N, M, Q = map(int, input().split())
tmp = [list(map(int, input().split())) for i in range(Q)]


#最初に全てのAペアを作ればいいだけだった
#1stepで何するか
#終了条件
ans = [0]
def dfs(A):
    if len(A) == N:
        tmp_ans = 0
        for ele in tmp
            if ele[1] - ele[0] == ele[2]:
                tmp_ans += ele[-1]
        ans[0] = max(tmp_ans,ans[0])

        return
    
    A_min = A[-1]
    while(1):
        if A_min > M:
            break
        A.append(A_min)
        dfs(A)
        A.pop()
        A_min += 1

for i in range(M):
    dfs([i+1])

print(ans[0])



### FIXED CODE ###

N, M, Q = map(int, input().split())
tmp = [list(map(int, input().split())) for i in range(Q)]


#最初に全てのAペアを作ればいいだけだった
#1stepで何するか
#終了条件
ans = [0]
def dfs(A):
    # print(A)
    if len(A) == N:
        tmp_ans = 0
        for ele in tmp:
            if A[ele[1]-1] - A[ele[0]-1] == ele[2]:
                tmp_ans += ele[-1]
        ans[0] = max(tmp_ans,ans[0])

        return
    
    A_min = A[-1]
    while(1):
        if A_min > M:
            break
        A.append(A_min)
        dfs(A)
        A.pop()
        A_min += 1

for i in range(M):
    dfs([i+1])

print(ans[0])
a,b,c = map(int,input().split())
k = int(input())
count = 0
while A >= B:
  count += 1
  B *= 2
while B >= C:
  count += 1
  C *= 2
return(['No','Yes'][count<=k])

### FIXED CODE ###

a,b,c = map(int,input().split())
k = int(input())
count = 0
while a >= b:
  count += 1
  b *= 2
while b >= c:
  count += 1
  c *= 2
print(['No','Yes'][count<=k])
import itertools
N=int(input())
F = [list(map(int, input().split())) for i in range(N)]
P = [list(map(int, input().split())) for i in range(N)]

store_str=list(product('01', repeat=10))
store=[[int(i) for i in j] for j in store_str]
store.pop(0)
all_sum=[]
for s in store:#joiの店をあけられる時間帯の組み合わせ
    value_list=[]
    for i,j in zip(F,P): #i番目の店の開いている時間帯のリスト
        l=len([1 for a,b in zip(s,i) if a==1 and b==1])
        value_list.append(j[l])
    value_sum=sum(value_list)
    all_sum.append(value_sum)
print(max(all_sum))

### FIXED CODE ###

from itertools import product
N=int(input())
F = [list(map(int, input().split())) for i in range(N)]
P = [list(map(int, input().split())) for i in range(N)]
store_str=list(product('01', repeat=10))
store=[[int(i) for i in j] for j in store_str]
store.pop(0)
all_sum=[]
for s in store:
    value_list=[]
    for i,j in zip(F,P): 
        l=len([1 for a,b in zip(s,i) if a==1 and b==1])
        value_list.append(j[l])
    value_sum=sum(value_list)
    all_sum.append(value_sum)
print(max(all_sum))
N = int(input())
A=[int(x) for x in input().split()]
k=0
if N==1:
    print("OK")
else:
     if A[0]//int(N) == A[1]//int(N) and A[0]%int(N)==A[1]%int(N) and A[0]%int(N)==0 :
        print("OK")
    elif A[0]//int(N) != A[1]//int(N) and A[0]%int(N)!=0 :
        print("OK")
     else:
        print("NG")


### FIXED CODE ###

N = int(input())
A=[int(x) for x in input().split()]
k=0
if N==1:
    print("OK")
else:
     if A[0]//int(N) == A[1]//int(N)  and A[0]%int(N)!=0  and A[1]%int(N)!=0:
        print("NG")
     else:
         print("OK")
n, k = map(int, input().split())

def func(n, k):
    if n == k:
        return print(0)
    elif n > k:
        if n % k == 0:
            return print(0)
        else:
            func(n%k, k)
    else:
        if k % n == 0:
            print((k-n)//n)
        else:
            print(k//n)

func(n, k)

### FIXED CODE ###

n, k = map(int, input().split())
m = n%k
print(min(m, abs(m-k)))