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

import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = float('inf')
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()
    DD = ((1,0),(0,1),(-1,0),(0,-1))

    H,W,K = LI()
    x1,y1,x2,y2 = _LI()

    p = [SI() for _ in range(H)]

    d = [[INF] * W for _ in range(H)]
    for i in range(4):
        d[x1][y1] = 0

    q = collections.deque()
    q.append((x1,y1))
    while q:
        x,y = q.pop()
        for dx,dy in DD:
            for n in range(1,K+1):
                nx = x + dx * n
                ny = y + dy * n
                if not(0<=nx<H and 0<=ny<W): break
                if p[nx][ny] == '@': break
                if d[nx][ny] < d[x][y] + 1: break
                if d[nx][ny] == d[x][y] + 1: continue
                d[nx][ny] = d[x][y] + 1
                q.append((nx,ny))
    if d[x2][y2] < float('inf'):
        print(d[x2][y2])
    else:
        print(-1)



if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = float('inf')
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()
    DD = ((1,0),(0,1),(-1,0),(0,-1))

    H,W,K = LI()
    x1,y1,x2,y2 = _LI()

    p = [SI() for _ in range(H)]

    d = [[INF] * W for _ in range(H)]
    d[x1][y1] = 0

    q = []
    q.append((0,x1,y1))
    while q:
        n,x,y =  heapq.heappop(q)
        if d[x][y] < n: continue
        for dx,dy in DD:
            for n in range(1,K+1):
                nx = x + dx * n
                ny = y + dy * n
                if not(0<=nx<H and 0<=ny<W): break
                if p[nx][ny] == '@': break
                if d[nx][ny] < d[x][y] + 1: break
                if d[nx][ny] == d[x][y] + 1: continue
                d[nx][ny] = d[x][y] + 1
                q.append((d[nx][ny],nx,ny))
    if d[x2][y2] < INF:
        print(d[x2][y2])
    else:
        print(-1)



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

def main():
  num,capacity,*wv =map(int,open(0).read().split())
  weights,values = wv[::2], wv[1::2]
  DP=[-1]*(capacity+1)
  DP[0]=0
  for weight,value in zip(weights, values):
    left=capacity-weight
    DP[weight:]=[max(DP[i]+value,DP[i+weight]) for i in range(left,-1,-1)][::-1]
  print(max(DP))
      
if __name__=="__main__":
  main()

### FIXED CODE ###

n,w=map(int,input().split())
goods=[list(map(int,input().split())) for _ in range(n)]
DP=[[0]*(w+1) for _ in range(n+1)]
for i in list(range(n))[::-1]:
  wi,vi=goods[i][0],goods[i][1]
  for j in range(w+1):
    if j<wi:
      DP[i][j]=DP[i+1][j]
    else:
      DP[i][j]=max(DP[i+1][j],DP[i+1][j-wi]+vi)
print(DP[0][w])
### BUGGY CODE ###

import sys
readline = sys.stdin.readline

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

D = list(map(int, readline().split()))

Ans = [None]*Q
for q in range(Q):
    n, x, mod = map(int, readline().split())
    D2 = [d%mod for d in D]
    res = x + ((n-1)//K)*sum(D2)
    zero = ((n-1)//K)*D2.count(0)
    for i in range((n-1)%K):
        res += D2[i]
        if not D2[i]:
            zero += 1
    minus = res//mod - x//mod
    Ans[q] = n-1 - zero - minus
print('\n'.join(map(str, Ans)))

### FIXED CODE ###

import sys
readline = sys.stdin.readline

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

D = list(map(int, readline().split()))

Ans = [None]*Q
for q in range(Q):
    n, x, mod = map(int, readline().split())
    x%= mod
    D2 = [d%mod for d in D]
    res = 0
    cnt = 0
    zero = 0
    for d2 in D2:
        res += d2
        if res > mod:
            cnt += 1
            res -= mod
        if not d2:
            zero += 1
    
    loop =  ((n-1)//K)
    minus = loop*cnt
    zero *= loop
    res2 = 0
    for i in range((n-1)%K):
        res2 += D2[i]
        if not D2[i]:
            zero += 1
        if res > mod:
            res -= mod
            minus += 1
    minus += (x%mod + loop*res + res2)//mod
    Ans[q] = n-1 - zero - minus
print('\n'.join(map(str, Ans)))
### BUGGY CODE ###

all,rolls=map(int,input().split())
List=list(map(int,input().split()))

sum = 0
sumList =[]

for i in range(all - rolls + 1):
	sum = 0
	for j in range(rolls):
		sum = sum + (List[i + j] + 1) / 2
	sumList.append(sum)

sumList.sort(reverse=True)
print(sumList[0])



### FIXED CODE ###

all,rolls=map(int,input().split())
inputList=list(map(int,input().split()))

sum = 0
sumList =[]

# 初めに全期待値計算
for i in range(all):
	inputList[i] = (inputList[i] + 1) / 2

# 最初の組み合わせの期待値計算
for i in range(rolls):
	sum = sum + inputList[i]
sumList.append(sum)

# 2番目以降の期待値計算
for i in range(all - rolls):
	sum = sum + inputList[i + rolls] - inputList[i]
	sumList.append(sum)

sumList.sort(reverse=True)
print(sumList[0])
### BUGGY CODE ###

s = input()
target = input()
for index in range(len(s)):
    ss = s[index]
    tt = target[index]

    if ss == tt:
        continue
    else: #ssとttを相互変換する
        s = s.replace(ss,"0").replace(tt,ss).replace("0",tt)

if s == target:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

from collections import Counter
s=sorted(Counter(input()).values())
t=sorted(Counter(input()).values())
print("Yes" if t==s else "No")
### BUGGY CODE ###

def main():
    A, B, C = map(int, input().split())

    a = A
    b = B
    c = C
    i = 0
    while True:
        if (b + c) % 2 > 0 or (a + c) % 2 > 0 or (a + b) % 2 > 0:
            break
        elif A == B == C:
            i = -1
        else:
            now_a = (b + c) / 2
            now_b = (a + c) / 2
            now_c = (a + b) / 2
            a = now_a
            b = now_b
            c = now_c
            i += 1
    print(i)

main()


### FIXED CODE ###

def main():
    A, B, C = map(int, input().split())

    a = A
    b = B
    c = C
    i = 0
    while True:
        if a % 2 > 0 or b % 2 > 0 or c % 2 > 0:
            break
        elif A == B == C:
            i = -1
            break
        else:
            now_a = (b + c) / 2
            now_b = (a + c) / 2
            now_c = (a + b) / 2
            a = now_a
            b = now_b
            c = now_c
            i += 1
    print(i)

main()
### BUGGY CODE ###

import numpy as np
from collections import deque

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
base = []
base.append(["#" for _ in range(w+4)])
base.append(["#" for _ in range(w+4)])
for n in range(h):
    s = list(input())
    s.append("#")
    s.append("#")
    s.insert(0, "#")
    s.insert(0, "#")
    base.append(s)
base.append(["#" for _ in range(w+4)])
base.append(["#" for _ in range(w+4)])
base = np.array(base)
ans = np.full_like(base, -1, dtype = int)
for j in range(w+4):
    for i in range(h+4):
        if base[i][j] == "#":
            ans[i][j] = -2
ch+=1
cw+=1
dh+=1
dw+=1
ans[ch][cw] = 0
move = [(1, 0), (-1, 0), (0, 1), (0, -1)]
move2 = []
for i in range(-2, 3):
    for j in range(-2, 3):
        move2.append((i, j))
q = deque()
one_time = deque()
q.append([ch, cw])
while q:
    x, y = q.popleft()
    one_time.append((x, y))
    for (i, j) in move:
        v1, v2 = x+i, y+j
        if ans[v1][v2] == -1:
            ans[v1][v2] = ans[x][y]
            q.append((v1, v2))
    if len(q) == 0:
        while one_time:
            x2, y2 = one_time.popleft()
            for (i, j) in move2:
                v1, v2 = x2+i, y2+j
                if ans[v1][v2] == -1:
                    ans[v1][v2] = ans[x2][y2] + 1
                    q.append((v1, v2))
print(ans[dh][dw])

### FIXED CODE ###

from collections import deque
 
 
# In[30]:
 
 
def main():
    H,W = map(int, input().split())
    ch,cw = map(int, input().split())
    dh,dw = map(int, input().split())
    s = ["#"*(W+4)]
    s.append("#"*(W+4))
    for i in range(H):
        s.append("##"+input()+"##")
    s.append("#"*(W+4))
    s.append("#"*(W+4))
    
    ans = [[-1]*(W+4) for _ in range(H+4)]
    for i in range(H+4):
        for j in range(W+4):
            if s[i][j] == "#":
                ans[i][j] = -2
    ch += 1; cw += 1
    dh += 1; dw += 1
    ans[ch][cw] = 0
    
    move = [[-1,0],[1,0],[0,-1],[0,1]]
    magic = [
        [-2,-2],[-2,-1],[-2,0],[-2,1],[-2,2],\
        [-1,-2],[-1,-1],[-1,0],[-1,1],[-1,2],\
        [0,-2],[0,-1],[0,0],[0,1],[0,2],\
        [1,-2],[1,-1],[1,0],[1,1],[1,2],\
        [2,-2],[2,-1],[2,0],[2,1],[2,2]
        ]
    
    mylist = deque([[ch,cw]])
    mylist2 = deque([])
    while len(mylist) > 0:
        x,y = mylist.popleft()
        mylist2.append([x,y])
        for p,q in move:
            v1,v2 = x+p,y+q
            if ans[v1][v2] == -1:
                mylist.append([v1,v2])
                ans[v1][v2] = ans[x][y]
        if len(mylist) == 0:
            while len(mylist2) > 0:
                x2,y2 = mylist2.popleft()
                for v1,v2 in magic:
                    i,j = x2+v1,y2+v2
                    if ans[i][j] == -1:
                        ans[i][j] = ans[x2][y2]+1
                        mylist.append([i,j])
    print(ans[dh][dw])
 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

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

import math

N = int(input())

power = 1
for i in range(N):
    power *= i + 1
print(int(power) % int(math.pow(10, 9) + 7))

### FIXED CODE ###

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

H,W = map(int,raw_input().split())
h = H/2
hh = H%2
w = W/2
ww = W%2

while True:
    if H == 0 and W == 0:
        break
    for i in range(h):
        print ("#."* w + "#"* ww)
        print (".#"* w + "."* ww)
    if hh == 1:
        print ("#."* w + "#"* ww)
    print""


         

### FIXED CODE ###

while True:
    H,W = map(int,raw_input().split())
    if H == 0 and W == 0:
        break
    for i in range(0,H/2):
        print ("#."* (W/2) + "#"* (W%2))
        print (".#"* (W/2) + "."* (W%2))
    if H%2 == 1:
        print ("#."* (W/2) + "#"* (W%2))
    print""
### BUGGY CODE ###

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

for i in range(1,N+1):
    b.append(a.index(i) + 1)


print(*b, sep=' ')





### FIXED CODE ###

N = int(input())
a = [int(i) for i in input().split()]
b = sorted(a)
c = []

dic = dict(zip(a , b))

for i in range(1,N+1):
    c.append(dic[i])

print(*c)
### BUGGY CODE ###

N, M = map(int, input().split())
A = [int(x) for x in input().split()]

for _ in range(M):
    A[A.index(max(A))] = max(A)//2

print(sum(A))


### FIXED CODE ###

import heapq

N, M = map(int, input().split())
A = [-int(x) for x in input().split()]
heapq.heapify(A)
for _ in range(M):
    pop = heapq.heappop(A)
    if pop % 2 == 0:
        num = pop//2
    else:
        num = (pop+1)//2
    heapq.heappush(A, num)

print(-sum(A))
### BUGGY CODE ###

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

# 入力を整数に変換して受け取る
def input_int():
    return int(input())


# マイナス1した値を返却
def int1(x):
    return int(x) - 1


# 半角スペース区切り入力をIntに変換してMapで受け取る
def input_to_int_map():
    return map(int, input().split())


# 半角スペース区切り入力をIntに変換して受け取る
def input_to_int_tuple():
    return tuple(map(int, input().split()))


# 半角スペース区切り入力をIntに変換してマイナス1した値を受け取る
def input_to_int_tuple_minus1():
    return tuple(map(int1, input().split()))


def main():
    n = int(input())
    a = input_to_int_tuple()

    ret = 0
    for i in range(1, n + 1):
        ah = a[i - 1]
        for j in range(i + ah, n + 1):
            if (j - i) == (ah + a[j - 1]):
                ret += 1

    return ret


if __name__ == "__main__":
    print(main())


### FIXED CODE ###

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

# 入力を整数に変換して受け取る
def input_int():
    return int(input())


# マイナス1した値を返却
def int1(x):
    return int(x) - 1


# 半角スペース区切り入力をIntに変換してMapで受け取る
def input_to_int_map():
    return map(int, input().split())


# 半角スペース区切り入力をIntに変換して受け取る
def input_to_int_tuple():
    return tuple(map(int, input().split()))


# 半角スペース区切り入力をIntに変換してマイナス1した値を受け取る
def input_to_int_tuple_minus1():
    return tuple(map(int1, input().split()))


def main():
    n = int(input())
    a = input_to_int_tuple()

    from collections import defaultdict
    l = defaultdict(int)
    r = defaultdict(int)
    for i, h in enumerate(a):
        no = i + 1
        l[no + h] += 1
        r[no - h] += 1

    ret = 0
    for i in range(1, n + 1):
        ret += (l.get(i, 0) * r.get(i, 0))

    return ret


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

from math import log2, ceil


class SegTree:
    #####単位元######
    ide_ele = []

    def __init__(self, init_val):
        n = len(init_val)
        self.num = 2**ceil(log2(n))
        self.seg = [self.ide_ele] * (2 * self.num - 1)

        for i in range(n):
            self.seg[i + self.num - 1] = init_val[i]

        # built
        for i in range(self.num - 2, -1, -1):
            self.seg[i] = self.segfunc(self.seg[2 * i + 1], self.seg[2 * i + 2])

    #####segfunc######
    def segfunc(self, x, y):
        _x = x[:]
        _y = y[:]
        _x.extend(_y)
        ans = list(set(_x))

        return ans

    def update(self, k, x):
        k += self.num - 1
        self.seg[k] = x
        while k:
            k = (k - 1) // 2
            self.seg[k] = self.segfunc(self.seg[k * 2 + 1], self.seg[k * 2 + 2])

    def query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return self.ide_ele
        if a <= l and r <= b:
            return self.seg[k]
        else:
            vl = self.query(a, b, k*2+1, l, (l+r)//2)
            vr = self.query(a, b, k*2+2, (l+r)//2, r)
            return self.segfunc(vl, vr)


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

init_val = [[s] for s in S]
seg_tree = SegTree(init_val)


ans = []
for _ in range(Q):
    i, l, r = input().split()
    i = int(i)
    l = int(l)
    if i == 1:
        seg_tree.update(l-1, [r])
    else:
        r = int(r)
        ans.append(len(seg_tree.query(l-1, r, 0, 0, seg_tree.num)))

for a in ans:
    print(a)


### FIXED CODE ###

from math import log2, ceil


class SegTree:
    #####単位元######
    ide_ele = 0

    def __init__(self, init_val):
        n = len(init_val)
        self.num = 2**ceil(log2(n))
        self.seg = [self.ide_ele] * (2 * self.num - 1)

        for i in range(n):
            self.seg[i + self.num - 1] = init_val[i]

        # built
        for i in range(self.num - 2, -1, -1):
            self.seg[i] = self.segfunc(self.seg[2 * i + 1], self.seg[2 * i + 2])

    #####segfunc######
    def segfunc(self, x, y):
        return x|y

    def update(self, k, x):
        k += self.num - 1
        self.seg[k] = x
        while k:
            k = (k - 1) // 2
            self.seg[k] = self.segfunc(self.seg[k * 2 + 1], self.seg[k * 2 + 2])

    def query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return self.ide_ele
        if a <= l and r <= b:
            return self.seg[k]
        else:
            vl = self.query(a, b, k*2+1, l, (l+r)//2)
            vr = self.query(a, b, k*2+2, (l+r)//2, r)
            return self.segfunc(vl, vr)


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

li = [1 << (ord(s) - ord('a')) for s in S]
seg_tree = SegTree(li)
ans = []
for _ in range(Q):
    i, l, r = input().split()
    i = int(i)
    l = int(l)
    if i == 1:
        seg_tree.update(l-1, 1 << (ord(r) - ord('a')))
    else:
        r = int(r)
        num = seg_tree.query(l-1, r, 0, 0, seg_tree.num)
        ans.append(bin(num).count('1'))

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

n = int(input())
a = [int(input()) for i in range(n)]
m_num = max(a)
m_index = [i for i, x in enumerate(a) if x == m_num]

for i in range(n):
  if i in m_index:
    b = a[i]
    del a[i]
    print(max(a))
    a.insert(i, b)
  else:
    print(m_num)

### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
m_num = max(a)
m_index = [i for i, x in enumerate(a) if x == m_num]

if len(m_index) > 1:
  for i in range(n):
    print(m_num)
else:
  if len(a) == 1:
    print(a[0])
  else:
    m2_num = sorted(a)[-2]
    for i in range(n):
      if (i in m_index):
        print(m2_num)
      else:
        print(m_num)
### BUGGY CODE ###

N,M=map(int,input().split())
if M==0:
  print("Yes")
  exit(0)
INF=10**9+1
dist=[INF]*N
from collections import deque
info=deque()
for i in range(M):
  L,R,d=map(int,input().split())
  L,R=L-1,R-1
  info.append([L,R,d])
  
L,R,d=info.popleft()
dist[L]=0
dist[R]=d

while info:
  L,R,d=info.popleft()
  if dist[L]==INF and dist[R]==INF:
    info.append([L,R,d])
  else:
    if dist[L]!=INF and dist[R]==INF:
      dist[R]=dist[L]+d
    elif dist[L]==INF and dist[R]!=INF:
      dist[L]=dist[R]-d
    else:
      if dist[L]+d!=dist[R]:
        print("No")
        exit(0)
print("Yes")


### FIXED CODE ###

# 人を頂点と見なしたグラフを作る。有向で、逆向きの場合は正負を反転させて辺を張る
# 頂点からの距離を記録し、一致しない箇所があればNG。
# 全ての辺を通るまで続ける。
# 辺の情報を[{0から行ける頂点},{1から行ける頂点},...]で管理する
# 親には進まないようにしてDFSする

N,M = map(int,input().split())
E = [[] for i in range(N)]
for i in range(M):
  L,R,D = map(int,input().split())
  E[L-1].append([R-1,D])
  E[R-1].append([L-1,-D])
from collections import deque
# 頂点、親、距離
INF = 10 ** 10
dist = [INF] * N
for i in range(N):
  if dist[i] != INF:
    continue
  dist[i] = 0
  q = deque()
  q.append(i)
  while q:
    v = q.popleft()
    for child in E[v]:
      if dist[child[0]] == INF:
        dist[child[0]] = dist[v] + child[1]
        q.append(child[0])
      else:
        if dist[child[0]] != dist[v] + child[1]:
          print("No")
          exit(0)
else:
  print("Yes")
### BUGGY CODE ###

#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import sys

EMPTY = (0, 0, frozenset())


def solve(values, nb, max_capacity):
    dp = [[0 for _ in range(max_capacity + 1)] for _ in range(nb + 1)]
    for i in range(1, nb + 1):
        w, v = values[i - 1]
        dp[i] = [dp[i - 1][j] for j in range(w)] + [
            max(dp[i - 1][j], dp[i - 1][j - w] + v) for j in range(w, max_capacity + 1)
        ]
        # for j in range(1, max_capacity + 1):
        #     if w <= j:
        #         dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v)
        #     else:
        #         dp[i][j] = dp[i - 1][j]
    # print("\n".join(map(str, dp)))
    return dp[nb][max_capacity]


def do_job():
    "Do the work"
    # first line is number of test cases
    N, W = map(int, input().split())
    values = []
    for _ in range(N):
        values.append(list(map(int, input().split())))
    result = solve(values, N, W)
    print(result)


def print_output(testcase, result) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case #{}: {}".format(testcase + 1, result))


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())


### FIXED CODE ###

# DP
def main():
    N, W = map(int, input().split())

    dp = [-1] * (W + 1)
    dp[0] = 0
    for _ in range(N):
        w, v = map(int, input().split())
        for i in range(W - w, -1, -1):
            if dp[i] == -1:
                continue
            if dp[i + w] < dp[i] + v:
                dp[i + w] = dp[i] + v
    print(max(dp))


main()
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
dp=[float('inf')]*n
dp[0]=0
for i in range(0,n):
    for j in range(1,k+1):
        if i+j>n-1:
            continue
        dp[i+j]=min(dp[i+j],dp[i]+abs(a[i]-a[i+j]))
print(dp[-1])

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
dp=[float('inf')]*n
dp[0]=0
for i in range(0,n):
    for j in range(1,k+1):
        if i+j>n-1:
            continue
        dp[i+j]=min(dp[i+j],dp[i]+abs(a[i]-a[i+j]))
print(dp[-1])
### BUGGY CODE ###

from collections import deque

def solve():
  h,w=map(int,input().split())
  cy,cx=map(int,input().split())
  dy,dx=map(int,input().split())

  M=[]
  for i in range(2):
    M.append("#"*(w+4))
  for i in range(h):
    M.append("##"+input()+"##")
  for i in range(2):
    M.append("#"*(w+4))

  INF=10**6
  C=[[INF for _ in range(w+4)] for _ in range(h+4)]
  C[-~cy][-~cx]=0
  QA,QB=deque(),deque()
  QA.append((-~cy,-~cx,0))
  W=[[i,j] for i in range(-2,3) for j in range(-2,3) if abs(i)+abs(j)>1]

  while QA:
    h,w,c=QA.popleft()
    QB.append((h,w,c))

    for i,j in [[1,0],[0,1],[-1,0],[0,-1]]:
      dh,dw=h+i,w+j
      if M[dh][dw]=="." and c<C[dh][dw]:
        C[dh][dw]=c
        QA.appendleft((dh,dw,c))

    if QA:
      continue

    while QB:
      h,w,c=QB.popleft()
      for i,j in W:
        dh,dw=h+i,w+j
        if M[dh][dw]=="." and -~c<C[dh][dw]:
          C[dh][dw]=-~c
          QA.append((dh,dw,-~c))

  print(C[-~dy][-~dx] if C[-~dy][-~dx]!=INF else -1)

if __name__ == "__main__":
  solve()


### FIXED CODE ###

from collections import deque

def main():
  h,w=map(int,input().split())
  cy,cx=map(int,input().split())
  dy,dx=map(int,input().split())

  M=["##"+input()+"##" for x in range(h)]
  for i in range(2):
    M.insert(0,"#"*(w+4))
    M.append("#"*(w+4))

  C=[[-1 if M[j][i]=="." else -2 for i in range(w+4)] for j in range(h+4)]
  C[-~cy][-~cx]=0
  QA,QB=deque(),deque()
  QA.append((-~cy,-~cx,0))
  W=[[i,j] for i in range(-2,3) for j in range(-2,3) if abs(i)+abs(j)>1]

  while QA:
    h,w,c=QA.popleft()
    QB.append((h,w,c))

    for i,j in [[1,0],[0,1],[-1,0],[0,-1]]:
      dh,dw=h+i,w+j
      if C[dh][dw]==-1:
        C[dh][dw]=c
        QA.appendleft((dh,dw,c))

    if QA:
      continue

    while QB:
      h,w,c=QB.popleft()
      for i,j in W:
        dh,dw=h+i,w+j
        if C[dh][dw]==-1:
          C[dh][dw]=-~c
          QA.append((dh,dw,-~c))

  print(C[-~dy][-~dx])

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

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

ans1 = abs(N - K)
cnt = 0
if N > ans1:
    while True:
        ans2 = abs(ans1 - K)
        if ans1 > ans2:
            ans1 = ans2
            cnt = 1
            cnt += 1
        else:
            ANS = ans1
            break
elif N <= ans1:
    ANS = N

# print(ans1, ans2)
print(ANS)
# print(cnt)

### FIXED CODE ###

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

t = N % K
ANS = min(t, K-t)
print(ANS)
### BUGGY CODE ###

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

#n,k=5,2
#a=[1,0,0,1,0]

dp=[[0]*(n+1) for i in range(k+1)]

for i in range(n):
    dp[0][i]=a[i]
    
for ki in range(1,k+1):
    ims=[0]*(n+1)
#    print("ki:",ki,"dp[ki-1]:",dp[ki-1])
    for ni in range(n):
#        print("1:",ni,ni-dp[ki-1][ni],ni+dp[ki-1][ni]+1)
        if 0>ni-dp[ki-1][ni]:
            ims[0]+=1
        else:
            ims[ni-dp[ki-1][ni]]+=1
        if n<ni+dp[ki-1][ni]+1:
            ims[n]-=1
        else:
            ims[ni+dp[ki-1][ni]+1]-=1
#        print("ni:",ni,"ims:",ims)
#    print(ki,"ims:",ims)
    imsi=0
    for ni in range(n):
        imsi+=ims[ni]
        dp[ki][ni]=imsi
#    print(dp[ki])
           
for i in range(n):
    print(dp[k][i],end=" ")
print()


### FIXED CODE ###

n,k=map(int,input().split())
dp2=list(map(int,input().split()))
    
k=min(k,41)
for ki in range(1,k+1):
    ims=[0]*(n+1)
    for ni in range(n):
        if 0>ni-dp2[ni]:
            ims[0]+=1
        else:
            ims[ni-dp2[ni]]+=1
        if n<ni+dp2[ni]+1:
            ims[n]-=1
        else:
            ims[ni+dp2[ni]+1]-=1

    dp2[0]=ims[0]
    for ni in range(1,n):
        dp2[ni]=dp2[ni-1]+ims[ni]
    
for i in range(n):
    print(dp2[i],end=" ")
print()