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

import sys
import numpy as np
import itertools
import math
input = lambda: sys.stdin.readline().rstrip()

def main():
    n = int(input())
    loc = [list(map(int,input().split())) for _ in range(n)]
    arr = np.array(list(itertools.permutations(loc)))
    p = math.factorial(n)
    dis = np.zeros(p)
    for i in range(p):
        for j in range(n-1):
            dis[i] += np.linalg.norm(arr[i][j+1]-arr[i][j])
    print(dis.mean())
    
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
import itertools
import math
input = lambda: sys.stdin.readline().rstrip()

def main():
    n = int(input())
    loc = [list(map(int,input().split())) for _ in range(n)]
    arr = list(itertools.permutations(loc))
    p = math.factorial(n)
    dis = 0
    for i in range(p):
        for j in range(n-1):
            dis += math.sqrt((arr[i][j+1][1]-arr[i][j][1])**2+(arr[i][j+1][0]-arr[i][j][0])**2)
    print(dis/p)
    
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    import bisect
    from collections import deque
    from copy import deepcopy

    n = int(input())
    l = list(map(int,input().split()))
    e = [[] for i in range(n)]
    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 = [[False] for i in range(n)]
    dp[0] = [l[0]]
    
    q = deque([])
    q.append(0)
    while q:
        now = q.popleft()

        for nex in e[now]:
            if dp[nex] == [False]:
                dp[nex] = deepcopy(dp[now])
                if l[nex] > dp[nex][-1]:
                        dp[nex].append(l[nex])
                else:
                    dp[nex][bisect.bisect_left(dp[nex], l[nex])] = l[nex]
                q.append(nex)
    
    for i in dp:
        print(len(i))
if __name__ == "__main__":
    main()

### FIXED CODE ###


import sys
input = sys.stdin.readline
import bisect

sys.setrecursionlimit(10**7)
n = int(input())
l = list(map(int,input().split()))
e = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    e[a].append(b)
    e[b].append(a)


ans = [0]*n
ans[0] = 1
dp = [l[0]]

def dfs(now,bef):
    
    change = True
    if l[now] > dp[-1]:
        dp.append(l[now])
    else:
        index = bisect.bisect_left(dp,l[now])
        change = False
        s = dp[index]
        dp[index] = l[now] 
    ans[now] = len(dp)
    
    for nex in e[now]:
        if nex != bef:
            dfs(nex,now)
    if change:
        dp.pop()
    else:
        dp[index] = s 

for i in e[0]:
    dfs(i,0)

for i in ans:
    print(i)
### BUGGY CODE ###

import numpy as np
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
h = np.array([int(x) for x in input().split()])
dp = np.zeros(N)
for i in range(1, N):
  j = max(0, i-K)
  dp[i] = min(dp[j:i]+np.abs(h[i]-h[j:i]))
print(int(dp[N-1]))

### FIXED CODE ###

import sys
import numpy as np

# inputを高速化する。
input = sys.stdin.readline

n, k = map(int, input().split())
h = [int(i) for i in input().split()]

# dpの配列を作る。
dp = np.zeros(n, dtype=int)
# hの配列を作る。
h = np.array(h)


for i in range(1, n):
    # start は負になることはない。
    start = max(0, i-k)
    # 行列として足し算できるのでforを使う必要がない。
    dp[i] = min(dp[start: i] + np.abs(h[i] - h[start: i]))

print(dp[n-1])
### BUGGY CODE ###

import sys


def resolve():
    def max2(a: int, b: int):
        """
        入力された2つの整数a,bの大きいほうを返す
        Parameters
        ----------
        a, b : int
            比較したい整数
        Returns
        -------
        a or b : int
            大きいほうの整数
        """
        if a >= b:
            return a
        else:
            return b
    
    readline = sys.stdin.readline

    s = readline()
    t = readline()
    
    # 配るDP
    # dp[i + 1][j + 1]はsのi文字目までとtのj文字目までのLCSの長さ
    # LCS=最長共通部分列問題
    dp = [[0] * (len(t) + 1) for _ in [0] * (len(s) + 1)]

    for i in range(len(s)):
        for j in range(len(t)):
            if s[i] == t[j]:
                dp[i + 1][j + 1] = max2(dp[i + 1][j + 1], dp[i][j] + 1)
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1],
                                   dp[i + 1][j],
                                   dp[i][j + 1])

    # LCSを求めたDPから部分文字列を復元
    res = ''
    i, j = len(s), len(t)
    while i > 0 and j > 0:
        if dp[i][j] == dp[i - 1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j - 1]:
            j -= 1
        else:
            res += s[i - 1]
            i -= 1
            j -= 1
    print(res[::-1])


resolve()


### FIXED CODE ###

def resolve():
    import sys
    def max2(a: int, b: int):
        """
        入力された2つの整数a,bの大きいほうを返す
        Parameters
        ----------
        a, b : int
            比較したい整数
        Returns
        -------
        a or b : int
            大きいほうの整数
        """
        if a >= b:
            return a
        else:
            return b
    
    readline = sys.stdin.readline
 
    s = readline()
    t = readline()
 
    # 配るDP
    # dp[i + 1][j + 1]はsのi文字目までとtのj文字目までのLCSの長さ
    # LCS=最長共通部分列問題
    dp = [[0] * (len(t) + 1) for _ in [0] * (len(s) + 1)]
 
    for i in range(len(s)):
        for j in range(len(t)):
            if s[i] == t[j]:
                dp[i + 1][j + 1] = max2(dp[i + 1][j + 1], dp[i][j] + 1)
            dp[i + 1][j + 1] = max2(dp[i + 1][j + 1], dp[i + 1][j])
            dp[i + 1][j + 1] = max2(dp[i + 1][j + 1], dp[i][j + 1])
 
    # LCSを求めたDPから部分文字列を復元
    res = []
    i, j = len(s), len(t)
    while i > 0 and j > 0:
        if dp[i][j] == dp[i - 1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j - 1]:
            j -= 1
        else:
            res.append(s[i - 1])
            i -= 1
            j -= 1
    print(''.join(res[::-1]))
 
 
resolve()
### BUGGY CODE ###

n = int(input())
p = list(map(int, input().split()))
cnt = 0
for i in range(n):
    if all(map(lambda pj: p[i] <= pj, p[:i + 1])):
        cnt += 1
print(cnt)

### FIXED CODE ###

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

cnt = 0
pjmin = P[0]
for pi in P:
    if pi <= pjmin:
        cnt +=1
        pjmin = pi
        if pi ==1:
            break
print(cnt)
### BUGGY CODE ###

n = int(input())
x = [int(x) for x in list(input())]
lx = len(x)-1

xx = 0
xx_cnt = 0
for i, y in enumerate(x):
    xx += (1 << (lx-i))*y
    if y == 1:
        xx_cnt += 1

for i in range(n):
    if x[i] == 0:
        val = xx + (1 << (lx-i))*1
        cnt = xx_cnt + 1
    else:
        val = xx - (1 << (lx-i))*1
        cnt = xx_cnt - 1

    ans = 0
    if val == 0:
        print(ans)
    else:
        while val > 0:
            ans += 1
            val = val % cnt
            tmp = val % cnt
            cnt = 0
            while tmp > 0:
                if tmp & 1:
                    cnt += 1
                    tmp = (tmp-1) // 2
                else:
                    tmp = tmp // 2
        print(ans)


### FIXED CODE ###

n = int(input())
x = [int(x) for x in list(input())]

x_cnt = 0
for i, y in enumerate(x):
    if y == 1:
        x_cnt += 1

aa = x_cnt + 1
bb = x_cnt - 1

a = [1 % aa]
if bb > 0:
    b = [1 % bb]
else:
    bb = 1
    b = [0]

for _ in range(n-1):
    a.append(a[-1]*2 % aa)
    b.append(b[-1]*2 % bb)

a = a[::-1]
b = b[::-1]

x_ps = 0
x_ng = 0
for i, val in enumerate(x):
    if val == 1:
        x_ps += a[i]
        x_ng += b[i]

for i in range(n):
    ans = 0
    if x[i] == 0:
        cnt = x_cnt + 1
        val = (x_ps + a[i]) % cnt
    else:
        cnt = x_cnt - 1
        if cnt == 0:
            print(ans)
            continue
        val = (x_ng - b[i]) % cnt
    ans += 1

    tmp = val
    cnt = 0
    while tmp > 0:
        if tmp & 1:
            cnt += 1
            tmp = (tmp-1) // 2
        else:
            tmp = tmp // 2

    if cnt == 0:
        print(ans)
        continue

    while val > 0:
        ans += 1
        val = val % cnt
        tmp = val % cnt
        cnt = 0
        while tmp > 0:
            if tmp & 1:
                cnt += 1
                tmp = (tmp-1) // 2
            else:
                tmp = tmp // 2
    print(ans)
### BUGGY CODE ###

import numpy as np

n, d, a = map(int, input().split())
lst = []
for i in range(n):
    xi, hi = map(int, input().split())
    if hi % a == 0:
        hi = hi // a
    else:
        hi = hi // a + 1
    lst.append([xi, hi])
lst.sort(key=lambda x: x[0])
x, h = [], []
for i in range(n):
    x.append(lst[i][0])
    h.append(lst[i][1])

x.append(10**11)
h.append(0)

h = np.array(h)

kougeki_start = 0
kougeki_end = 0
cnt = 0
for i in range(n):
    if h[i] > 0:
        j = i + 1
        while x[j] - x[i] <= 2*d:
            j += 1
        j -= 1
        cnt += h[i]
        h[i:j+1] -= h[i]

print(cnt)

### FIXED CODE ###

n, d, a = map(int, input().split())
lst = []
for i in range(n):
    xi, hi = map(int, input().split())
    if hi % a == 0:
        hi = hi // a
    else:
        hi = hi // a + 1
    lst.append([xi, hi])
lst.sort(key=lambda x: x[0])
x, h = [], []
for i in range(n):
    x.append(lst[i][0])
    h.append(lst[i][1])

x.append(10**11)
h.append(0)

# 攻撃に巻き込めるインデックスを求める
left = 0 # 可能
right = n # 不可能
while left+1 < right:
    mid = (left + right) // 2
    if x[mid] - x[0] <= 2*d:
        left = mid
    else:
        right = mid
makikomi = [left]
right = left
for i in range(1, n):
    while x[right] - x[i] <= 2*d:
        right += 1
    right -= 1
    makikomi.append(right)

cnt = [0 for i in range(n)]
left = 0
already = 0
for i in range(n):
    while x[makikomi[left]] < x[i]:
        already -= cnt[left]
        left += 1
    cnt[i] = max(h[i] - already, 0)
    already += cnt[i]

print(sum(cnt))
### BUGGY CODE ###

from collections import deque
from collections import defaultdict


class Graph(object):
    """
    隣接リストによる無向グラフ
    重み無しで距離は１
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst):
        self.graph[src].append(dst)
        self.graph[dst].append(src)

    def get_nodes(self):
        return self.graph.keys()


if __name__ == "__main__":
    n, x, y = map(int, input().split())
    x -= 1
    y -= 1

    g = Graph()
    for i in range(n-1):
        g.add_edge(i, i+1)
    g.add_edge(x, y)

    ans = [0] * (n-1)

    # BFSによる解法
    for i in range(n-1):
        # 始点からの距離
        # -1を未訪問とする
        dist = [-1] * n

        # 初期条件
        # 今回は頂点iから探索を行う
        dist[i] = 0
        que = deque([i])

        while len(que) != 0:
            vertex = que.popleft()
            for v in g.graph[vertex]:
                if dist[v] != -1:
                    pass
                else:
                    tmp = dist[vertex] + 1
                    dist[v] = tmp
                    if v > i:
                        ans[tmp-1] += 1
                    que.extend(g.graph[vertex])

    for a in ans:
        print(a)


### FIXED CODE ###

from collections import deque
from collections import defaultdict


class Graph(object):
    """
    隣接リストによる無向グラフ
    重み無しで距離は１
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst):
        self.graph[src].append(dst)
        self.graph[dst].append(src)

    def get_nodes(self):
        return self.graph.keys()


if __name__ == "__main__":
    n, x, y = map(int, input().split())
    x -= 1
    y -= 1

    g = Graph()
    for i in range(n-1):
        g.add_edge(i, i+1)
    g.add_edge(x, y)

    ans = [0] * (n-1)

    # BFSによる解法
    for i in range(n-1):
        # 始点からの距離
        # -1を未訪問とする
        dist = [-1] * n

        # 初期条件
        # 今回は頂点iから探索を行う
        dist[i] = 0
        que = deque([i])

        while len(que) != 0:
            vertex = que.popleft()
            for v in g.graph[vertex]:
                if dist[v] != -1:
                    pass
                else:
                    tmp = dist[vertex] + 1
                    dist[v] = tmp
                    if v > i:
                        ans[tmp-1] += 1
                    que.extend(g.graph[vertex])

    for a in ans:
        print(a)
### BUGGY CODE ###

#また、50ぷんはかかった、しかもTLE
#マジで死にたくなってくる
import copy
import fractions
from functools import reduce

n=int(input())
a1=[int(i) for i in input().split()]
#高階関数reduce
def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

#def gcd_list(numbers):
#    nul = numbers[0]
#    for i in range(1, len(numbers)):
#        nul = fractions.gcd(nul, numbers[i])
#    return nul

c=1

for i in range(n):
    a2=copy.deepcopy(a1)
    a2.pop(i)
    c=max([c,gcd_list(a2)])
print(c)


### FIXED CODE ###

import fractions
from functools import reduce

n=int(input())
a1=[int(i) for i in input().split()]
a2=[]
a3=[]
nul2 = a1[0]
nul3 = a1[-1]
a2.append(nul2)
a3.append(nul3)
#nが2以上?
for i in range(1,n-1):
    nul2=fractions.gcd(nul2,a1[i])
    nul3=fractions.gcd(nul3,a1[-i-1])
    a2.append(nul2)
    a3.append(nul3)
#print(a2)
#print(a3)
c=max([a2[-1],a3[-1]])
for i in range(n-2):
    d=fractions.gcd(a2[i],a3[-i-2])
    if d>c:
        c=d
print(c)
### BUGGY CODE ###

#!/usr/bin/python3
# abc121_c

"""
Energy Drink Collector
"""

def main():
    """
    とにかく安い方からM本になるまで買い続ける。
    """
    N, M = map(int, input().split())
    l = []

    for _ in range(N):
        # [値段, 在庫本数] の2xNリストをつくる。
        l.append(list(map(int, input().split())))

    # 安い順に並べる
    l.sort()
    l_price = []

    # 安い順に、値段だけのリストをつくる。[100, 100, 100, 110, 120, 120, ...]
    for v in l:
        for _ in range(v[1]):
            l_price.append(v[0])

    # 買う。
    cost = 0
    for i in range(M):
        cost += l_price[i]

    # 合計金額を出力
    print(cost)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/python3
# abc121_c

"""
Energy Drink Collector
"""
test = False


def main():
    """
    とにかく安い方からM本になるまで買い続ける。
    """
    N, M = map(int, input().split())
    l = []
    bottle = 0
    cost = 0

    for _ in range(N):
        # [値段, 在庫本数] の2xNリストをつくる。
        l.append(list(map(int, input().split())))

    # 安い順に並べる
    l.sort()
    # 安い店の在庫を全部買って、M本を超えたら中断

    for i in range(N):
        bottle += l[i][1]
        cost += l[i][0] * l[i][1]
        # 買いすぎた分を返品
        if bottle >= M:
            cost -= (bottle - M) * l[i][0]
            break

    # 合計金額を出力
    print(cost)


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

from collections import Counter

S = input()
S = list(map(int, S))

nums = [0] * (len(S) + 1)
pow10 = 1
for i in range(1, len(S) + 1):
    nums[i] = (nums[i - 1] + pow10 * S[-i]) % 2019
    pow10 *= 10

counter = Counter(nums)
ans = 0
for count in counter.values():
    if count >= 2:
        ans += count * (count - 1) // 2

print(ans)


### FIXED CODE ###

S = input()
S = list(map(int, S))

t = 1
r = 0
d = [0] * 2019
d[0] += 1
for n in reversed(S):
    r = (r + n * t) % 2019
    t = t * 10 % 2019
    d[r] += 1

ans = 0
for m in d:
    ans += m * (m-1) // 2

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

def main():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    cost = [0 for _ in range(n)]
    for i in range(1, n):
        m = float('inf')
        for j in range(1, k+1):
            if (i - j) < 0:
                break
            m = min(m, cost[i-j] + abs(h[i] - h[i - j]))
        cost[i] = m
    return cost[n - 1]


print(main())


### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    cost = [0 for _ in range(n)]
    for i in range(1, n):
        m = float('inf')
        for j in range(1, k+1):
            if (i - j) < 0:
                break
            m = min(m, cost[i-j] + abs(h[i] - h[i - j]))
        cost[i] = m
    return cost[n - 1]


print(main())
### BUGGY CODE ###


import sys
input = sys.stdin.readline
n = input()
ans = 0
num_list = [ int(v) for v in input().split() ]
count_list = [ [num_list.count(i),i] for i in sorted(set(num_list),reverse = True)]

a, b = -1, -1
for i in count_list:
	if i[0] >= 4 and a == -1:
		ans = i[1]**2
		break
	elif i[0] >= 2:
		if a == -1:
			a = i[1]
		else:
			b = i[1]
			ans = a*b
			break

print(ans)

### FIXED CODE ###

n = int(input())
ans = 0
num_list = sorted([ int(v) for v in input().split() ],reverse = True)

a, b = -1, -1
d = 0

for i in range(n-1):
	if num_list[i] != num_list[i+1]:
		d = 0
	else:
		if a != -1 and d == 0:
			b = num_list[i]
			ans = a*b
			break
		else:
			d += 1
			a = num_list[i]
			if d == 3:
				ans = a**2
				break

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

import sys
sys.setrecursionlimit(100000000)
input = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = 10 ** 15

def main():
    H,W = map(int,input().split())
    A = [tuple(map(int,input().split())) for _ in range(H)]
    B = [tuple(map(int,input().split())) for _ in range(H)]

    dp = [[[0]*12800 for _ in range(W)] for _ in range(H)]
    dp[0][0][6400] = 1
    for i in range(H):
        for j in range(W):
            if i == H - 1 and j == W - 1:
                break
            a,b = A[i][j],B[i][j]
            for k in range(12800):
                if dp[i][j][k] == 0:
                    continue
                if 0 <= k + a - b < 12800:
                    if i + 1 < H:
                        dp[i + 1][j][k + a - b] |= dp[i][j][k]
                    if j + 1  < W:
                        dp[i][j + 1][k + a - b] |= dp[i][j][k]
                if 0 <= k - a + b < 12800:
                    if i + 1 < H:
                        dp[i + 1][j][k - a + b] |= dp[i][j][k]
                    if j + 1 < W:
                        dp[i][j + 1][k - a + b] |= dp[i][j][k]
    
    ans = INF
    a,b = A[-1][-1],B[-1][-1]
    for i in range(12800):
        if (0 <= i + a - b < 12800 and dp[-1][-1][i + a - b]) or (0 <= i - a + b < 12800 and dp[-1][-1][i - a + b]):
            ans = min(ans,abs(i - 6400))

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


### FIXED CODE ###

import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

def main():
    H,W = map(int,input().split())
    A = [list(map(int,input().split())) for _ in range(H)]
    B = [list(map(int,input().split())) for _ in range(H)]

    dp = [[0]*(1 + W) for _ in range(H + 1)]
    x = abs(A[0][0] - B[0][0])
    dp[0][0] = 1 << (12800 + x)
    dp[0][0] |= 1 << (12800 - x)
    for i in range(H):
        for j in range(W):
            c = abs(A[i][j] - B[i][j])
            if i > 0:
                dp[i][j] |= dp[i - 1][j] << c
                dp[i][j] |= dp[i - 1][j] >> c
            if j > 0:
                dp[i][j] |= dp[i][j - 1] << c
                dp[i][j] |= dp[i][j - 1] >> c
    ans = INF
    x = dp[H - 1][W - 1]
    for i in range(25600):
        if x&1:
            ans = min(ans,abs(i - 12800))
        x >>= 1
    print(ans)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys

a = []
b = []
for line in sys.stdin:
    a.append(int(line))
    b.append(int(line))

del a[0]
del a[len(a)-1]
del b[0]
del b[0]

sub = -100000000000
for i in range(len(a)):
    for j in range(len(b)):
        if j >= i:
            if sub <= b[j]-a[i]:
                sub = b[j]-a[i]
print(sub)


### FIXED CODE ###

import sys

a = []
b = []
for line in sys.stdin:
    a.append(int(line))
    b.append(int(line))

del a[0]
del a[len(a)-1]
del b[0]
del b[0]

maxv = -1000000000
minv = a[0]
for i in range(len(a)):
    maxv = max(maxv,b[i]-minv)
    minv = min(minv,b[i])
print(maxv)
### BUGGY CODE ###

S = input()
Q = int(input())
for i in range(Q):
    query = list(input().split())
    if query[0] == '1':
        S = S[::-1]
    else:
        if query[1] == '1':
            S = query[2] + S
        else:
            S = S + query[2]
print(S)


### FIXED CODE ###

S = input()
Q = int(input())
bs = ''
fs = ''
hanten = 0
for i in range(Q):
    query = list(input().split())
    if query[0] == '1':
        hanten += 1
    else:
        if query[1] == '1':
            if hanten % 2 == 0:
                fs += query[2]
            else:
                bs += query[2]
        else:
            if hanten % 2 == 0:
                bs += query[2]
            else:
                fs += query[2]
if hanten % 2 == 0:
    print(fs[::-1]+S+bs)
else:
    print(bs[::-1]+S[::-1]+fs)
### BUGGY CODE ###

def main():
    import sys
    import time
    input = sys.stdin.buffer.readline
    from math import gcd
    N = int(input())
    A = list(map(int, input().split()))
    g = A[0]

    S = 1
    for x in A:
        S *= x
    start = time.time()

    def factorization(n):
        ret = set()
        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
                ret.add(i)

        if temp != 1:
            ret.add(temp)

        if len(ret) == 0 and n != 1:
            ret.add(n)

        return ret

    flag = True
    s = factorization(A[0])
    for x in A[1:]:
        tmp = 0
        now = time.time()
        if now - start > 1:
            break
        for y in s:
            if x % y == 0:
                flag = False
                break
        if flag:
            s |= factorization(x)
            continue
        else:
            break

    if flag:
        print("pairwise coprime")
    else:
        g = A[0]
        for i, x in enumerate(A[::-1]):
            g = gcd(g, x)
        if g == 1:
            print("setwise coprime")

        else:
            print("not coprime")


main()


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.buffer.readline
    from math import gcd
    N = int(input())
    A = list(map(int, input().split()))
    g = A[0]
    M = max(A)
    X = [i for i in range(M+1)]
    S = [True for i in range(M+1)]
    S[0] = False
    S[1] = False

    for i in range(1, M+1):
        if S[i]:
            for j in range(i, M+1, i):
                if S[j]:
                    S[j] = False
                    X[j] = i
    flag = True
    s = set()
    ls = 0
    for x in A:
        tmp = set()
        while(X[x] != 1):
            tmp.add(X[x])
            x //= X[x]
        l = len(tmp)
        s |= tmp
        if len(s) == ls + l:
            ls += l
            continue
        else:
            flag = False
            break

    if flag:
        print("pairwise coprime")
    else:
        for x in A[1:]:
            g = gcd(g, x)
        if g == 1:
            print("setwise coprime")

        else:
            print("not coprime")


main()
### BUGGY CODE ###

n = int(input())
a_s = [list(map(int, input().split())) for _ in range(n)]
ans = 0
for a in a_s:
    ans += sum(a)

for i in range(n):
    for j in range(n):
        if i == j:
            continue
        for k in range(n):
            if i == k or j == k:
                continue
            if a_s[i][j] > a_s[i][k] + a_s[j][k]:
                print(-1)
                exit()
            if a_s[i][j] == a_s[i][k] + a_s[j][k]:
                ans -= a_s[i][j]

ans //= 2
print(ans)

### FIXED CODE ###

n = int(input())
a_s = [list(map(int, input().split())) for _ in range(n)]
ans = 0
for a in a_s:
    ans += sum(a)

for i in range(n):
    for j in range(n):
        if i == j:
            continue
        for k in range(n):
            if i == k or j == k:
                continue
            if a_s[i][j] > a_s[i][k] + a_s[j][k]:
                print(-1)
                exit()
            if a_s[i][j] == a_s[i][k] + a_s[j][k]:
                ans -= a_s[i][j]
                break

ans //= 2
print(ans)
### BUGGY CODE ###

n,k=map(int, input().split())
if n % k == 0:
    print(0)
else:
    before =n
    while True:
        if abs(n-k) < before:
            n = abs(n - k)
            before = n
        else:
            print(n)
            break

### FIXED CODE ###

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

if n % k == 0:
    print(0)
else:
    n = n - (k*(n // k))
    if n > abs(n - k):
        print(abs(n-k))
    else:
        print(n)