Harryxun/stf_run huggingface dataset:
def Input():
    matrix = []
    row, col = [int(x) for x in input().split()]
    i = row
    while i > 0:
        matrix.append([int(y) for y in input().split()])
        i -=  1
    return matrix

def calcTotalOfRowAndCol(matrix):
    for l in matrix:
        total = 0
        for val in l:
            total += val
        l.append(total)
    matrix.append([])
    for i in range(6):
        total = 0
        j = 0
        while j < 4:
            total += matrix[j][i]
            j += 1
        matrix[4].insert(i, total)

    return matrix

def Output(matrix):
    for l in matrix:
        print(' '.join(str(x) for x in l))

if __name__ == '__main__':
    matrix1 = Input()
    matrix2 = calcTotalOfRowAndCol(matrix1)
    Output(matrix2)

### FIXED CODE ###

def calcTotalOfRowAndCol(matrix, r, c):
    for l in matrix:
        total = 0
        for val in l:
            total += val
        l.append(total)
    matrix.append([])
    for i in range(c + 1):
        total = 0
        j = 0
        while j < r:
            total += matrix[j][i]
            j += 1
        matrix[r].insert(i, total)

if __name__ == '__main__':
    matrix = []
    row, col = [int(x) for x in input().split()]
    i = row
    while i > 0:
        matrix.append([int(y) for y in input().split()])
        i -= 1
    calcTotalOfRowAndCol(matrix, row, col)
    for l in matrix:
        print(' '.join(str(x) for x in l))
def main():
    import sys
    input = sys.stdin.readline

    n = int(input())
    a = list(map(int, input().split()))
    A = ()
    A_append = A.append
    cnt = 0

    for i in range(n-1):
        A_append(a[i])
        x = sum(A) + a[i+1]
        if sum(A) > 0 and x > 0:
            y = abs(x)+1
            cnt += y
            a[i+1] -= y

        elif sum(A) < 0 and x < 0:
            y = abs(sum(A) - a[i+1])-1
            cnt += y
            a[i+1] += y

    if sum(a) == 0:
        cnt += 1

    print(cnt)

if __name__ == '__main__':
    main()

### FIXED CODE ###

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

def Chk(a, pos):
    cnt = 0
    tmp = 0

    for a in A:
        tmp += a

        if pos and tmp < 1:
            cnt += 1 - tmp
            tmp = 1
        elif not pos and tmp > -1:
            cnt += 1 + tmp
            tmp = -1

        pos = not pos
    return cnt

print(min(Chk(A, True), Chk(A, False)))
def squaremod(A,p,mod):#A^p(mod p)の計算
    if p==0:
        return 1
    if p%2==1:
        return (A*squaremod(A,p-1,mod))%mod
    if p%2==0:
        return (squaremod(A,p/2,mod) %mod)**2 %mod

INV=[None]*(N+1)
for i in range(1,N+1):
    INV[i]=squaremod(i,mod-2,mod)

def Combi(n,r):
    ANS=1
    for i in range(min(r,n-r)):
        ANS *= (N-i)*INV[i+1]

    return ANS
        

ANS=0

if B>A:
    (A,B)=(B,A)

ran=K//A

for i in range(min(ran,N)+1):
    q, r = divmod(K-(A*i), B)
    if r==0 and q<=N:
        ANS = (ANS+(Combi(N,i)*Combi(N,q)))%mod
        #print(q,r,ANS)

print(ANS)

### FIXED CODE ###

N,A,B,K=map(int,input().split())
mod=998244353

INV=[None]*(N+1)
for i in range(1,N+1):
    INV[i]=pow(i,mod-2,mod)

Combi=[None]*(N+1)
Combi[0]=1
Combi[1]=N
for i in range(2,N//2+2):
    Combi[i]=Combi[i-1]*(N-i+1)*INV[i] %mod
for i in range(N//2+2,N+1):
    Combi[i]=Combi[N-i]


ANS=0

if B>A:
    (A,B)=(B,A)

ran=K//A

for i in range(min(ran,N)+1):
    q, r = divmod(K-(A*i), B)
    if r==0 and q<=N:
        ANS = (ANS+(Combi[i]*Combi[q])%mod)%mod

print(ANS)
n=int(input())
m=a=r=c=h=0
ls
for i in range(n):
    s=input()
    if s[0]=='M':
        m+=1
    elif a[0]=='A':
        a+=1
    elif a[0]=='R':
        r+=1
    elif a[0]=='C':
        c+=1
    elif a[0]=='H':
        h+=1
print(m*a*r+m*a*c+m*a*h+m*r*c+m*r*h+m*c*h+a*r*c+a*r*h+a*c*h+r*c*h)

### FIXED CODE ###

n=int(input())
m=a=r=c=h=0
for i in range(n):
    s=input()
    if s[0]=='M':
        m+=1
    elif s[0]=='A':
        a+=1
    elif s[0]=='R':
        r+=1
    elif s[0]=='C':
        c+=1
    elif s[0]=='H':
        h+=1
print(m*a*r+m*a*c+m*a*h+m*r*c+m*r*h+m*c*h+a*r*c+a*r*h+a*c*h+r*c*h)
x = str(input())
if x = "a" or x = "i" or x = "u" or x = "e" or x = "o":
  print("vowel")
else:
  print("consonant")

### FIXED CODE ###

x = str(input())
if x == "a" or x == "i" or x == "u" or x == "e" or x == "o":
  print("vowel")
else:
  print("consonant")
s = input()$
s = s.replace(',', ' ')$
print(s)

### FIXED CODE ###

s = input()
s = s.replace(',', ' ')
print(s)
N,M,K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
ans = 0
time = 0
while time < K:
    if not A:
        ans += 1
        time += B[0]
        B.pop(0)
    elif not B:
        ans += 1
        time += A[0]
        A.pop(0)
    elif A[0] = B[0]:
        if A[1] > B[1]:
            time += B[0]
            ans += 1
            B.pop(0)
        else A[1] < B[1]:
            time += B[0]
            ans += 1
            A.pop(0)
    elif A[0] > B[0] :
        time += B[0]
        ans += 1
        B.pop(0)
    elif A[0] < B[0]:
        time += B[0]
        ans += 1
        A.pop(0)
print(ans)


### FIXED CODE ###

#import sys
N,M,K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

a=[0]
b=[0]
for i in range(N):
    a.append(a[i]+A[i])
for j in range(M):
    b.append(b[j]+B[j])
ans = 0
l = M
for k in range(N+1):
    if a[k] > K:
        break
    while b[l] > K - a[k]:
        l -= 1
    ans = max(ans,k+l)
print(ans)
n, x = map(int, input().split())
l = map(int, input().split())

d = 0
c = 0
for i in range(n):
  d += l[i]
  if d < x:
    c += 1
  else:
    break
    
print(c)

### FIXED CODE ###

n, x = map(int, input().split())
l = list(map(int, input().split()))

d = 0
c = 1

for i in range(n):
  d += l[i]
  if d <= x:
    c += 1

    
print(c)
N = int(input())
S = input()

ret = 0

for i in range(N):
    if S[i] == 'A' and S[i+1] == 'B' and S[i+2] == 'C':
        ret += 1

print(ret)


### FIXED CODE ###

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

ret = 0

for i in range(0, N-2):
    if S[i] == 'A' and S[i+1] == 'B' and S[i+2] == 'C':
        ret += 1

print(ret)
def f(a):
	s=0;q=[]
	for i in range(n):s+=a[i];heappush(q,a[i])
	r=[s]
	for i in range(n,2*n):s+=a[i];s-=heappushpop(q,a[i]);r+=[s]
	return r
import sys;from heapq import*;n,*a=list(map(int,sys.stdin.read().split()));print(max(x+y for x,y in zip(f(a),f(reversed(-e for e in a)))))

### FIXED CODE ###

import sys,heapq
n=int(sys.stdin.readline())
a=list(map(int,sys.stdin.readline().split()))
sa=sb=0
la=[]
lb=[]
for i in range(n):
	sa+=a[i]
	heapq.heappush(la,a[i])
ra=[sa]
for i in range(n,2*n):
	sa+=a[i]
	heapq.heappush(la,a[i])
	sa-=heapq.heappop(la)
	ra.append(sa)
for i in range(3*n-1,2*n-1,-1):
	sb+=a[i]
	heapq.heappush(lb,-a[i])
rb=[sb]
for i in range(2*n-1,n-1,-1):
	sb+=a[i]
	heapq.heappush(lb,-a[i])
	sb+=heapq.heappop(lb)
	rb.append(sb)
print(max(x-y for x,y in zip(ra,reversed(rb))))
a,b = map(str,input().split())
num = 0
if a == "D"
  num = num + 1
if b == "D"
  num = num + 1
if num%2 == 0:
  print("H")
else:
  print("D")

### FIXED CODE ###

a,b = map(str,input().split())
num = 0
if a == "D":
  num = num + 1
if b == "D":
  num = num + 1
if num%2 == 0:
  print("H")
else:
  print("D")
import math

N = int(input())
A = list(map(int, input().split()))
left = [0]*N
right = [0]*N

left_gcd = A[0]
left[0] = A[0]
for i in range(1, N-1):
    left[i] = math.gcd(left_gcd, A[i])

right_gcd = A[-1]
right[-1] = A[-1]
for i in range(N-2, 0, -1):
    right[i] = math.gcd(right_gcd, A[i])

# print(left, right)
max_val = max(left[-2], right[1])
for i in range(1, N-1):
    max_val = max(max_val, math.gcd(left[i-1], right[i+1]))

print(max_val)

### FIXED CODE ###

from fractions import gcd

NN = 202020
MOD = 10**9+7
INF = float("inf")

N = int(input())
A = list(map(int, input().split()))
left = [0]*N
right = [0]*N

left[0] = A[0]
for i in range(1, N-1):
    left[i] = gcd(left[i-1], A[i])

right[-1] = A[-1]
for i in range(N-2, 0, -1):
     right[i] = gcd(right[i+1], A[i])

# print(left, right)
max_val = max(left[-2], right[1])
for i in range(1, N-1):
    max_val = max(max_val, gcd(left[i-1], right[i+1]))

print(max_val)
def main():
    from itertools import permutations

    n, m, r, *x = map(int, open(0).read().split())
    to = x[:r]

    dis = [[float("Inf")] * (n + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        dis[i][i] = 0

    for a, b, c in zip(*[iter(x[r:])] * 3):
        dis[a][b] = c
        dis[b][a] = c

    for k in range(1, n + 1):
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])

    ans = float("Inf")
    done = set()
    for p in permutations(to, r):
        tmp = 0
        if list(p) in done:
            continue
        q = list(p)
        done.add(sorted(q))
        for i, j in zip(p, p[1:]):
            tmp += dis[i][j]
        ans = min(ans, tmp)

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
read = sys.stdin.read
from itertools import permutations
def main():
    def warshall_floyd(d):
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j])
        return d
 
    n, m, r = map(int, input().split())
    rs = tuple(map(int, input().split()))
    d = [[10**9] * n for _ in range(n)]
    m = map(int, read().split())
    mmm = zip(m, m, m)
    for s, t, dis in mmm:
        s -= 1
        t -= 1
        d[t][s] = d[s][t] = dis
    for j1 in range(n):
        d[j1][j1] = 0
    res = warshall_floyd(d)
    rsp = tuple(permutations(rs))
    result = float('inf')
    for rspe in rsp:
        res_t = 0
        for i1 in range(r - 1):
            res_t += res[rspe[i1]-1][rspe[i1+1]-1]
        result = min(result, res_t)
    print(result)
 
if __name__ == '__main__':
    main()
def insertionSort( nums, n, g ):
	global cnt
	for i in range( g, n ):
		v = nums[i]
		j = i - g
		while ( 0 <= j ) and ( v < nums[j] ):
			nums[ j+g ] = nums[j]
			j -= g
			cnt += 1
		nums[ j+g ] = v

def shellSort( nums ):
	global cnt
	g = []
	v = 1
	n = len( nums )
	while v <= n:
		g.append( v )
		v = 3*v+1     
	g.reverse( )
	m = len( g )
	print( m )
	print( " ".join( map( str, g ) ) )  
	cnt = 0
	for i in range( m ):
		insertionSort( nums, n, g[i] )
	print( cnt )

n = int( raw_input( ) )
nums = [ int( raw_input( ) ) for i in range( n ) ]
shellSort( nums )
for v in nums:
	print( v )

### FIXED CODE ###

import sys
 
def insertionSort( nums, n, g ):
    cnt = 0
    i = g
    while i < n:
        v = nums[i]
        j = i - g
        while 0 <= j and v < nums[j]:
            nums[ j+g ] = nums[j]
            j -= g
            cnt += 1
        nums[ j+g ] = v
        i += 1
    return cnt
         
def shellSort( nums, n ):
    g = []
    val = 1
    while val <= n:
        g.append( val )
        val = 3*val+1
     
    g.reverse( )
    m = len( g )
    print( m )
    print( " ".join( map( str, g ) ) )
    cnt = 0
    for i in range( m ):
        cnt += insertionSort( nums, n, g[i] )
    print( cnt )
     
n = int( sys.stdin.readline( ) )
nums = []
for i in range( n ):
    nums.append( int( sys.stdin.readline( ) ) )
 
shellSort( nums, n )
print( "\n".join( map( str, nums ) ) )
n = int(input())
p = list(map(int,input().split()))
ans = 0
for i in range(n-1):
    if i+1 == p[i]:
        p[i+1] = p[i]
        ans += 1
if p[n] == n:
    ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = 0
for i in range(n):
    if i+1 == a[i] and i != n-1:
        b = a[i]
        c = a[i+1]
        a[i] = c
        a[i+1] = b
        ans += 1
    elif i+1 == a[i]:
        ans += 1
print(ans)
def num_of_1bit(n: int)->int:
    s = 0
    while n > 0:
        s += n & 1
        n >>= 1
    return s


def diff_by_1_bit(N: int, A: int, B: int)->list:
    num_A = num_of_1bit(A)
    num_B = num_of_1bit(B)
    if abs(num_A - num_B) & 1 == 1:
        raise [0]
    else:
        return []


if __name__ == "__main__":
    N, A, B = map(int, input().split())
    ans = diff_by_1_bit(N, A, B)
    if len(ans) == 0:
        print('NO')
    else:
        print('YES')
        print(' '.join(map(str, ans)))


### FIXED CODE ###

def num_of_1bit(n: int)->int:
    '''n の立っているビットを数えます。
    :param n: number
    :return: number of 1 bit
    '''
    s = 0
    while n > 0:
        s += n & 1
        n >>= 1
    return s


def diff_idx(a: int, b: int)->int:
    '''a と b のビット列を比較してビットの状態が異なる最小の
    インデックスを返します。ここで、インデックスは 2^i の i 
    に対応する。
    :param a: number 1
    :param b: number 2
    :return: index
    '''
    if a == b:
        return -1
    idx = 0
    while a > 0 or b > 0:
        if a & 1 != b & 1:
            break
        idx += 1
        a, b = a >> 1, b >> 1
    return idx


def remove_bit(n: int, idx: int)->int:
    '''n の idx 番目のビットを消去します。idx は 2^idx に対
    応します。
    ex) n = 1011011, idx = 2
    -> 101111

    :param n: number
    :param idx: index
    :return: number removed `idx`th bit
    '''
    upper = (n >> (idx+1)) << idx
    lower = n & ((1 << idx) - 1)
    return upper | lower


def insert_bit(n: int, idx: int, bit: bool)->int:
    '''n の idx 番目にビットを挿入します。
    ex) n = 101111, idx = 2, bit = True
    -> 1011111
    '''
    upper = (n >> idx) << (idx + 1)
    lower = n & ((1 << idx) - 1)
    insert = bit << idx
    return upper | insert | lower


def route(_from: int, to: int, N: int)->list:
    '''_from から to に至る N ビットの数を全て使ったルートを
    計算します。
    :param _from: start
    :param to: end
    :param N: number of bit
    :return: routes
    '''
    if N == 1:
        return [_from, to]

    di = diff_idx(_from, to)

    a = remove_bit(_from, di)
    b = remove_bit(to, di)
    c = a ^ 1

    from_bit = (_from & (1 << di)) != 0
    to_bit = (to & (1 << di)) != 0

    first_half = map(lambda x: insert_bit(x, di, from_bit), route(a, c, N-1))
    second_half = map(lambda x: insert_bit(x, di, to_bit),  route(c, b, N-1))

    return list(first_half) + list(second_half)


def diff_by_1_bit(N: int, A: int, B: int)->list:
    num_A = num_of_1bit(A)
    num_B = num_of_1bit(B)
    if abs(num_A - num_B) % 2 == 0:
        return []

    return route(A, B, N)


if __name__ == "__main__":
    N, A, B = map(int, input().split())
    ans = diff_by_1_bit(N, A, B)
    if len(ans) == 0:
        print('NO')
    else:
        print('YES')
        print(' '.join(map(str, ans)))
A,B = map(int,input().split())
if A>B:
  print("GREATER")
elif A < B:
  print("LESS")
else:
  print("EQUAL")

### FIXED CODE ###

A = int(input())
B = int(input())

if A>B:
  print("GREATER")
elif A < B:
  print("LESS")
else:
  print("EQUAL")
N = int(input())
S = list(input())
max = N - 1
for i in range(N):
  cnt = S[:i].count('W') + S[i+1:].count('E')
  if cnt < min:
    min = cnt
print(min)

### FIXED CODE ###

N = int(input())
S = list(input())
W = 0
E = S[1:].count('E')
Turn = []
Turn.append(E)

for i in range(1, N):
  if S[i] == 'E':
    E -= 1
  if S[i-1] == 'W':
    W += 1
  Turn.append(E+W)

print(min(Turn))
# -*- coding: utf-8 -*-
# スペース区切りの整数の入力
import sys
import numpy as np
s = sys.stdin.readlines()
N, W = map(int, s[0].split())
matrix = np.zeros((N,N),dtype=np.int)
for idx, iterator in enumerate(s[1:]):
    W_list = iterator
    for w_idx, w_iterator in enumerate(W_list):
        if w_iterator == "#":
            matrix[idx][w_idx] = 1
ch_matrix = matrix.copy()
for i in range(N * 2):
    zero_index_list = np.where(matrix == 0)
    if len(zero_index_list[0]) == 0:
        print(i)
        break
    for i in range(len(zero_index_list[0])):
        row = zero_index_list[0][i]
        col = zero_index_list[1][i]
        bw_checker = 0
        if row != 0:
            bw_checker += matrix[row - 1][col]
        if row != N - 1:
            bw_checker += matrix[row + 1][col]
        if col != 0:
            bw_checker += matrix[row][col - 1]
        if col != W - 1:
            bw_checker += matrix[row][col + 1]
        if bw_checker > 0:
            ch_matrix[row][col] = 1
    matrix = ch_matrix.copy()

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from scipy import ndimage
s = sys.stdin.readlines()
N, W = map(int, s[0].split())
W_matrix = [list(line.strip()) for line in s[1:N + 1]]
matrix_like_list = [[1 if x == "." else 0 for x in W_list] for W_list in W_matrix]
dist = ndimage.distance_transform_cdt(matrix_like_list, metric="taxicab")
print(dist.max())
N = int(input())

if N%2==1:
  print(ans)
else:
  cnt = 0
  NN = (N//10)*10
  for i in range(25):
    cnt += NN//((5**(i+1))*2)
  print(cnt)

### FIXED CODE ###

N = int(input())

if N%2==1:
  print(0)
else:
  cnt = 0
  NN = (N//10)*10
  for i in range(25):
    cnt += NN//((5**(i+1))*2)
  print(cnt)
from numba import jit

n = int(input())
x = input()

def popcount(ni):
    n_b = str(bin(ni))
    return n_b.count("1")

@jit
def ans(n,x):
    x_i = int(x, 2)
    x_orig = popcount(x_i)
    x_i_t = x_i % (x_orig+1)
    x_i_b = x_i % (x_orig-1)
    solve = 0
    n_i = 2**(n-1)
    for i in range(n):
        x_count = x_orig
        if x[i] == "0":
            x_count += 1
            solve = x_i_t + (n_i % x_count)
        else:
            x_count -= 1
            solve = x_i_b - (n_i % x_count) 
        n_i = n_i >> 1 
        count = 0

        if solve != 0 :
            solve = solve % x_count
            count+=1

        while solve > 0:
            solve = solve % popcount(solve)
            count+=1

        print(count)

    
ans(n,x)


### FIXED CODE ###


n = int(input())
x = input()

def popcount(ni):
    n_b = str(bin(ni))
    return n_b.count("1")

def ans(n,x):
    x_i = int(x, 2)
    x_orig = popcount(x_i)
    x_i_t = x_i % (x_orig+1)
    if x_orig != 1:
        x_i_b = x_i % (x_orig-1)
    else:
        x_i_b = x_i
    solve = 0
    for i in range(n):
        x_count = x_orig
        if x[i] == "0":
            x_count += 1
            solve = x_i_t + pow(2,n-1-i,x_count)
        else:
            x_count -= 1
            if x_count != 0:
                solve = x_i_b - pow(2,n-1-i,x_count)
            else:
                print(0)
                continue
        count = 0

        if x_count != 0 :
            solve = solve % x_count
            count+=1

        while solve > 0:
            solve = solve % popcount(solve)
            count+=1

        print(count)

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

xor=0
for i in a:
    xor ^= i

pop=0 #xorのpopにする
while(xor >> pop >=1):
    pop += 1

sum_xor=0 #各猫の排他的論理和
if N%2==1:
    for i in range(pop):
        sum_xor += 2 **i
else:
    sum_xor=xor

ans=[]
for i in range(n):
    x=a[i]^sum_xor
    if i<n-1:
        print(x,end=' ')
    else:
        print(x)

### FIXED CODE ###

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

xor=0
for i in a:
    xor ^= i

pop=0 #xorのpopにする
while(xor >> pop >=1):
    pop += 1

sum_xor=xor #各猫の排他的論理和

ans=[]
for i in a:
    x=i^sum_xor
    ans.append(x)

print(" ".join(map(str, ans)))
n = int(input())
v = list(map(int,input().split()))
c = list(map(int,input().split()))
cnt = 0
for i in range(len(n)):
    if v > c:
        cnt += (v - c)
    else:
        cnt += 0
print(cnt)

### FIXED CODE ###

n = int(input())
v = list(map(int,input().split()))
c = list(map(int,input().split()))
cnt = 0
for i in range(n):
    if v[i] > c[i]:
        cnt += (v[i] - c[i])
print(cnt)
from math import gcd
N, M = map(int, input().split())
A = list(map(int, input().split()))
A = [i // 2 for i in a]
l = 1
for a in A:
    lcd *= a // gcd(lcd, a)
for a in A:
    if lcd // a % 2 == 0:
        print(0)
        exit()
print((M//lcd+1)//2)


### FIXED CODE ###

from math import gcd, ceil
n, m = map(int, input().split())
a = list(map(int, input().split()))
a = [i // 2 for i in a]
l = 1
for i in a:
    l *= i // gcd(l, i)
for i in a:
    if l // i % 2 == 0:
        print(0)
        exit()
print(ceil((m // l) / 2))
S = input()
T = input()
aa = 0
for i in range(length(S)):
  if S[i] != T[i]:
    aa += 1
print(aa)
  


### FIXED CODE ###

S = input()
T = input()
aa = 0
for i in range(len(S)):
  if S[i] != T[i]:
    aa += 1
print(aa)
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)]

AB = [list(map(lambda x, y: abs(x - y), a, b)) for a, b in zip(A, B)]

dp = [[[0] * 6401 for _ in range(W + 1)] for _ in range(H + 1)]
dp[0][0][0] = 1

for h in range(H):
    for w in range(W):
        ab = AB[h][w]
        for i in range(6400):
            if dp[h][w][i] == 1:
                dp[h+1][w][i+ab] = 1
                dp[h+1][w][abs(i-ab)] = 1
                dp[h][w+1][i+ab] = 1
                dp[h][w+1][abs(i-ab)] = 1

for i in range(6400):
    if dp[H][W-1][i] == 1:
        print(i)
        break


### 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)]

AB = [list(map(lambda x, y: abs(x - y), a, b)) for a, b in zip(A, B)]
dp = [[[0] * 12801 for _ in range(W + 1)] for _ in range(H + 1)]
dp[0][0][0] = 1

for h in range(H):
    for w in range(W):
        ab = AB[h][w]
        for i in range(10000):
            if dp[h][w][i] == 1:
                dp[h+1][w][i+ab] = 1
                dp[h+1][w][abs(i-ab)] = 1
                dp[h][w+1][i+ab] = 1
                dp[h][w+1][abs(i-ab)] = 1

for i in range(1000):
    if dp[H][W-1][i] == 1:
        print(i)
        break
s = input()
end = (len(s)-1)//2
start = (len(s)+3)//2
if s[0:end] == s[end-1::-1]:
    if s[start-1::] == s[-1:start-2:-1]:
        if s[0::] == s[::-1]
            print("Yes")
        else:
            print("No")
    else:
        print("No")
else:
    print("No")

### FIXED CODE ###

s = input()
end = (len(s)-1)//2
start = (len(s)+3)//2
if s[0:end] == s[end-1::-1]:
    if s[start-1::] == s[-1:start-2:-1]:
        if s[0::] == s[::-1]:
            print("Yes")
        else:
            print("No")
    else:
        print("No")
else:
    print("No")
n,x = int(input())
gr = [0 for i in range(1,n)]
for i in range(1,n):
  gr[i] = int(input())
print(n-1 + x//min(gr))


### FIXED CODE ###

n,x = map(int,input().split())
m = [int(input()) for i in range(n)]
print(n + (x-sum(m))//min(m))
input()
p = list(map(int, input().split()))
for i, p_ in enumerate(p):
  a += (p_ != (i + 1))
print('YNEOS'[a > 2 :: 2])


### FIXED CODE ###

input()
p = list(map(int, input().split()))
a = 0
for i, p_ in enumerate(p):
  a += (p_ != (i + 1))
print('YNEOS'[a > 2 :: 2])
m,n=map(int,input().split())
par=[i for i in range(m)]
def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x]) #経路圧縮
        return par[x]
def same(x,y):
    return find(x) == find(y)
def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    par[x] = y
for i in range(n):
    a,b=map(int,input().split())
    unite(a,b)

print(len(set(par))-1)

### FIXED CODE ###

n,m=map(int,input().split())
par=[-1 for _ in range(n)]
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x]) #経路圧縮
        return par[x]

def unite(x,y):
    x = find(x)
    y = find(y)

    if x != y:
        x,y=y,x
    else:
        return
    par[x]+=par[y]

    par[y] = x
for _ in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    unite(a,b)

ans=0
for i in par:
    if i<0:
        ans+=1
print(ans-1)
S = str(input())
Q = int(input())
List = [list(map(str, input().split())) for i in range(Q)]

#print(List)

#S='a'
#Q=4
#List=[['2', '1', 'p'], ['1'], ['2', '2', 'c'], ['1']]
han=0
b=''
for a in List:
    if a[0]=='1':
        han+=1
    if a[0]=='2':
        if (a[1]=='1' and han%2==0) or (a[1]=='2' and han%2==1):
            b=+a[2]
        if (a[1]=='2' and han%2==0) or (a[1]=='1' and han%2==1):
            S=S+a[2]
            
if han%2==0:
    print(b[::-1]+S)
else:
    print(S[::-1]+b)
        

### FIXED CODE ###

S = str(input())
Q = int(input())
List = [list(map(str, input().split())) for i in range(Q)]

#print(List)

#S='a'
#Q=4
#List=[['2', '1', 'p'], ['1'], ['2', '2', 'c'], ['1']]
han=0
b=''
for a in List:
    if a[0]=='1':
        han+=1
    if a[0]=='2':
        if (a[1]=='1' and han%2==0) or (a[1]=='2' and han%2==1):
            b+=a[2]
        if (a[1]=='2' and han%2==0) or (a[1]=='1' and han%2==1):
            S=S+a[2]
#print(S)
#print(b)
if han%2==0:
    print(b[::-1]+S)
else:
    print(S[::-1]+b)