Harryxun/stf_run huggingface dataset:
import string
if __name__=="__main__":
    s = list(input())
    t = list(input())
    flag = False
    if s is t:
        print("No")
        exit()
    dic = string.ascii_lowercase
    c = 0
    for j in range(len(s)):
        if s[j] in t:
            c+=1
    if c==len(s) and c<len(t):
        print("Yes")
        exit()
    for i in range(len(dic)):
        if s.__contains__(dic[i]) and t.__contains__(dic[i]):
            flag = True
        if flag and s.__contains__(dic[i]) and not t.__contains__(dic[i]):
            for j in range(i+1,len(dic)):
                if t.__contains__(dic[j]):
                    print("Yes")
                    exit()
    print("No")


### FIXED CODE ###

if __name__=="__main__":
    a = list(map(int,input().split(" ")))
    b = (a[0]+a[1])/2
    if b%1:
        print(int(b)+1)
    else:
        print(int(b))
a,b=int(input().split())
if a-b＊2<0:
  
  print(0)
else:
  print(a-b＊2)
  


### FIXED CODE ###

a,b=map(int,input().split())
if a-b*2<=0:
  
  print(0)
else:
  print(a-b*2)
import numpy as np
while True:
    n= int(input())
    if n == 0:
        break
    a=map(int, input().split())
    print(np.std(a))

### FIXED CODE ###

while True:
    n = int( input() )
    if n==0:
        break
    a=list(map(int, input().split()))
    m=sum(a)/n
    s=0
    for i in a:
        s+=(i-m)**2
    print( ( s/n)**0.5 )
N=int(input())
 
if N < 10:
  print(N)
  
elif N < 100:
  print(9)

  
elif N < 1000:
  print(9+ N-99)
  
  
elif N < 10000:
  print(909)
  
elif N < 100000:
  print(909 + N - 9999)

else:
  print(90909)

### FIXED CODE ###

A, B, C = (int(i) for i in input().split(" "))
 
D = A - B

 
if C - D <= 0:
  print(0)
else:
  print(C-D)
K =int(input())
A =[1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
print(A[K])

### FIXED CODE ###

K =int(input())
A =[1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
print(A[K-1])
s = str(input())

if s=="Sunny":
    print("Cloudy")
else if s=="Cloudy":
    print("Rainy")
else if s=="Rainy":
    print("Sunny")


### FIXED CODE ###

s = str(raw_input())

if s=="Sunny":
    print ("Cloudy")
if s=="Cloudy":
    print ("Rainy")
if s=="Rainy":
    print ("Sunny")
a, b = map(int, input().split())
print('GREATER' if a > b else 'LESS' if a < b else 'EQUAL')


### FIXED CODE ###

a = int(input())
b = int(input())
print('GREATER' if a > b else 'LESS' if a < b else 'EQUAL')
N = int(input
med = N // 2
a_list = []
b_list = []
for i in range(N):
    ab = list(map(int, input().split()))
    a_list.append(ab[0])
    b_list.append(ab[1])

if N%2 == 1:
    a_med = a_list[t]
    b_median = b_list[t]
    print(b_list-a_list+1)
elif N%2 == 0:
    a_median = (a_list[t-1]+a_list[t])/2
    b_median = (b_list[t-1]+b_list[t])/2
    print(int(2*(b_median-a_median)+1))


### FIXED CODE ###

N = int(input())
t = N // 2
a_list = []
b_list = []
for i in range(N):
    ab = list(map(int, input().split()))
    a_list.append(ab[0])
    b_list.append(ab[1])

a_list = sorted(a_list)
b_list = sorted(b_list)

if N%2 == 1:
    a_median = a_list[t]
    b_median = b_list[t]
    print(b_median-a_median+1)
elif N%2 == 0:
    a_median = (a_list[t-1]+a_list[t])/2
    b_median = (b_list[t-1]+b_list[t])/2
    print(int(2*(b_median-a_median)+1))
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(N)]
AB.sort(key = lambda x: x[0])

total = 0
i = 0

while True:
    total += AB[i][1]
    if total < m:
        i += 1
    else:
        break

ans = 0
for j in range(i):
    ans += AB[j][0]*AB[j][1]
ans += (m - sum(AB[p][1] for p in range(0,i))) * AB[i][0]

### FIXED CODE ###

N, M = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(N)]
AB.sort(key = lambda x: x[0])

total = 0
i = 0

while True:
    total += AB[i][1]
    if total < M:
        i += 1
    else:
        break

ans = 0
for j in range(i):
    ans += AB[j][0]*AB[j][1]
ans += (M - sum(AB[p][1] for p in range(0,i))) * AB[i][0]
print(ans)
a = [i in input().split()]
nums = [int(i) in input().split()]
thr = input()
if(thr == a[0]):
	nums[0] -= 1
else:
	nums[1] -= 1
print(nums[0],nums[1])

### FIXED CODE ###

a = [i for i in input().split()]
nums = [int(i) for i in input().split()]
thr = input()
if(thr == a[0]):
	nums[0] -= 1
else:
	nums[1] -= 1
print(nums[0],nums[1])
s,t=input().split()
u=0
for i in range(0,len(s)):
    if s[i]!=t[i]:
        u+=1
print(u)


### FIXED CODE ###

s=input()
t=input()
u=0
for i in range(0,len(s)):
    if s[i]!=t[i]:
        u+=1
print(u)
H1 = int(input())
M1 = int(input())
H2 = int(input())
M2 = int(input())
K = int(input())

### FIXED CODE ###

import sys
readline = sys.stdin.buffer.readline

h1, m1, h2, m2, k = map(int, readline().split())
print(60 * (h2 - h1) + m2 - m1 - k)
def nibutan(A,B,X,L,H):
	M=(H+L)//2
	tmp=A*M+B*len(str(M))
	if M == 0:
		return 0
	elif tmp==X:
		return M
	elif tmp<X:
		if M=999999999:
			return 999999999
		else:
			return nibutan(A,B,X,M,H)
	elif tmp>X:
		tmp_2=A*(M-1)+B*len(str(M-1))
		if tmp_2<X:
			return M-1
		else:
			return nibutan(A,B,X,L,M)

A,B,X=map(int,input().split())
if X>=A*1000000000+B*10:
	print(1000000000)
else:
	ans=nibutan(A,B,X,0,1000000000)
	print(ans)



### FIXED CODE ###

S = input()

mp = {
    'SUN':7,
    'MON':6,
    'TUE':5,
    'WED':4,
    'THU':3,
    'FRI':2,
    'SAT':1
}

print(mp[S])
import bisect

n = int(input())
s = list(input())
q = int(input())
l = [[] for i in range(26)]
for i in range(n):
    l[ord(s[i])-ord("a")].append(i)


for i in range(q):
    x,y,z = input().split()
    if int(x) == 1:
        if s[int(y)-1] == z:
            continue
        index = bisect.bisect_left(l[ord(s[int(y)-1])-ord("a")],int(y)-1)
        l[ord(s[int(y)-1])-ord("a")].pop(index)
        index = bisect.bisect_left(l[ord(z)-ord("a")],int(y)-1)
        l[ord(z)-ord("a")].insert(index,int(y)-1)
    if int(x) == 2:
        count = 0
        for j in l:
            index = bisect.bisect_left(j,int(y)-1)
            if index < len(j) and j[index] < int(z):
                count += 1
        print(count)





### FIXED CODE ###

import bisect

n = int(input())
s = list(input())
q = int(input())
l = [[] for i in range(26)]
for i in range(n):
    l[ord(s[i])-ord("a")].append(i)


for i in range(q):
    x,y,z = input().split()
    if int(x) == 1:
        if s[int(y)-1] == z:
            continue
        index = bisect.bisect_left(l[ord(s[int(y)-1])-ord("a")],int(y)-1)
        l[ord(s[int(y)-1])-ord("a")].pop(index)
        index = bisect.bisect_left(l[ord(z)-ord("a")],int(y)-1)
        l[ord(z)-ord("a")].insert(index,int(y)-1)
        s[int(y)-1] = z
    if int(x) == 2:
        count = 0
        for j in l:
            index = bisect.bisect_left(j,int(y)-1)
            if index < len(j) and j[index] < int(z):
                count += 1
        print(count)
INFTY = 10**9+7
N = int(input())
A = list(map(int,input().split()))
C = {}
for i in range(N):
    if A[i] not in C:
        C[A[i]] = 0
    C[A[i]] += 1
if N%2==0:
    flag = 0
    for i in range(1,N,2):
        if C[i]==2:
            pass
        else:
            flag = 1
            break
else:
    flag = 0
    for i in range(2,N,2):
        if C[i]==2:
            pass
        else:
            flag = 1
            break
    if 0 not in C or C[0]!=1:
        flag = 1
if flag==0:
    cnt = 1
    for i in range(N//2):
        cnt = (cnt*2)%INFTY
else:
    cnt = 0
print(cnt)

### FIXED CODE ###

INFTY = 10**9+7
N = int(input())
A = list(map(int,input().split()))
C = {}
for i in range(N):
    if A[i] not in C:
        C[A[i]] = 0
    C[A[i]] += 1
if N%2==0:
    flag = 0
    for i in range(1,N,2):
        if i in C and C[i]==2:
            pass
        else:
            flag = 1
            break
else:
    flag = 0
    for i in range(2,N,2):
        if i in C and C[i]==2:
            pass
        else:
            flag = 1
            break
    if 0 not in C or C[0]!=1:
        flag = 1
cnt = 0
if flag==0:
    cnt = 1
    for i in range(N//2):
        cnt = (cnt*2)%INFTY
print(cnt)
a,b = map(int,input().split())

if a%b == 0:
    print("-1")

else:
    print(X)

    

### FIXED CODE ###

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

if a%b == 0:
    print("-1")

else:
    print(a)
X, K, D = map(int,input().split())
import math
f = math.fabs 
def solve(x,k,d):
    if k%2 ==0:
        if k == 0:
            return int(f(x))
        elif f(x-2*d) > f(x) and f(x+2*d) > f(x):
            return int(f(x))
        elif k%4 == 0:
            return int(min(solve(x-k//2*d,k//2,d),solve(x+k//2*d,k//2,d)))
        elif k%4 != 0:
            return int(min(solve(x-(k+2)//2*d,(k-2)//2,d),solve(x+(k+2)//2*d,(k-2)//2,d)))
    elif k%2 != 0:
        if k == 1:
            return int(min(f(x-d),f(x+d)))
        else:
            return int(min(solve(x-(k+1)//2*d,(k-1)//2,d),solve((x+(k+1)//2*d,(k-1)//2,d))))
print(solve(X,K,D))

### FIXED CODE ###

import math
X, K, D = map(int,input().split())
X = math.fabs(X)
ans = 0
E = X//D
if E > K:
    ans = X - K * D
elif K%2 == E%2:
    ans = X-E*D
else:
    ans = -X+(E+1)*D
print(int(ans))
N = int(input())
h = list(map(int,input().split()))

mincost = [-1] * N

def calcMinCost(n):
#    print("calcMinCost(" + str(n) + ")")
#    print(mincost)
    if(n == 0):
        mincost[0] = 0
        return 0
    elif(n == 1):
        mincost[1] = abs(h[1] - h[0])
        return abs(h[1] - h[0])
    elif(mincost[n-1] != -1 and mincost[n-2] != -1):
        a = mincost[n-1] + abs(h[n-1] - h[n])
        b = mincost[n-2] + abs(h[n-2] - h[n])
        mincost[n] = a if a < b else b
        return mincost[n]
    elif(mincost[n-1] != -1):
        a = mincost[n-1] + abs(h[n-1] - h[n])
        b = calcMinCost(n-2) + abs(h[n-2] - h[n])
        mincost[n] = a if a < b else b
        return mincost[n]
    elif(mincost[n-2] != -1):
        a = calcMinCost(n-1) + abs(h[n-1] - h[n])
        b = mincost[n-2] + abs(h[n-2] - h[n])
        mincost[n] = a if a < b else b
        return mincost[n]
    else:
        a = calcMinCost(n-1) + abs(h[n-1] - h[n])
        b = calcMinCost(n-2) + abs(h[n-2] - h[n])
        mincost[n] = a if a < b else b
        return mincost[n]


print(calcMinCost(N-1))


### FIXED CODE ###

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

mincost = [-1] * N
mincost[0] = 0
mincost[1] = abs(h[1] - h[0])

for i in range(2,N):
    a = mincost[i-2] + abs(h[i] - h[i-2])
    b = mincost[i-1] + abs(h[i] - h[i-1])
    mincost[i] = a if a < b else b

print(mincost[N-1])
import sys
input = sys.stdin.readline
N = int(input())
S = input().rstrip().split()
from collections import Counter
c = Counter(S)
if len(c.keys) == 4:
    print("Four")
else:
    print("Three")

### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
S = input().rstrip().split()
from collections import Counter
c = Counter(S)
if len(c.keys()) == 4:
    print("Four")
else:
    print("Three")
import math
from functools import reduce
n,X=map(int,input().split())
x=list(map(int,input().split()))
y=[]
for i in range(n):
  y.append(abs(x[i]-X))
def GCD(*numbers):
  return reduce(math.gcd,numbers)
print(GCD(*y))
  
  


### FIXED CODE ###

import fractions
import sys
n,X=map(int,input().split())
x=list(map(int,input().split()))
y=[]
if n==1:
  print(abs(x[0]-X))
  sys.exit()
for i in range(n):
  y.append(abs(x[i]-X))
G=100000000000
for j in range(n-1):
  G=min(G,fractions.gcd(y[j],y[j+1]))
print(G)
a,b = map(int, input().split())
if a%3=0 or b%3=0 or (a+b)%3=0:
  print("Possible")
else:
  print("Impossible")

### FIXED CODE ###

a,b = map(int, input().split())
if a%3==0 or b%3==0 or (a+b)%3==0:
  print("Possible")
else:
  print("Impossible")
N = int(input())
array = []

for i in range(N-1):
  _input = str(input()).split(' ')
  array.append((int(_input[0]), int(_input[1], int(_input[2]))))

for i in range(N-1):
  time = array[i][0] + array[i][1]
  for j in range(i+1, N-1):
    if array[j][1] > time:
      time = array[j][1]
    elif time % array[j][2] != 0:
      time = time - time % array[j][2] + array[j][2]
    time = time + array[j][0]
  print(time)

print(0)

### FIXED CODE ###

N = int(input())
array = []

for i in range(N-1):
  _input = str(input().replace('\r','')).split(' ')
  array.append((int(_input[0]), int(_input[1]), int(_input[2])))

for i in range(N-1):
  time = array[i][0] + array[i][1]
  for j in range(i+1, N-1):
    if array[j][1] > time:
      time = array[j][1]
    elif time % array[j][2] != 0:
      time = time - time % array[j][2] + array[j][2]
    time = time + array[j][0]
  print(time)

print(0)
a,b = int(input())
if a*b % 2 = 1:
  print("Odd")
else:
  print("Even")



### FIXED CODE ###

a, b = map(int,input().split())
if a*b % 2 == 1:
  print("Odd")
else:
  print("Even")
cnt = 0
s = input().lower()
while 1:
    line = input()
    if line == "END_OF_TEXT":
        break
    for s in line.lower().split():
print(cnt)

### FIXED CODE ###

cnt = 0
s = input().lower()
while 1:
    line = input()
    if line == "END_OF_TEXT":
        break
    for w in line.lower().split():
        if w == s:
            cnt+=1
print(cnt)
if __name__ == '__main__':
    N = int(input())
    kv = collections.defaultdict(int)
    max_cnt = 0
    res = []
    for _ in range(N):
        word = input()
        kv[word] += 1
        if kv[word] == max_cnt:
            res.append(word)
        elif kv[word] > max_cnt:
            res = [word]
            max_cnt = kv[word]
    print('\n'.join(sorted(res)))

### FIXED CODE ###

import collections

if __name__ == '__main__':
    N = int(input())
    kv = collections.defaultdict(int)
    max_cnt = 0
    res = []
    for _ in range(N):
        word = input()
        kv[word] += 1
        if kv[word] == max_cnt:
            res.append(word)
        elif kv[word] > max_cnt:
            res = [word]
            max_cnt = kv[word]
    for s in sorted(res):
        print(s)
N = int(input())
ans = 0

for i in range(1, N+1):
  Y = N // j
  ans += Y * (Y+1) * j / 2
  
print(int(ans))

### FIXED CODE ###

N = int(input())
ans = 0
 
for i in range(1, N+1):
  Y = N // i
  ans += Y * (Y+1) * i / 2
  
print(int(ans))
#!/usr/bin/env python3
from collections import defaultdict
import sys
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
def LI(): return list(map(int, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def LIR(n):
    res = [None] * n
    for i in range(n):
        l,r = map(int, input())
        res[i] = (l, r, i)
    return res

#solve
def solve():
    n, q = LI()
    c = LI()
    lr = LIR(q)
    ans = [None] * q
    lr.sort(key=lambda x: x[1])
    dp = [-1] * (max(c) + 1)
    bit = [0] * (n + 1)
    def add(i, w):
        """
        i番目にwを加える
        :param int i:
        :param int w:
        :return:
        """
        x = i + 1
        while x <= n:
            bit[x - 1] += w
            x += x & -x
        return
    def sum(i):
        """
        [0,i]の合計
        :param int i:
        :return:
        """
        res = 0
        x = i + 1
        while x > 0:
            res += bit[x - 1]
            x -= x & -x
        return res
    t = 0
    def f(t):
        l, r, j = lr[t]
        xr = sum(r)
        xl = sum(l-1)
        tmp = xr - xl
        ans[j] = tmp
        pre = r
    pre = lr[0][1]
    for i in range(n):
        ci = c[i]
        l = dp[ci]
        add(i, 1)
        dp[ci] = i
        if l != -1:
            add(l, -1)
        while t < q and pre <= i:
            f(t)
            t += 1
        if t == q:
            break
    for ai in ans:
        print(ai) 
    return


#main
if __name__ == '__main__':
    solve()


### FIXED CODE ###

#!/usr/bin/env python3
from collections import defaultdict
import sys
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
def LI(): return list(map(int, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def LIR(n):
    res = [None] * n
    for i in range(n):
        l, r = map(int, input().split())
        res[i] = (l-1, r-1, i)
    return res

#solve
def solve():
    n, q = LI()
    c = LI()
    lr = LIR(q)
    ans = [None] * q
    lr.sort(key=lambda x: x[1])
    dp = [-1] * (max(c) + 1)
    bit = [0] * (n + 1)
    def add(i, w):
        """
        i番目にwを加える
        :param int i:
        :param int w:
        :return:
        """
        x = i + 1
        while x <= n:
            bit[x - 1] += w
            x += x & -x
        return
    def sum(i):
        """
        [0,i]の合計
        :param int i:
        :return:
        """
        res = 0
        x = i + 1
        while x > 0:
            res += bit[x - 1]
            x -= x & -x
        return res
    t = 0
    def f(t):
        l, r, j = lr[t]
        xr = sum(r)
        xl = sum(l-1)
        tmp = xr - xl
        ans[j] = tmp
        
    for i in range(n):
        ci = c[i]
        l = dp[ci]
        add(i, 1)
        dp[ci] = i
        if l != -1:
            add(l, -1)
        while t < q and lr[t][1]<= i:
            f(t)
            t += 1
        if t == q:
            break
    for ai in ans:
        print(ai) 
    return


#main
if __name__ == '__main__':
    solve()
N = int(input())

S = str()
count = 1
memo = 0
while a:
    amari = N%(2 ** count)
#    print ('amari', amari)
    if (amari- memo) == 2 ** (count-1):
        s = 1
    else:
        s = 0
    memo = memo + s * (-2) **(count-1)
#    print ('momo', memo)
    S = str(s) + S
    count += 1
    if memo == N:
        print (S)
        a = not a


### FIXED CODE ###

N = int(input())

S = str()
a = True
count = 1
memo = 0
while a:
    amari = N%(2 ** count)
#    print ('amari', amari)
    if (amari- memo) == 2 ** (count-1):
        s = 1
    else:
        s = 0
    memo = memo + s * (-2) **(count-1)
#    print ('momo', memo)
    S = str(s) + S
    count += 1
    if memo == N:
        print (S)
        a = not a
N,M=map(int,input().split())
H=list(map(int,input().split()))
P=[]
for i in range(M):
    P.append(list(map(int,input().split()))) #2次元配列、P[A_i,B_i]

ans=[]

for i in range(M):
    if H[P[i][0]-1]>H[P[i][1]-1]:   #H[A_i]>H[B_i]ならばA_iを加える
        ans.append([P[i][0])
    elif H[P[i][0]-1]<H[P[i][1]-1]: #H[A_i]<H[B_i]ならばB_iを加える
        ans.append(P[i][1])       
    else:                           #H[A_i]=H[B_i]ならば何もしない
        continue                    
    
list=[]

for j in range(M): 
    list+=P[j]

print(len(set(ans))+N-len(set(list)))

### FIXED CODE ###

n, m = map(int, input().split())
h = list(map(int, input().split()))
l = []
for _ in range(m):
  l.append(list(map(int, input().split())))

bad = []
for i in range(m):
  if h[l[i][0] - 1] > h[l[i][1] - 1]:
    bad.append(l[i][1])
  elif h[l[i][0] - 1] < h[l[i][1] - 1]:
    bad.append(l[i][0])
  else:
    bad.append(l[i][0])
    bad.append(l[i][1])

print(n - len(set(bad)))
6 15
6 5
5 6
6 4
6 6
3 5
7 2


### FIXED CODE ###

N, W = map(int, input().split())
import numpy as np
dp = np.zeros(W+1, dtype=int)
for i in range(N):
    w, v = map(int, input().split())
    np.maximum(dp[:-w] + v, dp[w:], out=dp[w:])
print(dp.max())
X = int(input())
if X=3 or X=5 or X=7:
  print("YES")
else:
  print("NO")

### FIXED CODE ###

x = int(input())
if x==3 or x==5 or x==7:
  print("YES")
else:
  print("NO")
n = int(input())
s,t = map(input().split())
for i in range(n):
  print(s[i]+t[i],end='')

### FIXED CODE ###

n = int(input())
s,t = input().split()
for i in range(n):
  print(s[i]+t[i],end='')
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, b % a)

import sys
input = sys.stdin.readline
N = int(input())
T = [int(input()) for _ in range(N)]
ans = T[0] * T[1] // gcd(T[0], T[1])
for i in range(2, N):
    ans = ans * T[i] // gcd(ans, T[i])
print(ans)

### FIXED CODE ###

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

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

import sys
input = sys.stdin.readline
N = int(input())
if N == 1:
    print(input())
else:
    T = [int(input()) for _ in range(N)]
    ans = lcm(T[0], T[1])
    for i in range(2, N):
        ans = lcm(ans, T[i])
    print(ans)
import math
a,b = map(int,input().split())
x = math.gcd(a,b)
c= x
ans = 1
for i in range(2,min(int(math.sqrt(x))+1,x)):
    if(c%i==0):
        ans+=1
    while(c%i==0):
        c=c//i
if(c>1):
    ans+=1
print(ans)

### FIXED CODE ###

def gcd(a,b):
    if(b==0):
        return a
    return gcd(b,a%b)
import math
a,b = map(int,input().split())
x = gcd(a,b)
c= x
ans = 1
for i in range(2,int(math.sqrt(x))+1):
    if(c%i==0):
        ans+=1
    while(c%i==0):
        c=c//i
        
if(c>1):
    ans+=1
print(ans)
from sys import stdin
a = [2,1]
for i in xrange(80):
 a.append(a[-1] + a[-2])
print a[int(stdin.readline())]

### FIXED CODE ###

from sys import stdin
a = [2,1]
for i in xrange(100):
 a.append(a[-1] + a[-2])
print a[int(stdin.readline())]
from collections import deque
dy = [-1, 0, 0, 1]
dx = [0, -1, 1, 0]
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()



### FIXED CODE ###

from collections import deque
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}}
goal = 123456780
def g(i, j, a):
    t = a // (10 ** j) % 10
    return a - t * (10 ** j) + t * (10 ** i)
def solve():
    MAP = "".join(input().replace(" ", "") for _ in range(N))
    zero = 8 - MAP.find("0")
    start = int(MAP)
    if start == goal:
        return 0
    dp = deque([(0, start, zero, 1), (0, goal, 0, 0)])
    TABLE = {start: (1, 0), goal: (0, 0)}
    while dp:
        cnt, M, yx, flg = dp.popleft()
        cnt += 1
        for nyx in m[yx]:
            key = g(yx, nyx, M)
            if key in TABLE:
                if TABLE[key][0] != flg:
                    return TABLE[key][1] + cnt
                continue
            TABLE[key] = (flg, cnt)
            dp.append((cnt, key, nyx, flg))
def MAIN():
    print(solve())
MAIN()