Harryxun/stf_run huggingface dataset:
import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions

import copy

# import heapq
# from collections import deque
# import decimal

sys.setrecursionlimit(10000001)
INF = sys.maxsize
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    def euclid(a, b):
        if b == 0:
            return a
        else:
            return euclid(b, a % b)

    def multiple(a, b):
        return a * b // euclid(a, b)

    n, m = ns()
    s = list(input())
    t = list(input())



    gcd =  multiple(n, m)

    s_idx = [gcd // n * i for i in range(n)]
    t_idx = [gcd // m * i for i in range(m)]

    ans = [-1] * (gcd + 1)
    for i, si in enumerate(s_idx):
        ans[si] = s[i]
    for i, ti in enumerate(t_idx):
        if ans[ti] != -1 and ans[ti] != t[i]:
            print(-1)
            exit(0)
    print(gcd)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions

import copy

# import heapq
# from collections import deque
# import decimal

sys.setrecursionlimit(10000001)
INF = sys.maxsize
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    def euclid(a, b):
        if b == 0:
            return a
        else:
            return euclid(b, a % b)

    def multiple(a, b):
        return a * b // euclid(a, b)

    n, m = ns()
    s = list(input())
    t = list(input())

    gcd = multiple(n, m)

    s_idx = [gcd // n * i for i in range(n)]
    t_idx = [gcd // m * i for i in range(m)]
    t_set = set(t_idx)

    for idx in s_idx:
        if idx in t_set:
            if s[idx * n // gcd] != t[idx * m // gcd]:
                print(-1)
                exit(0)

    print(gcd)


if __name__ == '__main__':
    main()
n = int(input())
a = list(map(int,input().split()))
ans_bigger = max(a)
ans_half = a / 2
dif = float("inf")
for i in range(n):
  x = abs(a[i]-ans_half)
  if dif > x:
    dif = x
    ans_smaller = a[i]
print(ans_bigger,ans_smaller)

### FIXED CODE ###

n = int(input())
a = sorted(list(map(int,input().split())))
ans_bigger = max(a)
ans_half = ans_bigger / 2
dif = float("inf")
for i in range(n-1):
  x = abs(a[i]-ans_half)
  if dif > x:
    dif = x
    ans_smaller = a[i]
print(ans_bigger,ans_smaller)
a,b = list(map(int, input().split()))
if (a == b) {
print(a, '==', b)
} elif (a > b) {
print(a, '>', b)
} else {
print(a, '<', b)
}

### FIXED CODE ###

a,b = list(map(int, input().split()))
if a == b:
  print('a == b')
elif a > b:
  print('a > b')
else:
  print('a < b')
a,b,c,d = [int(input()) for_ in range(4)]
print(min(a,b)+min(c,d))

### FIXED CODE ###

a,b,c,d=[int(input()) for _ in range(4)]
print(min(a,b)+min(c,d))
#55b
n=int(input())
p=1
for i in range(1,n+1):
    p = p*i
print(a%(10**9+7))

### FIXED CODE ###

#55b
n = int(input())
p=1

for i in range(1,n+1):
    p = i*p%(10**9+7)

print(p)
N = int(input())
M = int(input())

frag = True
for i in range(N):
    A[i] = -1
for i in range(M):
    si = int(input())
    ci = int(input())
    if A[si] != -1 and A[si] != ci:
        frag = False
        break
    else if si == 1 and ci == 0:
        frag = False
        break
    else:
        A[si] = ci

ans = 0
for i in range(N):
    if A[N-i-1] == -1:
        A[N-i-1] = 0
    ans += A[N-i-1]*(10**i)
    
if frag:
    print(ans)
else:
    print(-1)

### FIXED CODE ###

import numpy as np
N, M = map(int, input().split())

frag = True
A = np.zeros(N)
for i in range(N):
    A[i] = -1
for i in range(M):
    si,ci = map(int, input().split())
    if A[si-1] != -1 and A[si-1] != ci:
        frag = False
    elif si == 1 and ci == 0 and N != 1:
        frag = False
    else:
        A[si-1] = ci

ans = 0
for i in range(N):
    if A[N-i-1] == -1:
        A[N-i-1] = 0
    ans += A[N-i-1]*(10**i)
    
if ans == 0 and N == 1:
    pass
elif ans < 10**(N-1):
    ans += 10**(N-1)
    
if frag:
    print(int(ans))
else:
    print(-1)
n,q = map(int,input().split())
g = [[] for _ in range(n+1)]
d = [0]*(n+1)
for _ in range(n-1):
    a,b = map(int,input().split())
    g[a].append(b)
for _ in range(q):
    p,x = map(int,input().split())
    d[p] += x
ans = [0]*(n+1)
seen = [False]*(n+1)
def helper(s,cost):
    if not seen[s]:
        seen[s] = True
        ans[s] += cost
        for e in g[s]:
            if not seen[e]:
                helper(e,cost+d[e])
helper(1,d[1])
res = []
for a in ans[1:]:
    res.append(str(a))

print(' '.join(res))

### FIXED CODE ###

n,q = map(int,input().split())
g = [[] for _ in range(n+1)]
d = [0]*(n+1)
for _ in range(n-1):
    a,b = map(int,input().split())
    g[a].append(b)
    g[b].append(a)
for _ in range(q):
    p,x = map(int,input().split())
    d[p] += x
ans = [0]*(n+1)
seen = [False]*(n+1)
from collections import deque
q = deque([(1,d[1])])
while q:
    s,cost = q.popleft()
    seen[s] = True
    ans[s] += cost
    for e in g[s]:
        if not seen[e]:
            q.append((e,cost+d[e]))
# def helper(s,cost):
#     seen[s] = True
#     ans[s] += cost
#     for e in g[s]:
#         if not seen[e]:
#             helper(e,cost+d[e])
# for i in range(1,n+1):
#     if not seen[i]:
#         helper(i,d[i])
res = []
for a in ans[1:]:
    res.append(str(a))

print(' '.join(res))
lst = [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(lst[int(input()-1)])

### FIXED CODE ###

lst = [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(lst[int(input())-1])
import collections

N = int(input())

S = [input() for i in range(N)]

result = collections.Counter(S)

result_max = sorted([i for i in result.keys() if result[i] == max(result.values())])

for r in result_max:
    print(r)

### FIXED CODE ###

ABC = [int(i) for i in input().split()]

if len(set(ABC)) == 2:
    print("Yes")
else:
    print("No")
N = int(input())
A = list(int(i) for i in input().split())
count_m = 0
count_z = 0

for i in A:
  if i < 0:
    count_m += 1
  elif i == 0:
    count_z += 1

A_abs = [abs(i) for i in A]
if count_m%2 == 0 or (count_m+count_z)%2 == 0:
  print(sum(A_abs))
  
else:
  A_min = A.index(min(A_abs))
  A_abs[A_min] = A_min[A_min]*(-1)
  print(sum(A_abs))

### FIXED CODE ###

N = int(input())
A = list(int(i) for i in input().split())
count_m = 0
count_z = 0

for i in A:
  if i < 0:
    count_m += 1
  elif i == 0:
    count_z += 1

A_abs = [abs(i) for i in A]
if count_m%2 == 0 or (count_m+count_z)%2 == 0:
  print(sum(A_abs))
  
else:
  A_min = A_abs.index(min(A_abs))
  A_abs[A_min] = A_abs[A_min]*(-1)
  print(sum(A_abs))
a = int(input())
b = int(input())
c = int(input())

if a == b and a == c:
    print(1)
elif a == b or a == c or b == c:
    print(2)
else:
    print(3)


### FIXED CODE ###

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

if a == b and a == c:
    print(1)
elif a == b or a == c or b == c:
    print(2)
else:
    print(3)
n,k=map(int,input().split( ))

m=(n-2)*(n-1)//2

if m<k:
    print(-1)
else:
    l=m-k
    line=[]
    for i in range(n-1):
        line.append((1,i+2))
    
    counter=0
    for j in range(2,n):
        for i in range(n-j):
            line.append((j,i+j))
            counter+=1
            if counter==l:
                break
        if counter==l:
            break

print(len(line))
for i in range(len(line)):
    print(str(line[i][0])+' '+str(line[i][1]))


### FIXED CODE ###

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

m=(n-2)*(n-1)//2

if m<k:
    print(-1)
else:
    l=m-k
    line=[]
    for i in range(n-1):
        line.append((1,i+2))
    
    counter=0
    for j in range(2,n):
        if counter==l:
            break
        for i in range(j+1,n+1):
            line.append((j,i))
            counter+=1
            if counter==l:
                break
        if counter==l:
            break
    print(len(line))
    for i in range(len(line)):
        print(str(line[i][0])+' '+str(line[i][1]))
a,b=map(int, input().split())


if (a + b) % 2 === 0:
  print((a + b) // 2)
else:
  print("IMPOSSIBLE")

### FIXED CODE ###

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

if (a + b) % 2 == 0:
    print((a + b) // 2)
else:
    print("IMPOSSIBLE")
# -*- coding: utf-8 -*-
def Palindrome(S):
    if len(S)==1:
        return "Yes"
    for i in range(int((len(S)-1)/2)):
        if S[i]==S[len(S)-i-1]:
            YorN="Yes"
        else:
            YorN="No"
            break
    return YorN
S = input()
Sl = list(S)
left = right = "No"
if Palindrome(Sl) == "Yes":
    middle=int((len(Sl)-1)/2)
    print(Sl[:middle],Sl[middle+1:])
    left  = Palindrome(Sl[:middle])
    right = Palindrome(Sl[middle+1:])
if left == "Yes" and right == "Yes":
    YorN = "Yes"
else:
    YorN = "No"
print(YorN)


### FIXED CODE ###

# -*- coding: utf-8 -*-
def Palindrome(S):
    if len(S)==1:
        return "Yes"
    for i in range(int((len(S))/2)):
        if S[i]==S[len(S)-i-1]:
            YorN="Yes"
        else:
            YorN="No"
            break
    return YorN
S = input()
Sl = list(S)
left = right = "No"
if Palindrome(Sl) == "Yes":
    middle=int((len(Sl)-1)/2)
#    print(Sl[:middle],Sl[middle+1:])
    left  = Palindrome(Sl[:middle])
    right = Palindrome(Sl[middle+1:])
if left == "Yes" and right == "Yes":
    YorN = "Yes"
else:
    YorN = "No"
print(YorN)
H, W, K = map(int, input().split())

cake = [list(input()) for _ range(H)]

print("1 3 4")
print("1 3 4")
print("2 3 5")

### FIXED CODE ###

H, W, K = map(int, input().split())

cake = [list(input()) for _ in range(H)]
ans = [[0] * W for _ in range(H)]

id = 1
sign = 0
nothing = 0

for i in range(H):
    if cake[i].count('#') == 0:
        nothing += 1
        if i == H-1:
            for j in range(W):
                for d in range(nothing):
                    ans[i-d][j] = ans[i-nothing][j]
        continue
    for j in range(W):
        if cake[i][j] == '#':
            ans[i][sign:j+1] = [id] * (j+1-sign)
            sign = j+1
            id += 1
        elif j == W-1:
            ans[i][sign:j+1] = [id-1] * (j+1-sign)
    if nothing != 0:
        for j in range(W):
            for d in range(1,nothing+1):
                ans[i-d][j] = ans[i][j]
    sign = 0
    nothing = 0

for i in range(H):
    for j in range(W):
        print('{} '.format(ans[i][j]), end='')
    print()
import math
sum_gcd = 0
K = int(input())

for a in range(1,K+1):
  for b in range(1,K+1):
    for c in range(1,K+1):
      gcd = math.gcd(a, b, c) 
      sum_gcd += gcd

print(sum_gcd)

### FIXED CODE ###

from math import gcd
K = int(input())
sum_gcd = [0]*201
ans = 0
 
for i in range(1,K+1):
  for j in range(1,K+1):
    sum_gcd[gcd(i,j)] += 1
for i in range(1,K+1):
  for k in range(1,K+1):
    ans += sum_gcd[i]*gcd(i,k)

print(ans)
import numpy as np

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

X = np.zeros(10**9, dtype = int)
flg = 'YES'
for a in A:
    if X[a]==1:
        flg = 'NO'
        break
    else:
        X[a] += 1
print(flg)

### FIXED CODE ###

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

X = set(A)
if len(A) == len(X):
    print('YES')
else:
    print('NO')
d={}
s=0
for _ in range(int(input())):
  l=input()
  l=sorted(l)
  f=d.keys()
  if l not in f:
    d[l]=0
  else:
    d[j]+=1
    s+=d[j]
print(s)
    
    
  

### FIXED CODE ###

d={}
s=0
for _ in range(int(input())):
  l=input()
  l=str(sorted(l))
  f=d.keys()
  if l not in f:
    d[l]=0
  else:
    d[l]+=1
    s+=d[l]
print(s)
a = input()

if a < 1000 :
    print("ABC")
else :
    print("ABD")

### FIXED CODE ###

a = int(input())

if a < 1000 :
    print("ABC")
else :
    print("ABD")
s=input()
if s[3]==s[4] and s[5]==s[6]:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

s=input()
if s[2]==s[3] and s[4]==s[5]:
  print("Yes")
else:
  print("No")
print((input()+input())*input()//2)

### FIXED CODE ###

print((int(input())+int(input()))*int(input())//2)
n = input()
a = input().split("")
b = list(set([x for x in a if a.count(x) > 2]))

for i in b:
  print(i)
  

### FIXED CODE ###

from collections import defaultdict
from collections import OrderedDict
N = int(input())
ans = dict()
for _ in range(N):
    k = str(input())
    if k in ans:
        ans[k]+=1
    else:
        ans.update({k:1})
groupedByValue = defaultdict(list)
for key, value in sorted(ans.items()):
    groupedByValue[value].append(key)
l = groupedByValue[max(groupedByValue)]
for i in l:
    print(i)
#!/usr/bin/env python3

import re

if int(input()) > 100 and int(input()) <= 999:
    x = str(input())
else:
    print("No")
    exit

if re.match("7", x):
    print("Yes")
else:
    print("No")

### FIXED CODE ###

#!/usr/bin/env python3

if "7" in str(input()):
    print("Yes")
else:
    print("No")
n,m = map(int,input().split())
py = []
li = [1] * 10**5

for i in range(m):
    p,y = map(int,input().split())
    py.append((p,y,i))

py.sort(key = lambda x: x[1])

ans = []

for p,y,i in py:
    ans_tmp = '0' * (6 - len(str(p))) + str(p) + '0' * (6 - len(str(li[p]))) + str(li[p])
    li[p] += 1
    ans.append([ans_tmp, i])

ans.sort(key = lambda x: x[1])
for i in range(m):
    print(ans[i][0])


### FIXED CODE ###

n,m = map(int,input().split())
py = []
li = [1] * (10**5 + 10)

for i in range(m):
    p,y = map(int,input().split())
    py.append((p,y,i))

py.sort(key = lambda x: x[1])

ans = []

for p,y,i in py:
    ans_tmp = '0' * (6 - len(str(p))) + str(p) + '0' * (6 - len(str(li[p]))) + str(li[p])
    li[p] += 1
    ans.append([ans_tmp, i])

ans.sort(key = lambda x: x[1])
for i in range(m):
    print(ans[i][0])
N, K = map(int, input().split())
arr = list(map(int, input().split()))

if 0 in arr:
    K -= 1

if K==0:
    print(0)
    exit()

left =[]
right= []
for i in arr:
    if i<0:
        left.append(i*(-1))
    if i>0:
        right.append(i)

left = left[::-1]
if len(left)==0:
    print(right[K-1])
    exit()

if len(right)==0:
    print(left[K-1])
    exit()


if len(left)>=K and len(right)>=K:
    print(min(abs(left[K-1]),abs(right[K-1])))
    exit()

if len(left)<K and len(right)>=K:
    ans =[]
    ans.append(right[K-1])
    for i in range(K-2):
        ans.append(2*right[i]+left[K-i-2])
    for i in range(len(left)):
        ans.append(2*left[i]+right[K-i-2])
    print(min(ans))
    exit()

if len(right)<K and len(left)>=K:
    ans =[]
    ans.append(left[K-1])
    for i in range(K-2):
        ans.append(2*left[i]+right[K-i-2])
    for i in range(len(right)):
        ans.append(2*right[i]+left[K-i-2])
    print(min(ans))
    exit()

if len(right)<K and len(left)<K:
    ans =[]
    for i in range(len(left)):
        ans.append(2*left[i]+right[K-i-2])
    for i in range(len(right)):
        ans.append(2*right[i]+left[K-i-2])
    print(min(ans))
    exit()





### FIXED CODE ###

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

ans =[]
if arr[0]>0:
    ans.append(arr[K-1])

if arr[-1]<0:
    ans.append(abs(arr[-1*(K)]))

for i in range(N-K+1):
    if arr[i]*arr[i+K-1]<=0:
        left =2*abs(arr[i])+abs(arr[i+K-1])
        right=2*abs(arr[i+K-1])+abs(arr[i])
        ans.append(min(left,right))

print(min(ans))
n,m,q=map(int,input().split())
ans=[[0]*(n+1) for __ in range(n+1)]
for _ in range(m):
  l,r=map(int,input().split())
  ans[l][r]+=1
for i in range(n+1):
  for j in range(n):
    ans[i][j+1]+=ans[i][j]
for i in range(n):
  for j in range(n+1):
    ans[i+1][j]+=ans[i][j]
for qq in q:
  p,q=map(int,input().split())
  print(ans[q][q]-ans[p-1][q]-ans[p][q-1]+ans[p][p])

### FIXED CODE ###

n,m,qu=map(int,input().split())
ans=[[0]*(n+1) for __ in range(n+1)]
for _ in range(m):
  l,r=map(int,input().split())
  ans[l][r]+=1
for i in range(n+1):
  for j in range(n):
    ans[i][j+1]+=ans[i][j]
for i in range(n):
  for j in range(n+1):
    ans[i+1][j]+=ans[i][j]
for qq in range(qu):
  p,q=map(int,input().split())
  print(ans[q][q]-ans[p-1][q]-ans[q][p-1]+ans[p-1][p-1])
import sys

#readline = sys.stdin.readline
_input = open('input')
readline = _input.readline

H, W = map(int, readline().split())
S = [readline().rstrip() for i in range(H)]

vert = [[0]*W for i in range(W)]
hori = [[0]*W for i in range(W)]

for y in range(H):
    for x in range(W):

        if x > 0 and S[y][x - 1] != '#':
            hori[y][x] = hori[y][x - 1]
        elif S[y][x] == '#':
            hori[y][x] = 0
        else:
            # hori
            count = 1
            while x + count < W and S[y][x + count] == '.':
                count += 1
            hori[y][x] = count

        if y > 0 and S[y - 1][x] != '#':
            vert[y][x] = vert[y - 1][x]
        elif S[y][x] == '#':
            vert[y][x] = 0
        else:
            # hori
            count = 1
            while y + count < H and S[y + count][x] == '.':
                count += 1
            vert[y][x] = count

ans = 0
for y in range(H):
    for x in range(W):
        a = hori[y][x] + vert[y][x] - 1
        ans = max(a, ans)
        sys.stdout.write('{},{}\t'.format(hori[y][x], vert[y][x]))
    print('')

print(ans)

### FIXED CODE ###

import sys

readline = sys.stdin.readline

H, W = map(int, readline().split())
S = [readline().rstrip() for i in range(H)]

vert = [[0]*W for i in range(H)]
hori = [[0]*W for i in range(H)]

for y in range(H):
    for x in range(W):

        if x > 0 and S[y][x - 1] != '#':
            hori[y][x] = hori[y][x - 1]
        elif S[y][x] == '#':
            hori[y][x] = 0
        else:
            # hori
            count = 1
            while x + count < W and S[y][x + count] == '.':
                count += 1
            hori[y][x] = count

        if y > 0 and S[y - 1][x] != '#':
            vert[y][x] = vert[y - 1][x]
        elif S[y][x] == '#':
            vert[y][x] = 0
        else:
            # hori
            count = 1
            while y + count < H and S[y + count][x] == '.':
                count += 1
            vert[y][x] = count

ans = 0
for y in range(H):
    for x in range(W):
        a = hori[y][x] + vert[y][x] - 1
        ans = max(a, ans)

print(ans)
def main():
    N, A, B = [int(x) for x in input().split()]
    a = 0
	for n in range(N+1):
      s = sum(int(x) for x in n)
      if A <= s <= B:
        a += n
    return a
main()
        
  



### FIXED CODE ###





def main():
    N, A, B = [int(x) for x in input().split()]
    a = 0
    for n in range(N+1):
        s = sum(int(x) for x in str(n))
        if A <= s <= B:
          	a += n
    return a
print(main())
def abc():
    a, b, c = map(int, input().split())
    n = list(range(a, b + 1))
    s = sorted(set(n[:c]) | set(n[-c:]))
    for _s in s:
        print(_s)


abc()

### FIXED CODE ###

def abc():
    a, b, c = map(int, input().split())
    n = range(a, b + 1)
    for s in sorted(set(n[:c]) | set(n[-c:])):
        print(s)


abc()
n=int(input())
result=0
a
for i in range(n): 
    if i % 3 == 0 and i % 5 == 0:
        a=result    
    elif i % 3 == 0:
        a=result
    elif i % 5 == 0:
        a=result
    else:
        result=result+i
    
print(result)
        

### FIXED CODE ###

n=int(input())
result=0
for i in range(n+1): 
    if i % 3 == 0 and i % 5 == 0:
        result=result    
    elif i % 3 == 0:
        result=result
    elif i % 5 == 0:
        result=result
    else:
        result=result+i
    
print(result)
import itertools
import math
from collections import deque
from collections import defaultdict
from itertools import permutations
import heapq
import bisect
from scipy.sparse.csgraph import floyd_warshall as wf
from collections import Counter
from itertools import*
from bisect import bisect_left,bisect_right
inf = 10**10
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
def lcm(a,b):
  return a*b //gcd(a,b)
n,m = map(int,input().split())
s = input()
t = input()
d = gcd(n,m)
l = lcm(n,m)
a = n//d 
b = m//d 
for i in range(d):
    if s[a*i]!= t[b*i]:
        print(-1)
        break
    else:
        print(l)

### FIXED CODE ###

N,M = map(int,input().split())
S = input()
T = input()
#良い文字列は存在するならば長さはN,Mの最小公倍数になる
#異なる文字が同じ場所に来たらダメ
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
def lcm(a,b):
  return a*b //gcd(a,b)
L = lcm(N,M)
n = N//gcd(N,M)
m = M//gcd(N,M)
for k in range(gcd(N,M)):
    if S[k*n] != T[k*m]:
        print(-1)
        exit()
print(L)
while True:
    n=int(input())
    if n==0:break
    b=[[int(p)for p in input().split(" ")],[int(p)for p in input().split(" ")]]
    mem=[[1145141919 for i in range(n)]for j in range(2)]
    mem[1][0]=True
    que=[[0,0,0],[1,0,0]]
    count=1145141919
    while len(que)!=0:
        d=que.pop(0)
        state=b[d[0]][d[1]]
        if state!=2 and d[1]==n-1 and d[2]<count:
            count=d[2]
        mem[d[0]][d[1]]=d[2]
        case=-1
        if state==0:case=0
        elif state==1:
            if b[d[0]][d[1]+1]==1:case=1
            else:case=0
        elif state==2:case=2

        if case==0:
            for i in range(3):
                if d[1]+i>=n:break
                if d[0]==0 and mem[1][d[1]+i]>d[2]+1:que.append([1,d[1]+i,d[2]+1])
                elif d[0]==1 and mem[0][d[1]+i]>d[2]+1:que.append([0,d[1]+i,d[2]+1])
        elif case==1:
            if mem[d[0]][d[1]+1]>d[2]:que.append([d[0],d[1]+1,d[2]])
        elif case==2:
            if mem[d[0]][d[1]-1]>d[2]:que.append([d[0],d[1]-1,d[2]])
    print(str(count)if count!=1145141919 else "NA")

### FIXED CODE ###

def bfs(b):
    mem=[[False for i in range(n)]for j in range(2)]
    st=[0,0]
    for i in range(2):
        if b[i][0]!=1:continue
        while st[i]<n-1 and b[i][st[i]+1]==1:
            st[i]+=1
        if st[i]==n-1:return 0
    mem[0][st[0]]=True
    mem[1][st[1]]=True
    que=[[0,st[0],0],[1,st[1],0]]
    while len(que)!=0:
        d=que.pop(0)
        des=(d[0]+1)%2
        cst=d[2]+1
        for i in range(3):
            fl=d[1]+i
            if fl>=n:break
            state=b[des][fl]
            if state!=2 and fl==n-1:
                return cst
            if state==0:
                if mem[des][fl]==False:
                    que.append([des,fl,cst])
                    mem[des][fl]=True
            elif state==1:
                k=1
                while True:
                    if fl+k>=n:return cst
                    if b[des][fl+k]!=1:
                        if mem[des][fl+k-1]==False:
                            que.append([des,fl+k-1,cst])
                            mem[des][fl+k-1]=True
                        break
                    else: k+=1

            elif state==2:
                k=1
                while True:
                    if b[des][fl-k]!=2:
                        if mem[des][fl-k]==False:
                            que.append([des,fl-k,cst])
                            mem[des][fl-k]=True
                        break
                    else:k+=1  
    return -1
while True:
    n=int(input())
    if n==0:break
    b=[[int(p)for p in input().split(" ")],[int(p)for p in input().split(" ")]]
    count=bfs(b)
    print(str(count)if count>=0 else "NA")
# -*- coding: utf-8 -*-
import math
n, k = map(int, input().split())

prop = 0.0
_prop = 0.0

if n >= k:
    _prop = (n - k) / n

end = min(n, k) + 1
for i in range(1, end):
    dest = k / i
    coin = math.ceil(math.log2(dest))
    __prop = (1 / n) * (1 / pow(2, coin))
    prop += __prop

print(prop + _prop)


### FIXED CODE ###

# -*- coding: utf-8 -*-
import math
n, k = map(int, input().split())

prop = 0.0
_prop = 0.0

if n >= k:
    _prop = (n - k) / n

end = min(n, k) + 1
for i in range(1, end):
    dest = k / i
    coin = math.ceil(math.log2(dest))
    __prop = (1 / n) * (1 / pow(2, coin))
    prop += __prop

print(prop + _prop)
N = int(input())
L = [ 0 ] * 86

L[0] = 2
L[1] = 1

for i in range(2, N):
    L[i] = L[i-2] + L[i-1]

print (L[N])
    


### FIXED CODE ###

N = int(input())
L = [ 0 ] * 1000000

L[0] = 2
L[1] = 1

for i in range(2, N+1):
  L[i] = L[i-2] + L[i-1]

print (L[N])
# -*- coding-UTF-8 -*-
A, B, K = map(int, input().split())

i = 0
while True:
    i += 1
    if A%2:
         A -= 1
    A /= 2
    B += A
    if i == K:
        break
    i += 1
    if B%2:
        B -= 1
    B /= 2
    A += B
    if i == K:
        break
print(A,B)

### FIXED CODE ###

S = input()
if len(S) == 3:
    S = S[::-1]
print(S)