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

S=input()
lens=len(S)

mod=10**9+7


Asum=[0]*lens
#Bsum=[0]*lens
Csum=[0]*lens
qsum=[0]*lens

for i in range(lens):
    if S[i]=="A":
        Asum[i]=Asum[i-1]+1
        Csum[i]=Csum[i-1]
        qsum[i]=qsum[i-1]
    elif S[i]=="C":
        Asum[i]=Asum[i-1]
        Csum[i]=Csum[i-1]+1
        qsum[i]=qsum[i-1]
    elif S[i]=="?":
        Asum[i]=Asum[i-1]
        Csum[i]=Csum[i-1]
        qsum[i]=qsum[i-1]+1
    else:
        Asum[i]=Asum[i-1]
        Csum[i]=Csum[i-1]
        qsum[i]=qsum[i-1]        

CSUM=Csum[lens-1]
QSUM=qsum[lens-1]


count=0
for i in range(1,lens-1):
    if S[i]=="B":
        count+=Asum[i-1]*(CSUM-Csum[i])*(3**max(0,QSUM))%mod
        count+=Asum[i-1]*(QSUM-qsum[i])*(3**max(0,(QSUM-1)))%mod
        count+=qsum[i-1]*(CSUM-Csum[i])*(3**max(0,(QSUM-1)))%mod
        count+=qsum[i-1]*(QSUM-qsum[i])*(3**max(0,(QSUM-2)))%mod


    elif S[i]=="?":
        count+=Asum[i-1]*(CSUM-Csum[i])*(3**max(0,(QSUM-1)))%mod
        count+=Asum[i-1]*(QSUM-qsum[i])*(3**max(0,(QSUM-2)))%mod
        count+=qsum[i-1]*(CSUM-Csum[i])*(3**max(0,(QSUM-2)))%mod
        count+=qsum[i-1]*(QSUM-qsum[i])*(3**max(0,(QSUM-3)))%mod

print(count%mod)


            


### FIXED CODE ###

S=input()
lens=len(S)

mod=10**9+7


Asum=[0]*lens
#Bsum=[0]*lens
Csum=[0]*lens
qsum=[0]*lens

for i in range(lens):
    if S[i]=="A":
        Asum[i]=Asum[i-1]+1
        Csum[i]=Csum[i-1]
        qsum[i]=qsum[i-1]
    elif S[i]=="C":
        Asum[i]=Asum[i-1]
        Csum[i]=Csum[i-1]+1
        qsum[i]=qsum[i-1]
    elif S[i]=="?":
        Asum[i]=Asum[i-1]
        Csum[i]=Csum[i-1]
        qsum[i]=qsum[i-1]+1
    else:
        Asum[i]=Asum[i-1]
        Csum[i]=Csum[i-1]
        qsum[i]=qsum[i-1]        

CSUM=Csum[lens-1]
QSUM=qsum[lens-1]


count=0
for i in range(1,lens-1):
    if S[i]=="B":
        count+=Asum[i-1]*(CSUM-Csum[i])*pow(3,max(0,QSUM),mod)%mod
        count+=Asum[i-1]*(QSUM-qsum[i])*pow(3,max(0,QSUM-1),mod)%mod
        count+=qsum[i-1]*(CSUM-Csum[i])*pow(3,max(0,QSUM-1),mod)%mod
        count+=qsum[i-1]*(QSUM-qsum[i])*pow(3,max(0,QSUM-2),mod)%mod


    elif S[i]=="?":
        count+=Asum[i-1]*(CSUM-Csum[i])*pow(3,max(0,QSUM-1),mod)%mod
        count+=Asum[i-1]*(QSUM-qsum[i])*pow(3,max(0,QSUM-2),mod)%mod
        count+=qsum[i-1]*(CSUM-Csum[i])*pow(3,max(0,QSUM-2),mod)%mod
        count+=qsum[i-1]*(QSUM-qsum[i])*pow(3,max(0,QSUM-3),mod)%mod
        
    



#count=0
#for a in range(lens-2):
#    if S[a]=="A" or S[a]=="?":
#        for b in range(a+1,lens-1):
#            if S[b]=="B" or S[b]=="?":
#                for c in range(b+1,lens):
#                    if S[c]=="C" or S[c]=="?":
#                        count+=1
print(count%mod)
### BUGGY CODE ###

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


class UFT:
    def __init__(self, N):
        self.UFdata = [-1] * (N+1)
        self.rank   = [0]  * (N+1)
        self.connected_num = [1] * (N+1)

    def find(self,x):
        UFdata = self.UFdata
        while UFdata[x] != -1:
            x = UFdata[x]
        return x

    def unite(self,x,y):
        UFdata = self.UFdata
        rank = self.rank
        connected_num = self.connected_num
        find = self.find

        x = find(x)
        y = find(y)
        if x != y:
            if rank[x] < rank[y]:
                x,y = y,x
            if rank[x] == rank[y]:
                rank[x] += 1
            UFdata[y] = x       
            

UF1 = UFT(N)
UF2 = UFT(N)
ans = [1] * (N+1)
MAP= [ [0] * (N+1) for _ in range(N+1)]
import sys
input = sys.stdin.readline
PQ = [ [int(j) for j in input().split()] for _ in range(K)]
RS = [ [int(j) for j in input().split()] for _ in range(L)]

for i in range(K):
    p,q = PQ[i]
    UF1.unite(p,q)
for i in range(L):
    p,q = RS[i]
    UF2.unite(p, q)
counter=[]
for i in range(1,N+1):
  counter.append((UF1.find(i),UF2.find(i)))
from collections import Counter  
p=Counter(counter)

ans = [0]*(N+1)
for i in range(1,N+1):
    ans[i] = p[(UF1.find(i),UF2.find(i))]

del ans[0]
# print(" ".join( map(lambda x: str(x), connected_num[1:])))
print(" ".join( map(lambda x: str(x), ans)))


### FIXED CODE ###

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


class UFT:
    def __init__(self, N):
        self.UFdata = [-1] * (N+1)
        self.rank   = [0]  * (N+1)

    def find(self,x):
        UFdata = self.UFdata
        while UFdata[x] != -1:
            x = UFdata[x]
        return x

    def unite(self,x,y):
        UFdata = self.UFdata
        rank = self.rank 
        find = self.find

        x = find(x)
        y = find(y)
        if x != y:
            if rank[x] < rank[y]:
                x,y = y,x
            if rank[x] == rank[y]:
                rank[x] += 1
            UFdata[y] = x       
            

UF1 = UFT(N)
UF2 = UFT(N)
ans = [1] * (N+1)
# MAP= [ [0] * (N+1) for _ in range(N+1)]
import sys
input = sys.stdin.readline
#PQ = [ [int(j) for j in input().split()] for _ in range(K)]
#RS = [ [int(j) for j in input().split()] for _ in range(L)]

for i in range(K):
    p,q = map(int,input().split())
    UF1.unite(p,q)
for i in range(L):
    p,q = map(int,input().split())#RS[i]
    UF2.unite(p, q)
counter=[]
from collections import defaultdict
cntdic =defaultdict(int)
for i in range(1,N+1):
  counter.append(UF1.find(i)+UF2.find(i)*10**6)
  cntdic[counter[-1]]+=1 

ans = [0]*(N+1)
for i in range(1,N+1):
    ans[i] = cntdic[counter[i-1]]

del ans[0]
# print(" ".join( map(lambda x: str(x), connected_num[1:])))
print(" ".join( map(lambda x: str(x), ans)))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

    s_li = []

    for i in range(n):
        s_i = input()
        if s_i in s_li:
            continue
        else:
            s_li.append(s_i)

    print(len(s_li))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

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

    s_li = []

    for i in range(n):
        s_i = input()
        s_li.append(s_i)

    print(len(set(s_li)))


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

N,M=map(int,input().split())
graph=[[] for _ in range(N)]
for i in range(M):
  a,b=map(int,input().split())
  graph[a-1].append(b-1)
  graph[b-1].append(a-1)

s=[-1]*N
d=[-1]*N

s[0]=0
d[0]=0


for i in range(N):
  finish=1
  for j in range(N):
    if d[j]==i:
      for saki in graph[j]:
        if d[saki]==-1:
          d[saki]=i+1
          s[saki]=j
          finish=0
  if finish==1:
    break

print("Yes")
for i in range(N-1):
  print(s[i+1]+1)

### FIXED CODE ###

N,M=map(int,input().split())
graph=[[] for _ in range(N)]
for i in range(M):
  a,b=map(int,input().split())
  graph[a-1].append(b-1)
  graph[b-1].append(a-1)

s=[-1]*N
d=[-1]*N
next=[[] for _ in range(N)]
next[0].append(0)

s[0]=0
d[0]=0


for i in range(N):
  finish=1
  for j in next[i]:
    if d[j]==i:
      for saki in graph[j]:
        if d[saki]==-1:
          d[saki]=i+1
          s[saki]=j
          next[i+1].append(saki)
          finish=0
  if finish==1:
    break

print("Yes")
for i in range(N-1):
  print(s[i+1]+1)
### BUGGY CODE ###

s=input()
cnt=0
le=len(s)
for i in range(1,le-2):
    for j in range(i+3,le+1):
        number=s[i-1:j]
        if int(number)%2019==0:
            cnt+=1
print(cnt)

### FIXED CODE ###

s=input()[::-1]
mod=[0]*2019
mod[0]=1
x=1
num=0
ans=0

for t in s:
    num += int(t) * x
    num %= 2019
    x *= 10
    x %= 2019
    mod[num] +=1

for u in mod:
    ans += u*(u-1)//2

print(ans)
### BUGGY CODE ###

import copy
from collections import deque

def main():
    N = int(input())
    A = [deque(map(int, input().split())) for i in range(N)]
    
    ans = 0
    finish = False
    base_used = [True] + [False] * N
    count = 0
    
    while not finish and count != N:
      finish = True
      ans += 1
      used = copy.deepcopy(base_used)
      
      for idx, u in enumerate(used):
        if not u:
          a = A[idx-1][0]
          if not used[a] and A[a-1][0] == idx:
            used[idx] = True
            used[a] = True
            A[idx-1].popleft()
            A[a-1].popleft()
            finish = False
            
            if not A[idx-1]:
                base_used[idx] = True
                count += 1
                
            if not A[a-1]:
                base_used[a] = True
                count += 1
     
    if N != count:
      ans = -1
    print(ans)
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys

input = sys.stdin.readline

def main():
    N = int(input())
    
    Id = {}
    
    cur = 0
    for i in range(1, N+1):
        for j in range(i+1, N+1):
            Id[(i,j)] = cur
            cur += 1
            
    G = [[] for i in range(N*(N-1)//2)]
    size = [0] * (N*(N-1)//2)
    
    for i in range(1, N+1):
        for idx, j in enumerate(list(map(int, input().split()))):
            if i < j: k = Id[(i, j)]
            else: k = Id[(j, i)]
            if idx: 
                G[par].append(k)
                size[k] += 1
            par = k
            
    g = [idx for idx, s in enumerate(size) if s == 0]
    
    ans = 0
    while g:
        ans += 1
        n_g = []
        
        for v in g:
            length = len(G[v])
            if not length: continue
            
            size[G[v][0]] -= 1
            if not size[G[v][0]]: n_g.append(G[v][0])
    
            if length == 2:
                size[G[v][1]] -= 1
                if not size[G[v][1]]: n_g.append(G[v][1])
        g = n_g
        
    for s in size:
        if s != 0:
            print(-1)
            sys.exit()
    print(ans)
            
if __name__ == '__main__':
    main()
### BUGGY CODE ###

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

    dp = [-1] * (T + 3000)
    dp[0] = 0
    for a, b in sorted(AB):
        for i in range(T - 1, -1, -1):
            if dp[i] == -1:
                continue
            dp[i + a] = max(dp[i + a], dp[i] + b)
    print(max(dp))


main()


### FIXED CODE ###

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

    dp = [-1] * (T + 3000)
    dp[0] = 0
    for a, b in sorted(AB):
        for j in range(T - 1, -1, -1):
            if dp[j] == -1:
                continue
            if dp[j] + b > dp[j + a]:
                dp[j + a] = dp[j] + b
    print(max(dp))


main()
### BUGGY CODE ###

data = input().split()
monsters = int(data[0])
smash = int(data[1])

mon_str = input().split()
mon_str = [int(b) for b in mon_str]
count = 0

for i in range(smash):
    try:
        enemy = mon_str.index(max(mon_str))
        del mon_str[enemy]
    
    except ValueError:
        pass
print(sum(mon_str))

### FIXED CODE ###

import numpy as np

def do():
    data = np.array(input().split(" "), dtype="int64")
    life = np.array(input().split(" "), dtype="int64")
    monsters = data[0]
    smash = data[1]
    if smash == 0:
        print(np.sum(life))
    elif smash >= monsters:
        print(0)
    else:
        a = np.sort(life)[-smash]
        leftover = np.where(life < a, life, 0)
        print(np.sum(leftover))

do()
### BUGGY CODE ###

N, K = map(int, input().split())
A = sorted(list(map(int, input().split())))
MOD = 10 ** 9 + 7

ans = 0
start = 1
x = K - 1
for i in range(N - K + 1):
  if i > 0:
    start = start * (K - 1 + i) // i
  ans += (A[- N + K + i - 1] - A[N - K - i]) * (start % MOD)
  ans = ans % MOD
    
print(ans % MOD)

### FIXED CODE ###

N, K = map(int, input().split())
A = sorted(list(map(int, input().split())))
MOD = 10 ** 9 + 7

ans = 0

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

N2 = 10 ** 6  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
 
for i in range(2, N2 + 1):
    fact.append((fact[-1] * i) % MOD)
    inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
    factinv.append((factinv[-1] * inv[-1]) % MOD)

#print(cmb(n, r, p))
for i in range(len(A)):
  if N - 1 - i >= K - 1:
    ans += (A[- i - 1] - A[i]) * cmb(N - 1 - i, K - 1, MOD)
    ans = ans % MOD
    
    
print(ans % MOD)
### BUGGY CODE ###

N,Q = map(int,input().split())
S = input()
z = []
for j in range(N-1):
  if S[j] =='A' and S[j+1]=='C':
    z.append(j+1)
for i in range(Q):
  l,r = map(int,input().split())
  if r-l >= 1:
    if r-l == 1:
      if l in z:
        print('1')
      else:
        print('0')
    else:
      ans = [x for x in z if x >= l and x<= r-1]
      print(len(ans))
  else:
    print('0')


### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
t = [0] * (N + 1)
for i in range(N):
  t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
for i in range(Q):
  l, r = map(int, input().split())
  print(t[r-1] - t[l-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    h,w = map(int,input().split())
    q = []
    A = ["" for i in range(h)]
    for i in range(h):
        b = input()
        A[i] = b
    #    print(b)
        for j in range(w):
            if b[j]=="#": q.append([i,j,0])
    #print(A)
    while q:
        a,b,c = q.pop(0)
        for x,y in [(1,0),(0,1),(-1,0),(0,-1)]:
            if 0<=b+y<h and 0<=a+x<w and A[b+y][a+x] == ".":
                #print(b+y,a+x)
                q.append([b+y,a+x,c+1])
                l = list(A[b+y])
                l[a+x] = "#"
                A[b+y] = "".join(l)
        if not q:
            print(c)
            break
    #print(A)
if __name__ == '__main__':
    main()



### FIXED CODE ###

import numpy as np
def main():
    h,w = map(int, input().split())
    mat = []
    for i in range(h):
        b = input()
        mat.append([0 if j=="#" else h+w for j in b])
    arr = np.array(mat)

    for i in range(w-1):
        arr[:,i+1] = np.minimum(arr[:,i]+1,arr[:,i+1])
        #print(arr)

    for i in range(w-1,0,-1):
        arr[:,i-1] = np.minimum(arr[:,i]+1,arr[:,i-1])
        #print(arr)

    for i in range(h-1):
        arr[i+1,:] = np.minimum(arr[i,:]+1,arr[i+1,:])
        #print(arr)

    for i in range(h-1,0,-1):
        arr[i-1,:] = np.minimum(arr[i,:]+1, arr[i-1,:])
        #print(arr)
    print(np.max(arr))


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

def check():
    N, M = map(int, input().split())
    A = [int(i) for i in input().split()]
    sousa = sorted([[int(i) for i in input().split()] for i in range(M)],
                   reverse=True, key=lambda x:x[1])
    for cnt, value in sousa:
        for i in range(cnt):
            if min(A) < value:
                A[A.index(min(A))] = value
            else:
                return(sum(A))
    return(sum(A))
  
print(check())

### FIXED CODE ###

def check():
    N, M = map(int, input().split())
    A = sorted([int(i) for i in input().split()])
    sousa = sorted([[int(i) for i in input().split()] for i in range(M)],
                   reverse=True, key=lambda x:x[1])
    index = 0
    for cnt, value in sousa:
        for i in range(cnt):
            if index == N:
                break
            if A[index] < value:
                A[index] = value
            else:
                return(sum(A))
            index += 1
    return(sum(A))
print(check())
### BUGGY CODE ###

import fractions

N = int(input())

total = 0

for i in range(1, N + 1):
  total += i

for i in range(1, N + 1):
  for j in range(i + 1, N + 1):
    total += (fractions.gcd(i, j) * 6)

for i in range(1, N + 1):
  for j in range(i + 1, N + 1):
    for k in range(j + 1, N + 1):
      total += (fractions.gcd(fractions.gcd(i, j), k) * 6)

print(total)

### FIXED CODE ###

import fractions

N = int(input())

total = 0

for i in range(1, N + 1):
  total += i

for i in range(1, N + 1):
  for j in range(i + 1, N + 1):
    tmp = fractions.gcd(i, j)
    total += (tmp * 6)
    for k in range(j + 1, N + 1):
      total += (fractions.gcd(tmp, k) * 6)

print(total)
### BUGGY CODE ###

N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
MOD = 10 ** 9 + 7
dp = [0] * (N + 1)
dp[0] = 1
for i in range(1, N + 1):
    if i == 1:
        if not i - 1 in a:
            dp[i] = 1
    else:    
        if not i - 1 in a:
            dp[i] += dp[i - 1] % MOD
        if not i - 2 in a:
            dp[i] += dp[i - 2] % MOD
print(dp[-1] % MOD)

### FIXED CODE ###

N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
a.sort(reverse=True)
dp = [0] * (N + 1)
dp[0] = 1
if len(a) > 0:
    A = a.pop()
else:
    A = -1

if A == 1:
    dp[1] = 0
    if len(a) > 0:
        A = a.pop()
    if A == 2:
        dp[2] = 0
    else:
        dp[2] = 1
else:
    dp[1] = 1
for i in range(2, N + 1):
    if i == A:
        if len(a) > 0:
            A = a.pop()
        continue
    if dp[i - 1] != 0 and dp[i - 2] != 0:
        dp[i] = (dp[i - 1] + dp[i - 2])  % 1000000007
    elif dp[i - 1] != 0:
        dp[i] = dp[i - 1]  % 1000000007
    elif dp[i - 2] != 0:
        dp[i] = dp[i - 2]  % 1000000007
    else:
        dp[i] = 0
print(dp[-1])
### BUGGY CODE ###

def main():

    import sys
    sys.setrecursionlimit(10 ** 9)

    input = sys.stdin.readline

    N = int(input())

    G =[[] for _ in range(N + 1)] #iさんが勝った相手のリストを要素とするリスト
    for i in range(2, N + 1):
        a = int(input())
        G[a].append(i)

    # print (G)

    set_lst = [set() for _ in range(N + 1)] #使った数字を管理する
    tmp_lst = [0] * (N + 1) #次に使える最小を管理する

    # print (set_lst)
    # print (tmp_lst)

    def calc(x): #xからの移動先を検討
        tmp = 0 #何試合目に行うことができるか
        for next_ in G[x]:
            y = max(calc(next_), tmp_lst[x])
            while y in set_lst[x]: #既に使われていたとき、一つずつ更新する
                y += 1
            set_lst[x].add(y) #新しく使ったことを記録する
            if y == tmp_lst[x]:
                tmp_lst[x] = y + 1
            tmp = max(y, tmp)
        return tmp + 1

    ans = calc(1) - 1

    # print (set_lst)
    # print (tmp_lst)
    print (ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 9)

input = sys.stdin.readline

N = int(input())

G =[[] for _ in range(N + 1)] #iさんが勝った相手のリストを要素とするリスト
for i in range(2, N + 1):
    a = int(input())
    G[a].append(i)

# print (G)

def calc(x): #xからの移動先を検討
    tmp = 0
    lst = []
    for next_ in G[x]:
        y = calc(next_)
        lst.append(y)
    lst.sort()
    for i in lst:
        if tmp >= i:
            tmp += 1
        else: #tmp < i
            tmp = i
    return tmp + 1

ans = calc(1) - 1

print (ans)
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-


def main():
  height, width = map(int, input().split())
  max_value = height * width
  values = []
  queue = []

  for y in range(height):
    values.append([0 if v == '#' else max_value for v in input().strip()])
    queue.extend((x, y) for x, v in enumerate(values[-1]) if v == 0)

  while len(queue) > 0:
    x, y = queue.pop(0)
    v = values[y][x] + 1

    if x > 0 and values[y][x - 1] > v:
      values[y][x - 1] = v
      queue.append((x - 1, y))

    if x < width - 1 and values[y][x + 1] > v:
      values[y][x + 1] = v
      queue.append((x + 1, y))

    if y > 0 and values[y - 1][x ] > v:
      values[y - 1][x] = v
      queue.append((x, y - 1))

    if y < height - 1 and values[y + 1][x] > v:
      values[y + 1][x] = v
      queue.append((x, y + 1))

  print(max(max(v) for v in values), flush=True)


if __name__ == '__main__':
  main()



### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
import numpy


def main():
  height, width = map(int, input().split())
  max_value = height + width
  values = []

  for y in range(height):
    values.append([0 if v == '#' else max_value for v in input().strip()])

  values = numpy.array(values)

  for x in range(width - 1):
    values[:, x + 1] = numpy.minimum(values[:, x] + 1, values[:, x + 1])

  for x in range(width - 1, 0, -1):
    values[:, x - 1] = numpy.minimum(values[:, x] + 1, values[:, x - 1])

  for y in range(height - 1):
    values[y + 1, :] = numpy.minimum(values[y, :] + 1, values[y + 1, :])

  for y in range(height - 1, 0, -1):
    values[y - 1, :] = numpy.minimum(values[y, :] + 1, values[y - 1, :])

  print(numpy.max(values), flush=True)


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

import sys
sys.setrecursionlimit(10**9)

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

stack = [0]
def dfs(a, k):
    global stack
    if k == 0:
        return a
    if k == -1:
        return stack[-1]
    next_a = A[a]-1
    if next_a in stack:
        idx = stack.index(next_a)
        n = len(stack)
        k %= (n - idx)
        res = dfs(next_a, k - 1)
    else:
        stack.append(next_a)
        res = dfs(next_a, k-1)
    return res

print(dfs(0, K) + 1)

### FIXED CODE ###

N, K = map(int, input().split())
A = [0] + list(map(int, input().split()))

d = {1:0}
pre_a = 0
a = 1
c = 0
while K:
    K -= 1
    next_a = A[a]
    c += 1
    if next_a in d:
        idx = d[next_a]
        n = len(d)
        K %= (n - idx)
        K += 1
        break
    else:
        d[next_a] = c
        pre_a = a
        a = next_a

while K:
    pre_a = a
    a = A[a]
    K -= 1

print(a)
### BUGGY CODE ###

vec = input().split(' ')
k = int(vec[0])
s = int(vec[1])
count = 0

for x in range(k + 1):
  for y in range(k + 1):
    for z in range(k + 1):
      if x + y + z == s:
        count += 1

print(count)

### FIXED CODE ###

vec = input().split(' ')
k = int(vec[0])
s = int(vec[1])
count = 0
for x in range(k + 1):
    if x <= s:
        for y in range(k + 1):
            if x + y <= s:
                z = s - x - y
                if z >= 0 and z <= k:
                    count += 1
            else: break
    else: break
print(count)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
H,W = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(H)]
B = [list(map(int,input().split())) for _ in range(H)]
D = [[abs(A[h][w]-B[h][w]) for w in range(W)] for h in range(H)]
dp = [[{} for _ in range(W)] for _ in range(H)]
dp[0][0][D[0][0]] = 0
for h in range(H):
    for w in range(W):
        for v in dp[h][w]:
            if w != W-1:
                v1 = v+D[h][w+1]
                v2 = v-D[h][w+1]
                if v1<0:
                    v1 *= -1
                if v2<0:
                    v2 *= -1
                dp[h][w+1][v1] = 0
                dp[h][w+1][v2] = 0
            if h != H-1:
                v1 = v+D[h+1][w]
                v2 = v-D[h+1][w]
                if v1<0:
                    v1 *= -1
                if v2<0:
                    v2 *= -1
                dp[h+1][w][v1] = 0
                dp[h+1][w][v2] = 0
ans = min(dp[H-1][W-1])
print(ans)

### FIXED CODE ###

H,W = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(H)]
B = [list(map(int,input().split())) for _ in range(H)]
D = [[abs(A[h][w]-B[h][w]) for w in range(W)] for h in range(H)]
def cal():
    dp1 = [set() for _ in range(W)]
    dp2 = [set() for _ in range(W)]
    for h in range(H):
        for w in range(W):
            d = D[h][w]
            if h==0 and w==0:
                dp2[0].add(d)
            for v in dp1[w]:
                v1 = v+d
                v2 = v-d if v>=d else -v+d
                dp2[w].add(v1)
                dp2[w].add(v2)
            if 0 < w:
                for v in dp2[w-1]:
                    v1 = v+d
                    v2 = v-d if v>=d else -v+d
                    dp2[w].add(v1)
                    dp2[w].add(v2)
        dp1 = dp2
        dp2 = [set() for _ in range(W)]
    return min(dp1[W-1])
ans = cal()
print(ans)