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

from collections import deque
h, w = map(int, input().split())
S = [list(input()) for _ in range(h)]

#BFS
## 距離の初期化
D = [[10000]*w for _ in range(h)]
D[0][0] = 0 if S[0][0]=='.' else 1
## キューの初期化.
que = deque([[0,0]])
## 探索方向の初期化.
directs = [[0,1],[1,0]]
## キューが尽きるまで探索を行う.
while que:
    ### 現在地の取得.
    hi, wi = que.pop()
    ### 以下の移動方向を探索する.
    for dh,dw in directs:
        #### 迷路の範囲外の場合は探索しない.
        if not (0<=hi+dh<h and 0<=wi+dw<w): continue
        #### 白から黒に移る場合、コストが増える.
        if S[hi][wi]!=S[hi+dh][wi+dw] and S[hi+dh][wi+dw]=='#':
            D[hi+dh][wi+dw] = min(D[hi+dh][wi+dw], D[hi][wi]+1)
        else:
            D[hi+dh][wi+dw] = min(D[hi+dh][wi+dw], D[hi][wi])
        que.appendleft([hi+dh, wi+dw])
print(D[-1][-1])

### FIXED CODE ###

from collections import deque
h, w = map(int, input().split())
S = [list(input()) for _ in range(h)]
DP = [[10000]*w for _ in range(h)]
DP[0][0] = 0 if S[0][0]=='.' else 1

directs = [[0,1], [1,0]]
for hi in range(h):
    for wi in range(w):
        for dh,dw in directs:
            if not (0<=hi+dh<h and 0<=wi+dw<w): continue
            if S[hi][wi]=='.' and S[hi+dh][wi+dw]=='#':
                DP[hi+dh][wi+dw] = min(DP[hi+dh][wi+dw], DP[hi][wi]+1)
            else:
                DP[hi+dh][wi+dw] = min(DP[hi+dh][wi+dw], DP[hi][wi])
print(DP[-1][-1])
### BUGGY CODE ###

from bisect import bisect_left

N,M=map(int,input().split())
A=list(map(int,input().split()))
A=sorted(A)

change=[tuple(map(int,input().split())) for _ in range(M)]
change=sorted(change,key=lambda x: x[1],reverse=True)

for i in range(M):
  b,c=change[i]
  idx = bisect_left(A,c)
  
  if idx-b>=0:
    A = A[b:idx]+[c]*b+A[idx:]
  else:
    A = [c]*idx+A[idx:]

print(sum(A))

### FIXED CODE ###

from bisect import bisect_left

N,M=map(int,input().split())
A=list(map(int,input().split()))
A=sorted(A)

change=[tuple(map(int,input().split())) for _ in range(M)]
change=sorted(change,key=lambda x: x[1],reverse=True)
change2=[]
count=0
for i in range(M):
  b,c=change[i]
  change2.extend([c]*b)
  count += b
  if count >= N:break

A.extend(change2)
A = sorted(A)
print(sum(A[len(A)-N:]))
### BUGGY CODE ###

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

from math import gcd
def lcm(a,b):
    return a*b//gcd(a,b)

pairprime_flag=True
allgcd=A[0]
product=1

for a in A:
    allgcd=gcd(allgcd,a)
    if gcd(product,a)!=1:
        pairprime_flag=False
    product=lcm(product,a)
if pairprime_flag:
    print('pairwise coprime')
elif allgcd==1:
    print('setwise coprime')
else:
    print('not coprime')


### FIXED CODE ###

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

#素数
def primes(n):
    n, correction = n-n%6+6, 2-(n%6>1)
    sieve = [True] * (n//3)
    for i in range(1, int(n**0.5)//3+1):
        if sieve[i]:
            k = 3*i+1|1
            sieve[k*k//3::2*k] = [False] * ((n//6-k*k//6-1)//k+1)
            sieve[k*(k-2*(i&1)+4)//3::2*k] = [False] * ((n//6-k*(k-2*(i&1)+4)//6-1)//k+1)
    return [2, 3] + [3*i+1|1 for i in range(1, n//3-correction) if sieve[i]]

primes=primes(int(1000))
points=[0]*1000001

from math import gcd
pairprime_flag=True
allgcd=A[0]
allprime=set()

for a in A:
    allgcd=gcd(allgcd,a)
    if pairprime_flag:
        for i in primes:
            if a%i==0:
                if points[i]==1:
                    pairprime_flag=False
                points[i]=1
                while a%i==0:
                    a//=i
            if a==1:
                break
        if a!=1:
            if points[a]!=0:
                pairprime_flag=False
            else:
                points[a]=1

if pairprime_flag:
    print('pairwise coprime')
elif allgcd==1:
    print('setwise coprime')
else:
    print('not coprime')
### BUGGY CODE ###

n = int(input())
M = 10**9+7
sum = 1
for i in range(1,n+1):
  sum *= i%M
print(sum%M)


### FIXED CODE ###

n = int(input())
d = 1
for i in range(1,n+1):
  d = (d*i)%(10**9+7)
print(d)
### BUGGY CODE ###

def solve(S):
    ref = {}
    ret = 0
    for i in range(len(S) + 1):
        t = int(S[i:]) % 2019 if i < len(S) else 0
        ret += ref.get(t, 0)
        ref[t] = ref.get(t, 0) + 1
    return ret

if __name__ == "__main__":
    S = input()
    print(solve(S))

### FIXED CODE ###

MOD = 2019

def solve(S):
    N = len(S)
    dp = [0 for _ in range(MOD)]
    tmp = 0
    ret = 0
    for i in range(N):
        m = (tmp + int(S[i]) * pow(10, N - i - 1, MOD)) % MOD
        ret += dp[m]
        dp[m] += 1
        tmp = m
    ret += dp[0]
    return ret

if __name__ == "__main__":
    S = input()
    print(solve(S))
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve_naive(n: int, a: "List[int]"):
    b = list()
    for i in range(n):
        b.append(str(a[i]))
        b.reverse()
    print(" ".join(b))
    return

def solve(n: int, a: "List[int]"):
    a = list(map(str, a))
    b = list()
    for i in range(n):
        if i % 2 == 0:
            # push
            b.insert(0, a[i])
        else:
            # append
            b.append(a[i])
    if n % 2 == 0:
        b.reverse()
    print(" ".join(b))
    return

# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    n = int(next(tokens))  # type: int
    a = [ int(next(tokens)) for _ in range(n) ]  # type: "List[int]"
    solve(n, a)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve_naive(n: int, a: "List[int]"):
    b = list()
    for i in range(n):
        b.append(str(a[i]))
        b.reverse()
    print(" ".join(b))
    return

def solve_(n: int, a: "List[int]"):
    a = list(map(str, a))
    b = list()
    for i in range(n):
        if i % 2 == 0:
            # push
            b.insert(0, a[i])
        else:
            # append
            b.append(a[i])
    if n % 2 == 0:
        b.reverse()
    print(" ".join(b))
    return

def solve__(n: int, a: "List[int]"):
    a = list(map(str, a))
    b = list()
    for i in range(n):
        if i % 2 == (n-1) % 2:
            # push
            b.insert(0, a[i])
        else:
            # append
            b.append(a[i])
    print(" ".join(b))
    return

def solve___(n: int, a: "List[int]"):
    b = list()
    for i in range(n):
        if i % 2 == (n-1) % 2:
            # push
            b.insert(0, a[i])
        else:
            # append
            b.append(a[i])
    print(*b)
    return

def solve(n: int, a: "List[int]"):
    import collections
    b = collections.deque()
    for i in range(n):
        if i % 2 == (n-1) % 2:
            # push
            b.appendleft(a[i])
        else:
            # append
            b.append(a[i])
    print(*b)
    return

# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    n = int(next(tokens))  # type: int
    a = [ int(next(tokens)) for _ in range(n) ]  # type: "List[int]"
    solve(n, a)

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

import sys
input=sys.stdin.readline
n,a,b,c=map(int,input().split())
s=[input() for i in range(n)]
dp=[dict() for i in range(n+1)]
dp[0][""]=[a,b,c]
for i in range(n):
    if len(dp[i])==0:
        print("No")
        break
    if s[i][0]=="A" and s[i][1]=="B":
        #print(0)
        for j in dp[i]:
            a,b,c=dp[i][j]
            if dp[i][j][0]>0:
                dp[i+1][j+"B"]=[a-1,b+1,c]
            if dp[i][j][1]>0:
                dp[i+1][j+"A"]=[a+1,b-1,c]
    elif s[i][0]=="A" and s[i][1]=="C":
        #print(1)
        for j in dp[i]:
            a,b,c=dp[i][j]
            if dp[i][j][0]>0:
                dp[i+1][j+"C"]=[a-1,b,c+1]
            if dp[i][j][2]>0:
                dp[i+1][j+"A"]=[a+1,b,c-1]
    else:
        #print(2)
        for j in dp[i]:
            a,b,c=dp[i][j]
            if dp[i][j][1]>0:
                dp[i+1][j+"C"]=[a,b-1,c+1]
            if dp[i][j][2]>0:
                dp[i+1][j+"B"]=[a,b+1,c-1]
else:
    if len(dp[n])==0:
        print("No")
    else:
        print("Yes")
        #print(dp)
        z=list(dp[-1])
        #print(z)
        for i in range(n):
            print(z[-1][i])






### FIXED CODE ###

n,a,b,c=map(int,input().split())
s_=[input() for i in range(n)]
ans=""
for i in range(n):
    s1,s2=s_[i]
    if s2=="B":
        if a==1 and b==1 and i!=n-1:
            if s_[i+1][0]=="A":
                a,b,ans=(a+1,b-1,ans+"A")
            else:
                a,b,ans=(a-1,b+1,ans+"B")
            continue
        a,b,ans=(a-1,b+1,ans+"B") if a>b else (a+1,b-1,ans+"A")
        if min(a,b)==-1:
            print("No")
            break
    elif s1=="A":
        if a==1 and c==1 and i!=n-1:
            if s_[i+1][1]=="C":
                a,c,ans=(a-1,c+1,ans+"C")
            else:
                a,c,ans=(a+1,c-1,ans+"A")
            continue
        a,c,ans=(a-1,c+1,ans+"C") if a>c else (a+1,c-1,ans+"A")
        if min(a,c)==-1:
            print("No")
            break
    else:
        if c==1 and b==1 and i!=n-1:
            if s_[i+1][1]=="C":
                b,c,ans=(b-1,c+1,ans+"C")
            else:
                b,c,ans=(b+1,c-1,ans+"B")
            continue
        b,c,ans=(b-1,c+1,ans+"C") if b>c else (b+1,c-1,ans+"B")
        if min(b,c)==-1:
            print("No")
            break
else:
    print("Yes")
    for j in range(n):
        print(ans[j])
### BUGGY CODE ###

import math
import numpy as np
 
N, K = map(int,input().split())
A = list(map(int,input().split()))
F = list(map(int,input().split()))

A_n = np.array(A)
F_n = np.array(F)
A_sort = np.sort(A_n)
F_sort = np.sort(F_n)[::-1]
 
for j in range(K):

    np_list = A_sort*F_sort
    max_index = np_list.argmax()
    if max(A_sort) == 0:
        break
    else:
        A_sort[max_index] -= 1
    
ans = 0

print(max(A_sort*F_sort))


### FIXED CODE ###

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

A_sort = sorted(A)
F_sort = sorted(F,reverse=True)

l = -1
r = 0
for i in range(N):
    r = max(r,A_sort[i]*F_sort[i])

def judge(c):
    s = 0
    for i in range(N):
        s += max(A_sort[i]-c//F_sort[i],0)
    return s <= K

while r-l > 1:
    c = (l+r)//2
    if judge(c):
        r = c
    else:
        l = c
print(r)
### BUGGY CODE ###

import math

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

product = math.prod(A)
if product <= 10 ** 18:
    print(product)
else:
    print(-1)


### FIXED CODE ###

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

if 0 in A:
    print(0)
else:
    product = 1
    for Ai in A:
        product *= Ai
        if product > 10 ** 18:
            print(-1)
            exit()

    print(product)
### BUGGY CODE ###

H, W, K = map(int, input().split())
S = [[int(i) for i in input()] for _ in range(H)]

m = float('inf')
for i in range(1 << (H - 1)) :
  pos = [0] * H
  x = 0
  for j in range(H - 1) :
    if i & (1 << j) :
      x += 1
    pos[j+1] = x
      
  x = 0
  cnt = [0] * H
  ret = bin(i)[2:].count('1')
  while x < W :
    for y in range(H) :
      cnt[pos[y]] += S[y][x]
      if cnt[pos[y]] > K :
        cnt = [0] * H
        ret += 1
        break
    else :
      x += 1
      
  m = min(m, ret)
  
print(m)

### FIXED CODE ###

import sys
input = sys.stdin.readline

H, W, K = map(int, input().split())
S = [[int(i) for i in input()[:-1]] for _ in range(H)]

m = float('inf')
for i in range(1 << (H - 1)) :
  pos = [0] * H
  x = 0
  for j in range(H - 1) :
    if i & (1 << j) :
      x += 1
    pos[j+1] = x
  
  ret = x
  x = 0
  cnt = [0] * H
  flag = 0
  while x < W :
    for y in range(H) :
      cnt[pos[y]] += S[y][x]
      if cnt[pos[y]] > K :
        cnt = [0] * H
        ret += 1
        flag += 1
        break
    else :
      x += 1
      flag = 0
      
    if flag == 2 :
      ret = float('inf')
      break
  
  m = min(m, ret)
  
print(m)
### BUGGY CODE ###

from sys import stdin
from sys import setrecursionlimit as SRL; SRL(10**7)
rd = stdin.readline
rrd = lambda: map(int, rd().strip().split())

n, q = rrd()

v = [[] for _i in range(n + 10)]

for i in range(n - 1):
    x, y = rrd()
    v[x].append(y)
    v[y].append(x)

add = [0] * (n + 10)

for i in range(q):
    p, x = rrd()
    add[p] += x


def dfs(now, fa):
    add[now] += add[fa]
    for i in v[now]:
        if i == fa:
            continue
        dfs(i, now)


dfs(1, 0)

for i in range(1, n + 1):
    print(add[i], end=' ')


### FIXED CODE ###

from sys import setrecursionlimit as SRL, stdin, stdout

SRL(10 ** 7)
rd = stdin.readline
rrd = lambda: map(int, rd().strip().split())

n, q = rrd()

v = [[] for _i in range(n + 10)]

for i in range(n - 1):
    x, y = rrd()
    v[x].append(y)
    v[y].append(x)

add = [0] * (n + 10)

for i in range(q):
    p, x = rrd()
    add[p] += x

p = [(1, 0)]
vis = [0] * (n + 2)
while len(p):
    now, fa = p.pop()
    add[now] += add[fa]
    vis[now] = 1
    for i in v[now]:
        if not vis[i]:
            p.append((i,now))

stdout.write(" ".join(map(str, add[1:n + 1])))
### BUGGY CODE ###

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

#print(sum(p[1:4]))
maxid = 0
for i in range(N - (K-1)):
    if(sum(p[maxid:(maxid+K)]) < sum(p[i:(i+K)])):
        maxid = i

maxsum = 0
for i in range(K):
    maxsum += ((p[maxid+i]*(p[maxid+i]+1))/2)/p[maxid+i]

print(maxsum)



### FIXED CODE ###

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

S = 0
maxsum = 0
for i in range(K):
    S += (p[i]+1)/2

for i in range(K,N):
    if(maxsum < S):
        maxsum = S
    S = S + (p[i]+1)/2 - (p[i-K]+1)/2

if(maxsum < S):
    maxsum = S

print(maxsum)
### BUGGY CODE ###

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

data = [0]*q;
for i in range(q):
    data[i] = list(map(int,input().split()));

A = [1]*n;
ans = 0;
As = [A];

for i in As :
    A_now = As.pop(0);
    for j in range(n) :
        if A_now[j] < m :
            A_next = [A_now[j]+1]*n;
            for k in range(j) :
                A_next[k] = A_now[k];
            As.append(A_next);
    ans_now = 0;
    for j in range(q) :
        if A_now[data[j][1]-1] - A_now[data[j][0]-1] == data[j][2] :
            ans_now += data[j][3];
    if ans_now>ans :
        ans = ans_now;


print(ans);

### FIXED CODE ###

n,m,q = list(map(int,input().split()));
 
data = [0]*q;
for i in range(q):
    data[i] = list(map(int,input().split()));
 
A = [1]*n;
ans = 0;
As = [A];
 
for i in As :
    A_now = As.pop(-1);
    for j in range(n) :
        if A_now[j] < m :
            A_next = [A_now[j]+1]*n;
            for k in range(j) :
                A_next[k] = A_now[k];
            As.append(A_next);
    ans_now = 0;
    for j in range(q) :
        if A_now[data[j][1]-1] - A_now[data[j][0]-1] == data[j][2] :
            ans_now += data[j][3];
    if ans_now>ans :
        ans = ans_now;
 
 
print(ans);
### BUGGY CODE ###

from queue import deque

    
H, W = map(int, input().split())
S = []
cnt = []


for _ in range(H):
    S.append([i for i in input()])
    
for start_h in range(H):
    for start_w in range(W):
        if S[start_h][start_w] == '#':
            continue
        for goal_h in range(H):
            for goal_w in range(W):
                if S[goal_h][goal_w] == '#':
                    continue
                if start_h == goal_h or start_w == goal_w:
                    cnt.append(abs(start_h - goal_h) + abs(start_w - goal_w))
                    continue
                    
                q = [[start_h, start_w]]
                checked = []
                c = 0
                tmp = []
                while q:
                    h, w = q.pop(0)
                    if [h, w] in checked:
                        continue
                    checked.append([h, w])
                    if h == goal_h and w == goal_w:
                        cnt.append(c)
                        break
                        
                    for dw, dh in ([1, 0], [-1, 0], [0, 1], [0, -1]):
                        next_h, next_w = h + dh, w + dw
                        if next_h < 0 or next_h >= H or next_w < 0 or next_w >= W:
                            continue
                        if S[next_h][next_w] == '#':
                            continue
                        if [next_h, next_w] in tmp or [next_h, next_w] in checked:
                            continue
                        tmp.append([next_h, next_w])
                    if not q:
                        q.extend(tmp)
                        tmp = []
                        c += 1

print(max(cnt))

### FIXED CODE ###

from queue import deque
from copy import deepcopy

    
H, W = map(int, input().split())
S = [['#'] * (W + 2)]
cnt = []
Checked = [[0 for _ in range(W+2)] for _ in range(H+2)]


for _ in range(H):
    S.append(['#'] + [i for i in input()] + ['#'])
S.append(['#']*(W + 2))

for start_h in range(1, H+1):
    for start_w in range(1, W+1):
        if S[start_h][start_w] == '#':
            continue
        q = deque([[start_h, start_w]])
        checked = deepcopy(Checked)
        c = 0
        tmp = []
        while q:
            h, w = q.popleft()
            if checked[h][w]:
                 continue
            checked[h][w] = 1
                    
            for dw, dh in ([1, 0], [-1, 0], [0, 1], [0, -1]):
                next_h, next_w = h + dh, w + dw
                if S[next_h][next_w] == '#':
                    continue
                if [next_h, next_w] in tmp or checked[next_h][next_w]:
                    continue
                tmp.append([next_h, next_w])
            if not q:
                q.extend(tmp)
                tmp = []
                c += 1
        cnt.append(c-1)
            
print(max(cnt))
### BUGGY CODE ###

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

count = {}
for a in A:
    if count.get(a):
        count[a] += 1
    else:
        count[a] = 1

q = int(input())
result = []
for i in range(q):
    b, c = list(map(int, input().split()))
    if count.get(b):
        count[c] = count.get(c, 0) + count.pop(b)
    sum = 0
    for key, value in count.items():
        sum += key * value
    result.append(str(sum))
print('\n'.join(result))

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
num = [0] * (10 ** 5 + 1)

for a in A:
    num[a] += 1
_sum = sum(A)

result = []
q = int(input())
for i in range(q):
    b, c = list(map(int, input().split()))
    _sum += (c - b) * num[b]
    num[c] += num[b]
    num[b] = 0
    result.append(str(_sum))
print('\n'.join(result))
### BUGGY CODE ###

s=input();mod=10**9+7
dp = [[0]*13for _ in range(len(s)+1)]
dp[0][0]=1
for i in range(len(s)):
  if s[i]=='?':
    for j in range(13):
      for k in range(10):
        dp[i+1][(10*j+k)%13] += dp[i][j]
        dp[i+1][(10*j+k)%13] %= mod
  else:
    for j in range(13):
      dp[i+1][(10*j+int(s[i]))%13] += dp[i][j]
      dp[i+1][(10*j+int(s[i]))%13] %= mod
print(dp[len(s)][5])

### FIXED CODE ###

s=input();mod=10**9+7
dp = [[0]*13for _ in range(len(s)+1)]
dp[0][0]=1
for i in range(len(s)):
  if s[i]=='?':
    for j in range(13):
      for k in range(10):
        dp[i+1][(10*j+k)%13] += dp[i][j]
        dp[i+1][(10*j+k)%13] %= mod
  else:
    for j in range(13):
      dp[i+1][(10*j+int(s[i]))%13] += dp[i][j]
      dp[i+1][(10*j+int(s[i]))%13] %= mod
print(dp[len(s)][5])
### BUGGY CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
ans = -1
for i in range(n):
    a[i] = a[i] - i - 1
count = Counter(a)
for b in count.keys():
    tmp = 0
    for i in range(n):
        tmp += abs(a[i] - b)
    if ans == -1 or tmp < ans:
        ans = tmp
print(ans)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(n):
    a[i] = a[i] - i - 1
a.sort()
b = a[n // 2]
for i in range(n):
    ans += abs(a[i] - b)
print(ans)
### BUGGY CODE ###

import sys

input = sys.stdin.readline

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

    DP = [[0 for _ in range(W*2)] for _ in range(N+1)]

    for i in range(N):
        for sum_w in range(W+1):

            if sum_w - wv[i][0] >= 0:
                DP[i+1][sum_w] = max(
                    DP[i][sum_w - wv[i][0]] + wv[i][1],
                    DP[i+1][sum_w])

            DP[i+1][sum_w] = max(DP[i][sum_w], DP[i+1][sum_w])

    print(DP[N][W])


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys

def main():
    _input = sys.stdin.readline

    N, W = map(int, _input().split())
    wv = [list(map(int, _input().split())) for _ in range(N)]

    wv.sort()

    DP = [-1] * (W+1)
    DP[0] = 0

    sum_w = 0
    for w, v in wv:
        sum_w += w
        for j in range(min(W, sum_w), w-1, -1):
            if DP[j-w] == -1:
                continue
            if DP[j] < DP[j-w] + v:
                DP[j] = DP[j-w] + v
    print(max(DP))


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

def resolve():
    N, K = list(map(int, input().split()))
    if (K == 1):
        print(0)
        return
    x = N
    memo = [N]
    while True:
        x = min(abs(x - K), x)
        if x in memo:
            print(min(memo))
            return
        memo.append(x)
    return

resolve()

### FIXED CODE ###

def resolve():
    N, K = list(map(int, input().split()))
    print(min(N % K, K - (N % K)))
    return


resolve()
### BUGGY CODE ###

def main():

    import sys
    input = sys.stdin.readline
    from bisect import bisect_left

    N,Q = map(int,input().split())
    info = []
    for _ in range(N):
        s,t,x = map(int,input().split())
        info.append((x,s,t))
    info = sorted(info)
    tmp = sorted([(int(input()),i) for i in range(Q)])
    D = []
    ID = []
    for d,i in tmp:
        D.append(d)
        ID.append(i)

    S = set(range(Q))
    ans = [-1]*Q

    for x,s,t in info:
        left = bisect_left(D,s-x)
        right = bisect_left(D,t-x)
        for i in ID[left:right]:
            if i in S:
                ans[i] = x
                S.remove(i)

    for a in ans:
        print(a)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
from bisect import bisect_left
inf = float('inf')

N, Q = map(int,input().split())
STX = [list(map(int,input().split())) for _ in range(N)]
D = [int(input()) for _ in range(Q)]

res = 1
while res < Q:
    res <<= 1
N0 = res
data = [inf for _ in range(2*N0-1)]

def update(l, r, x):
    L = l + N0
    R = r + N0
    while L < R:
        if R & 1:
            R -= 1
            data[R] = min(data[R], x)
        if L & 1:
            data[L] = min(data[L], x)
            L += 1
        L >>= 1; R >>= 1

def value(k):
    k += N0
    res = data[k]
    while k != 0:
        k >>= 1
        res = min(res, data[k])
    return res


for S, T, X in STX:
    l = bisect_left(D, S-X)
    r = bisect_left(D, T-X)
    update(l, r, X)

for k in range(Q):
    ans = value(k)
    if ans == inf:
        ans = -1
    print(ans)
### BUGGY CODE ###

n = int(input())
s = {}
for _ in range(n) :
    s_sub = input()

    if s_sub in s.keys() :
        s[s_sub] += 1
    else :
        s[s_sub] = 1


s_sorted = sorted(s)

for j in s_sorted :
    if s[j] == max(s.values()):
        print(j)


### FIXED CODE ###

n = int(input())
s = {}
for _ in range(n) :
    s_sub = input()
    if s_sub in s.keys() :
        s[s_sub] += 1
    else :
        s[s_sub] = 1


s_sorted1 = sorted(s.items(), key = lambda value: -value[1])
max = s_sorted1[0][1]
ans = []
for j,k in s_sorted1 :
    if k == max :
        ans.append(j)
    else:
        break

for x in sorted(ans):
    print(x)