CodeEff/ECCO huggingface dataset:
# Original solution
import sys
input = sys.stdin.buffer.readline

h, w = list(map(int, input().split()))
AA = [list(map(int, input().split())) for _ in range(h)]
BB = [list(map(int, input().split())) for _ in range(h)]

kouho = [[set() for _ in range(w)] for _ in range(h)]

delta = AA[0][0] - BB[0][0]
kouho[0][0].add(delta)
kouho[0][0].add(-delta)
dx = [1, 0]
dy = [0, 1]
for y in range(h):
    for x in range(w):
        for d in range(2):
            nx = x + dx[d]
            ny = y + dy[d]
            if nx < 0 or nx >= w or ny < 0 or ny >= h:
                continue
            delta = AA[ny][nx] - BB[ny][nx]
            for num in kouho[y][x]:
                temp = ((h + w - 2) - (ny + nx) + 1) * 80
                if temp >= abs(num + delta):
                    kouho[ny][nx].add(num + delta)
                if temp >= abs(num - delta):
                    kouho[ny][nx].add(num - delta)
ans = 10 ** 10
for a in kouho[h - 1][w - 1]:
    ans = min(ans, abs(a))
print(ans)


# Optimized solution
import sys

input = sys.stdin.buffer.readline

h, w = list(map(int, input().split()))
AA = [list(map(int, input().split())) for _ in range(h)]
BB = [list(map(int, input().split())) for _ in range(h)]

kouho = [[set() for _ in range(w)] for _ in range(h)]

delta = AA[0][0] - BB[0][0]
kouho[0][0].add(delta)
kouho[0][0].add(-delta)
dx = [1, 0]
dy = [0, 1]
for y in range(h):
    for x in range(w):
        for d in range(2):
            nx = x + dx[d]
            ny = y + dy[d]
            if nx < 0 or nx >= w or ny < 0 or ny >= h:
                continue
            delta = AA[ny][nx] - BB[ny][nx]
            for num in kouho[y][x]:
                if 80 * (h + w) >= abs(num + delta):
                    kouho[ny][nx].add(abs(num + delta))
                if 80 * (h + w) >= abs(num - delta):
                    kouho[ny][nx].add(abs(num - delta))
ans = 10 ** 10
for a in kouho[h - 1][w - 1]:
    ans = min(ans, abs(a))
print(ans)
# Original solution
import sys
from heapq import heappush, heapify

def solve():
    file_input = sys.stdin
    N, R, L = list(map(int, file_input.readline().split()))
    
    hq = []
    m = {}
    for i in range(1, N + 1):
        team = [0, i, 0]
        heappush(hq, team)
        m[i] = team
    
    time = 0
    for line in file_input:
        d, t, x = list(map(int, line.split()))
        m[d][0] -= x
        hq[0][2] += t - time
        time = t
        heapify(hq)
    hq[0][2] += L - time
    ans_team = max(hq, key = lambda x: (x[2], -x[1]))
    print((ans_team[1]))

solve()


# Optimized solution
import sys
from heapq import heappush, heappop

def solve():
    file_input = sys.stdin
    N, R, L = list(map(int, file_input.readline().split()))
    
    hq = []
    m = {}
    for i in range(1, N + 1):
        team = [0, i, 0]
        heappush(hq, team)
        m[i] = team
    
    time = 0
    for line in file_input:
        d, t, x = list(map(int, line.split()))
        hq[0][2] += t - time
        time = t
        
        scored_team = m[d][:]
        scored_team[0] -= x
        heappush(hq, scored_team)
        m[d][2] = -1
        m[d] = scored_team
        
        while hq[0][2] == -1:
            heappop(hq)
    hq[0][2] += L - time
    ans_team = max(hq, key = lambda x: (x[2], -x[1]))
    print((ans_team[1]))

solve()
# Original solution
import sys
from heapq import heappush, heappop, heapreplace

def solve():
    file_input = sys.stdin
    N, R, L = list(map(int, file_input.readline().split()))
    
    pq = [[0, i, 0] for i in range(1, N + 1)]
    m = dict(list(zip(list(range(1, N + 1)), pq)))
    
    pre_t = 0
    for line in file_input:
        d, t, x = list(map(int, line.split()))
        team = pq[0]
        team[2] += t - pre_t
        pre_t = t
        
        if team[1] == d:
            team[0] -= x
            if x < 0:
                heapreplace(pq, team)
        else:
            scored_team = m[d][:]
            scored_team[0] -= x
            heappush(pq, scored_team)
            m[d][2] = -1
            m[d] = scored_team
        
        while pq[0][2] == -1:
            heappop(pq)
    pq[0][2] += L - pre_t
    ans_team = max(pq, key = lambda x: (x[2], -x[1]))
    print((ans_team[1]))

solve()


# Optimized solution
import sys
from heapq import heappush, heappop, heapreplace

def solve():
    file_input = sys.stdin
    N, R, L = list(map(int, file_input.readline().split()))
    
    pq = [[0, i] for i in range(1, N + 1)]
    m = dict(list(zip(list(range(1, N + 1)), pq)))
    time = [0] * (N + 1)
    INVALID = -1
    
    pre_t = 0
    for line in file_input:
        d, t, x = list(map(int, line.split()))
        top_team = pq[0]
        time[top_team[1]] += t - pre_t
        pre_t = t
        
        if top_team[1] == d:
            top_team[0] -= x
            if x < 0:
                heapreplace(pq, top_team)
        else:
            scored_team = m[d][:]
            scored_team[0] -= x
            heappush(pq, scored_team)
            m[d][1] = INVALID
            m[d] = scored_team
        
        while pq[0][1] == INVALID:
            heappop(pq)
    time[pq[0][1]] += L - pre_t
    print((time.index(max(time))))

solve()
# Original solution
n, r, l = list(map(int, input().split()))
leaf_num = 1
while leaf_num < n:
  leaf_num *= 2
tree = [None] * (leaf_num * 2 - 1)

for i in range(n):
  tree[leaf_num - 1 + i] = (i, 0)

def set_value(index):
  if leaf_num - 1 <= index <= leaf_num * 2 - 2:
    return tree[index]
  t1 = set_value(index * 2 + 1)
  t2 = set_value(index * 2 + 2)
  if t1 == None and t2 == None:
    return None
  else:
    tree[index] = (t1[0], t1[1])
    return tree[index]

def update(index):
  if index <= -1:return 
  elif leaf_num - 1 <= index <= leaf_num * 2 - 2:
    update((index - 1) // 2)
  else:
    left = tree[index * 2 + 1]
    right = tree[index * 2 + 2]
    if right == None:
      tree[index] = left
    else:
      if left[1] < right[1]:
        tree[index] = right
      else:
        tree[index] = left
    update((index - 1) // 2)

set_value(0)
score = [0] * n
last_time = 0
for _ in range(r):
  d, t, x = list(map(int, input().split()))
  index, _ = tree[0]
  score[index] += t - last_time
  last_time = t
  d -= 1
  tree[leaf_num - 1 + d] = (tree[leaf_num - 1 + d][0], tree[leaf_num - 1 + d][1] + x)
  update(leaf_num - 1 + d)

score[tree[0][0]] += l - last_time
print((score.index(max(score)) + 1))


# Optimized solution
import sys
input = sys.stdin.readline

def main():
  n, r, l = list(map(int, input().split()))
  leaf_num = 1
  while leaf_num < n:
    leaf_num *= 2
  INF = 10 ** 20
  tree = [None] * (leaf_num * 2 - 1)
  save = [0] * n
  
  for i in range(n):
    tree[leaf_num - 1 + i] = i
  
  def set_value(index):
    if leaf_num - 1 <= index <= leaf_num * 2 - 2:
      return tree[index]
    t1 = set_value(index * 2 + 1)
    t2 = set_value(index * 2 + 2)
    tree[index] = t1
    return tree[index]
  
  def update(index):
    index = (index - 1) // 2
    while index >= 0:
      left = tree[index * 2 + 1]
      right = tree[index * 2 + 2]
      if right == None:
        index = (index - 1) // 2
        continue
      tree[index] = right if save[right] > save[left] else left
      index = (index - 1) // 2

  
  set_value(0)
  score = [0] * n
  last_time = 0
  for _ in range(r):
    d, t, x = list(map(int, input().split()))
    score[tree[0]] += t - last_time
    last_time = t
    save[d - 1] += x
    update(leaf_num + d - 2)
  
  score[tree[0]] += l - last_time
         
  print((score.index(max(score)) + 1))
main()
# Original solution
n, r, l = list(map(int, input().split()))
point, time = [], []

for i in range(n):
    point.append(0)
    time.append(0)

now, tv = 0, 0
for i in range(r):
    d, t, x = list(map(int, input().split()))
    time[tv] += t - now
    now = t
    point[d-1] += x
    m = sorted(point, reverse=True)[0]
    i = 0
    while True:
        if point[i] == m:
            tv = i
            break
        i += 1

time[tv] += l - now

m = sorted(time, reverse=True)[0]
i = 0
while True:
    if time[i] == m:
        print((i+1))
        break
    i += 1

# Optimized solution
n, r, l = list(map(int, input().split()))
point, time = [], []
rev = {0: []}
for i in range(n):
    point.append(0)
    time.append(0)
    rev[0].append(i)

now, tv = 0, 0
for i in range(r):
    d, t, x = list(map(int, input().split()))
    time[tv] += t - now
    now = t
    rev[point[d-1]].remove(d-1)
    point[d-1] += x
    if point[d-1] in rev:
        rev[point[d-1]].append(d-1)
    else:
        rev[point[d-1]] = [d-1]
    if tv != d-1: 
        if point[tv] == point[d-1]:
            tv = min(tv, d-1)
        elif point[tv] < point[d-1]:
            tv = d-1
    elif x < 0:
        tv = min(rev[max(point)])

time[tv] += l - now

m = max(time)
i = 0
while True:
    if time[i] == m:
        print((i+1))
        break
    i += 1
# Original solution
n,r,l=list(map(int,input().split()))
log=[list(map(int,input().split())) for i in range(r)]
log.insert(0,[1,0,0])
log.append([1,l,0])
id_t=[0]*n
id_x=[0]*n
max_id=0
for i in range(1,r+2):
	cur_id=log[i][0]-1
	id_t[max_id]+=log[i][1]-log[i-1][1]
	id_x[cur_id]+=log[i][2]
	if log[i][2]<0:
		max_id=id_x.index(max(id_x))
	elif id_x[max_id]<id_x[cur_id] or (id_x[max_id]==id_x[cur_id] and max_id>cur_id):
		max_id=cur_id
print(id_t.index(max(id_t))+1)

# Optimized solution
n,r,l=list(map(int,input().split()))
log=[list(map(int,input().split())) for i in range(r)]
log.insert(0,[1,0,0])
log.append([1,l,0])
id_t=[0]*n
id_x=[0]*n
max_id=0
for i in range(1,r+2):
	cur_id=log[i][0]-1
	id_t[max_id]+=log[i][1]-log[i-1][1]
	id_x[cur_id]+=log[i][2]
	if cur_id==max_id and log[i][2]<0:
		max_id=id_x.index(max(id_x))
	elif id_x[max_id]<id_x[cur_id] or (id_x[max_id]==id_x[cur_id] and max_id>cur_id):
		max_id=cur_id
print(id_t.index(max(id_t))+1)
# Original solution
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0282

"""
import sys
from sys import stdin
from heapq import heappop, heappush
input = stdin.readline


pq = []                         # list of entries arranged in a heap
entry_finder = {}               # mapping of tasks to entries
REMOVED = 100000000      # placeholder for a removed task

def add_team(score, team):
    if team in entry_finder:
        remove_team(team)
    entry = [-score, team]
    entry_finder[team] = entry
    heappush(pq, entry)

def remove_team(team):
    entry = entry_finder.pop(team)
    entry[-1] = REMOVED

def pop_team():
    while pq:
        score, team = heappop(pq)
        if team is not REMOVED:
            del entry_finder[team]
            return team
    raise KeyError('pop from an empty priority queue')


def main(args):
    N, R, L = list(map(int, input().split()))
    on_tv = [0] * (N + 1)       #  ????????????????????¬???????????£??????????????????????¨?
    scores = [0] * (N + 1)       #  ????????????????????¨?????????

    for i in range(1, N+1):
        add_team(0, i)

    last_time = 0
    for i in range(R):
        d, t, x = [int(x) for x in input().split()]
        team = pop_team()
        on_tv[team] += (t - last_time)
        if d != team:
            add_team(scores[team], team)

        scores[d] += x
        add_team(scores[d], d)
        last_time = t

    t = L
    team = pop_team()
    on_tv[team] += (t - last_time)

    print((on_tv.index(max(on_tv))))


if __name__ == '__main__':
    main(sys.argv[1:])

# Optimized solution
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0282

"""
import sys
from sys import stdin
from heapq import heappop, heappush
input = stdin.readline


pq = []                         # list of entries arranged in a heap
entry_finder = {}               # mapping of tasks to entries
REMOVED = float('inf')      # placeholder for a removed task

def add_team(score, team):
    if team in entry_finder:
        remove_team(team)
    entry = [-score, team]
    entry_finder[team] = entry
    heappush(pq, entry)

def remove_team(team):
    entry = entry_finder.pop(team)
    entry[-1] = REMOVED

def pop_team():
    while pq:
        score, team = heappop(pq)
        if team is not REMOVED:
            del entry_finder[team]
            return team
    #raise KeyError('pop from an empty priority queue')


def main(args):
    N, R, L = list(map(int, input().split()))
    on_tv = [0] * (N + 1)       #  ????????????????????¬???????????£??????????????????????¨?
    scores = [0] * (N + 1)       #  ????????????????????¨?????????

    for i in range(1, N+1):
        add_team(0, i)

    last_time = 0
    for i in range(R):
        d, t, x = [int(x) for x in input().split()]
        team = pop_team()
        on_tv[team] += (t - last_time)
        if d != team:
            add_team(scores[team], team)

        scores[d] += x
        add_team(scores[d], d)
        last_time = t

    t = L
    team = pop_team()
    on_tv[team] += (t - last_time)

    print((on_tv.index(max(on_tv))))


if __name__ == '__main__':
    main(sys.argv[1:])
# Original solution
import copy

def movable_state(state):
    x, y = None, None
    for i in range(3):
        for j in range(3):
            if state[i][j] == 0:
                x, y = i, j
                break

    rsts = []
    for r, c in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]:
        if 0 <= r and r < 3 and 0 <= c and c < 3:
            rst = copy.deepcopy(state)
            rst[x][y], rst[r][c] = rst[r][c], rst[x][y]
            rsts.append(rst)
    return rsts

def hist_check(state, depth):
    for i in range(depth-1):
        for hist in state_history[i]:
            if hist == state:
                return True
    return False

puzzle = [list(map(int, input().split(' '))) for i in range(3)]
state_history = [[puzzle]]

goal = [[1, 2, 3], [4, 5, 6], [7, 8, 0]]
exchange_num = 0
depth = 0
still_not = True
while still_not:
    depth += 1
    state_history.append([])
    for hist in state_history[depth-1]:
        next_states = movable_state(hist)
        for next_stat in next_states:
            if hist_check(next_stat, depth): continue
            if next_stat == goal:
                still_not = False
                break
            state_history[depth].append(next_stat)
        if not still_not: break
print(depth)



# Optimized solution
import copy

def movable_state(state):
    x, y = None, None
    for i in range(3):
        for j in range(3):
            if state[3*i+j] == 0:
                x, y = i, j
                break

    rsts = []
    for r, c in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]:
        if 0 <= r and r < 3 and 0 <= c and c < 3:
            rst = copy.copy(state)
            rst[3*x+y], rst[3*r+c] = rst[3*r+c], rst[3*x+y]
            rsts.append(rst)
    return rsts

def hist_check(state, depth):
    for i in range(depth-2, -1, -1):
        for hist in state_history[i]:
            if hist == state:
                return True
    return False

puzzle = []
for i in range(3):
    puzzle.extend(list(map(int, input().split(' '))))
state_history = [[puzzle]]

goal = [1, 2, 3, 4, 5, 6, 7, 8, 0]
exchange_num = 0
depth = 0
still_not = True
while still_not:
    depth += 1
    state_history.append([])
    for hist in state_history[depth-1]:
        next_states = movable_state(hist)
        for next_stat in next_states:
            if hist_check(next_stat, depth): continue
            if next_stat == goal:
                still_not = False
                break
            state_history[depth].append(next_stat)
        if not still_not: break
print(depth)
# Original solution
from collections import deque
from copy import deepcopy, copy
dy = [-1, 0, 0, 1]
dx = [0, -1, 1, 0]
N = 3
def MAIN():
    MAP = tuple(sum([input().split() for _ in range(N)], []))
    y0, x0 = divmod(MAP.index("0"), N)
    goal = ('1', '2', '3', '4', '5', '6', '7', '8', '0')
    ans = 0
    dp = deque([[y0, x0, 0, MAP]])
    LOG = {MAP}
    while dp:
        y, x, cnt, M = dp.popleft()
        if M == goal:
            print(cnt)
            break
        cnt += 1
        yx = y * N + x
        for ny, nx in ((y - 1, x), (y, x - 1), (y, x + 1), (y + 1, x)):
            if 0 <= ny < N and 0 <= nx < N:
                CM = list(deepcopy(M))
                nyx = ny * N + nx
                CM[yx], CM[nyx] = CM[nyx], CM[yx]
                CM = tuple(CM)
                if not CM in LOG:
                    dp.append([ny, nx, cnt, CM])
                    LOG.add(CM)
MAIN()



# Optimized solution
from collections import deque
from copy import deepcopy, copy
dy = [-1, 0, 0, 1]
dx = [0, -1, 1, 0]
N = 3
def g(i, j, a):
    t = a // (10 ** j) % 10
    return a - t * (10 ** j) + t * (10 ** i)
def MAIN():
    m = {8:{7, 5}, 7:{8, 6, 4}, 6:{7, 3}, 5:{8, 4, 2}, 4:{7, 5, 3, 1}, 3:{6, 4, 0}, 2:{5, 1}, 1:{4, 2, 0}, 0:{3, 1}}
    MAP = "".join(input().replace(" ", "") for _ in range(N))
    start = 8 - MAP.find("0")
    MAP = int(MAP)
    goal = ('1', '2', '3', '4', '5', '6', '7', '8', '0')
    goal = 123456780
    dp = deque([(0, start, MAP)])
    LOG = {MAP}
    while dp:
        cnt, yx, M = dp.popleft()
        if M == goal:
            print(cnt)
            break
        cnt += 1
        for nyx in m[yx]:
            CM = g(yx, nyx, M)
            if not CM in LOG:
                dp.append((cnt, nyx, CM))
                LOG.add(CM)
MAIN()
# Original solution
from heapq import heapify, heappush, heappop
from collections import deque
from copy import deepcopy, copy
N = 3
m = {8:{7, 5}, 7:{8, 6, 4}, 6:{7, 3}, 5:{8, 4, 2}, 4:{7, 5, 3, 1}, 3:{6, 4, 0}, 2:{5, 1}, 1:{4, 2, 0}, 0:{3, 1}}
def g(i, j, a):
    if i > j:
        i, j = j, i
    return a[:i] + a[j] + a[i + 1:j] + a[i] + a[j + 1:]
def MAIN():
    MAP = "".join(input().replace(" ", "") for _ in range(N))
    goal = "123456780"
    if MAP == goal:
        print((0))
        return
    start = MAP.find("0")
    dp = [(0, MAP, start)]
    LOG = {MAP}
    while dp:
        cnt, M, yx = heappop(dp)
        cnt += 1
        for nyx in m[yx]:
            CM = g(yx, nyx, M)
            if not CM in LOG:
                if CM == goal:
                    print(cnt)
                    return
                heappush(dp, (cnt, CM, nyx))
                LOG.add(CM)
MAIN()



# Optimized solution
from collections import deque
N = 3
def g(i, j, a):
    if i > j:
        i, j = j, i
    return a[:i] + a[j] + a[i + 1:j] + a[i] + a[j + 1:]
goal = "123456780"
def solve():
    m = {8:{7, 5}, 7:{8, 6, 4}, 6:{7, 3}, 5:{8, 4, 2}, 4:{7, 5, 3, 1}, 3:{6, 4, 0}, 2:{5, 1}, 1:{4, 2, 0}, 0:{3, 1}}
    MAP = "".join(input().replace(" ", "") for _ in range(N))
    if MAP == goal:
        return 0
    start = MAP.find("0")
    dp = deque([(0, MAP, start, 1), (0, goal, 8, 0)])
    TABLE = {MAP:(1, 0), goal:(0, 0)}
    while dp:
        cnt, M, yx, flg = dp.popleft()
        cnt += 1
        for nyx in m[yx]:
            CM = g(yx, nyx, M)
            if CM in TABLE:
                if TABLE[CM][0] != flg:
                    return TABLE[CM][1] + cnt
                continue
            TABLE[CM] = (flg, cnt)
            dp.append((cnt, CM, nyx, flg))
def MAIN():
    print((solve()))
MAIN()
# Original solution
import sys, itertools
f = sys.stdin

start = [line.split() for line in f]
start = tuple(int(x) for y in start for x in y)
end =(1, 2, 3, 4, 5, 6,7, 8, 0)

d = {start:0}

def next_board(b):
    brank = b.index(0)
    if brank % 3:
        yield b[:brank - 1] + (b[brank], b[brank - 1]) + b[brank + 1:]
    if brank // 3:
        yield b[:brank - 3] + (b[brank],)+ b[brank - 2:brank] +  (b[brank - 3],) + b[brank + 1:]
    if brank % 3 != 2:
        yield b[:brank] + (b[brank + 1], b[brank]) + b[brank + 2:]
    if brank // 3 != 2:
        yield b[:brank] + (b[brank + 3],)+ b[brank + 1:brank + 3] +  (b[brank],) + b[brank + 4:]

queue = set([start])
while len(queue):
    u = queue.pop()
    for b in next_board(u):
        if b not in d or d[b] > d[u] + 1:
            d[b] = d[u] + 1
            queue.update([b])
        
print((d[end]))

# Optimized solution
from sys import stdin
readline = stdin.readline


adjacent = (
    (1, 3),        # 0
    (0, 2, 4),     # 1
    (1, 5),        # 2
    (0, 4, 6),     # 3
    (1, 3, 5, 7),  # 4
    (2, 4, 8),     # 5
    (3, 7),        # 6
    (4, 6, 8),     # 7
    (5, 7)         # 8
)


def next_board(board, space, prev):
    for nxt in adjacent[space]:
        if nxt == prev:
            continue
        b = board[:]
        b[space], b[nxt] = b[nxt], 0
        yield b, nxt
from heapq import heappop, heappush

end = [1, 2, 3, 4, 5, 6, 7, 8, 0]

# ???????????¨????????°
FORE = 1
BACK = 0


def search(start):
    if start == end:
        return 0
    table = {}

    table[tuple(start)] = (FORE, 0)
    table[tuple(end)] = (BACK, 0)

    heap = [(0, start, start.index(0), None, FORE), (0, end, end.index(0), None, BACK)]
    while heap:
        i, board, space, prev, direction = heappop(heap)
        i += 1
        for b, nxt in next_board(board, space, prev):
            key = tuple(b)
            if key in table:
                if table[key][0] != direction:
                    return table[key][1] + i
                continue
            table[key] = (direction, i)
            if b == end:
                return i
            heappush(heap, (i, b, nxt, space, direction))


def main():
    start = (list(map(int, readline().split())) for _ in range(3))
    start = [y for x in start for y in x]
    print((search(start)))
main()
# Original solution
# -*- coding: utf-8 -*-

from collections import deque
import copy

class Puzzle(list):
    def __init__(self):
        list.__init__(self)
        self.space = None
        self.path = ""
    
    def __hash__(self):
        return hash(str(self[:]))

if __name__ == '__main__':
    
    N = 3
    N2 = 9
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    d = ["u", "l", "d", "r"]

    p = Puzzle()
    for i in range(N):
        p += [int(x) for x in input().split()]
    for i in range(N2):
        if p[i] == 0:
            p[i] = N2
            p.space = i
    target = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    def isTarget(p):
        return p[:] == target[:]

    def bfs(s):
        Q = deque()
        V = set()
        Q.append(s)
        V.add(s)
        while Q:
            u = Q.popleft()
            if isTarget(u):
                return u.path
            sx = u.space // N
            sy = u.space % N
            for r in range(4):
                tx = sx + dx[r]
                ty = sy + dy[r]
                if not (0<= tx < N and 0 <= ty < N):
                    continue
                v = copy.copy(u)
                v[u.space], v[tx * N + ty] = v[tx * N + ty], v[u.space]
                v.space = tx * N + ty
                if not v in V:
                    V.add(v)
                    v.path += d[r]
                    Q.append(v)

        return "unsolvable"

    ans = bfs(p)
    print((len(ans)))





# Optimized solution
# -*- coding: utf-8 -*-

from collections import deque
import copy

class Puzzle(list):
    def __init__(self):
        list.__init__(self)
        self.space = None
        self.path = ""
    
    def __hash__(self):
        return hash(str(self[:]))

if __name__ == '__main__':
    
    N = 3
    N2 = 9
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    d = ["u", "l", "d", "r"]

    p = Puzzle()
    for i in range(N):
        p += [int(x) for x in input().split()]
    for i in range(N2):
        if p[i] == 0:
            p[i] = N2
            p.space = i
    target = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    def isTarget(p):
        return p[:] == target[:]

    def bfs(s):
        Q = deque()
        V = set()
        Q.append(s)
        V.add(s)
        while Q:
            u = Q.popleft()
            if isTarget(u):
                return u.path
            sx = u.space // N
            sy = u.space % N
            for r in range(4):
                tx = sx + dx[r]
                ty = sy + dy[r]
                if not (0<= tx < N and 0 <= ty < N):
                    continue
                v = copy.copy(u)
                change = tx * N + ty
                v[u.space], v[change] = v[change], v[u.space]
                v.space = change
                if not v in V:
                    V.add(v)
                    v.path += d[r]
                    Q.append(v)

        return "unsolvable"

    ans = bfs(p)
    print((len(ans)))