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

s=input()
q=int(input())
s1="";s2=""
adds=[s1,s2]
sta=0
for i in range(q):
    a=list(input())#;print(a)
    if a[0]=="1":
        sta^=1
    else:
        if a[2]=="1":
            if not sta:
                s1=a[4]+s1
            else:
                s2+=a[4]
        if a[2]=="2":
            if sta:
                s1=a[4]+s1
            else:
                s2+=a[4]                
ans=s1+s+s2
#print(s1,s,s2)
if sta:
    print(ans[::-1])
else:print(ans)

### FIXED CODE ###

s=input()
q=int(input())
s1="";s2=""
adds=[s1,s2]
sta=0
for i in range(q):
    a=tuple(input().split(" "))#;print(a)
    if a[0]=="1":
        sta^=1
    else:
        if a[1]=="1":
            if not sta:
                s1=a[2]+s1
            else:
                s2+=a[2]
        if a[1]=="2":
            if sta:
                s1=a[2]+s1
            else:
                s2+=a[2]                
ans=s1+s+s2
#print(s1,s,s2)
if sta:
    print(ans[::-1])
else:print(ans)
### BUGGY CODE ###

S = input()

r_list = [0 for _ in range(2019)]
r_list[0 % 2019] += 1
m = len(S)
for i in range(1,m+1):
    r_list[int(S[m-i:]) % 2019] += 1

ans = r_list[0] - 1
for i in range(1,2019):
    if r_list[i] >= 2:
        ans += r_list[i]*(r_list[i]-1)//2

print(ans)


### FIXED CODE ###

S = input()
s_rev = S[::-1]

r_list = [0] * 2019
r_list[0] = 1
num, d = 0, 1
for i in range(len(S)):
    num += d*int(s_rev[i])
    num %= 2019
    r_list[num] += 1
    d *= 10
    d %= 2019

ans = 0
for i in range(2019):
        ans += r_list[i]*(r_list[i]-1)//2

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

n,m=map(int,input().split())
a=list(map(int,input().split()))
for i in range(m):
    b,c=map(int,input().split())
    a+=[c]*b
a=sorted(a)[::-1]
ans=0
for i in range(n):
    ans+=a[i]
print(ans)

### FIXED CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
l=[]
for i in range(n):
    l.append((a[i],1))
for i in range(m):
    b,c=map(int,input().split())
    l.append((c,b))
l=sorted(l,reverse=True) #
ans,cnt=0,n
for x,y in l:
    dy=min(y,cnt) #
    dx=dy*x
    ans+=dx
    cnt-=dy #
print(ans)
#ABC127D
### BUGGY CODE ###

N, M = list(map(int, input().split()))
A_list = list(map(int, input().split()))

cards = A_list
for _ in range(M):
    B, C = list(map(int, input().split()))
    cards.extend([C]*B)
ans = sum(sorted(cards)[-1::-1][:N])
print(ans)

### FIXED CODE ###

N, M = list(map(int, input().split()))
A_list = list(map(int, input().split()))

card = []
card_num = []

for a in A_list:
    card.append(a)
    card_num.append(1)
        
for _ in range(M):
    B, C = list(map(int, input().split()))
    card.append(C)
    card_num.append(B)
    
union = zip(card, card_num)
sorted_union = sorted(union, key=lambda x:x[0])[-1::-1]
sorted_card, sorted_card_num = zip(*sorted_union)

ans = 0
current_num = 0
for c, c_num in zip(sorted_card, sorted_card_num):
    if current_num + c_num < N:
        current_num += c_num
        ans += c * c_num
    else:
        ans += c * (N - current_num)
        current_num = N
        break
print(ans)
### BUGGY CODE ###

from itertools import accumulate
import bisect

n, c = [int(item) for item in input().split()]

xs, vs, xrs = [], [], []
for i in range(n):
  x, v = [int(item) for item in input().split()]
  xs.append(x)
  xrs.append(c-x)
  vs.append(v)
xrs = xrs[::-1]

lft_v = list(accumulate(vs))
rgt_v = list(accumulate(vs[::-1]))

ans = 0
# No return
for i in range(n):
  ans = max(ans, lft_v[i]-xs[i], rgt_v[i]-xrs[i])
  
# Includes return
for i in range(n-1):
  for j in range(n-1-i):
    ans = max(ans, lft_v[i] - xs[i]*2 + rgt_v[j] - xrs[j])
    ans = max(ans, rgt_v[j] - xrs[j]*2 + lft_v[i] - xs[i])
    
print(ans)

### FIXED CODE ###

from itertools import accumulate
import bisect

n, c = [int(item) for item in input().split()]

xs, vs, xrs = [], [], []
for i in range(n):
  x, v = [int(item) for item in input().split()]
  xs.append(x)
  xrs.append(c-x)
  vs.append(v)
xrs = xrs[::-1]

lft_v = list(accumulate(vs))
rgt_v = list(accumulate(vs[::-1]))

lft_c = []
rgt_c = []
for i in range(n):
  lft_c.append(lft_v[i]-xs[i])
  rgt_c.append(rgt_v[i]-xrs[i])
  
lft_max = [0] * n
rgt_max = [0] * n
lm, rm = 0,0
for i in range(n):
  if lm < lft_c[i]:
    lm = lft_c[i]
  lft_max[i] = lm
  if rm < rgt_c[i]:
    rm = rgt_c[i]
  rgt_max[i] = rm

ans = 0
# No return
for i in range(n):
  ans = max(ans, lft_c[i], rgt_c[i])
  
# Includes return
for i in range(n-1):
  ans = max(ans, lft_c[i] - xs[i] + rgt_max[n-2-i])
  ans = max(ans, rgt_c[i] - xrs[i] + lft_max[n-2-i])
    
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python
import math
def solve():
    a, b, c, d = map(int, input().split())
    # 自明
    if d < b or a < b:
        return 'No'
    if c > b:
        return 'Yes'
    a %= b
    if a > c:
        return 'No'
    if d-b == 0:
        return 'Yes'
    cache = set([a])
    while True:
        t = ((c-a)//(d-b)+1)*(d-b)+a
        if c < t < b:
            return 'No'
        a = t % b
        if a in cache:
            return 'Yes'
        else:
            cache.add(a)

T = int(input())
for _ in range(T):
    print(solve())

### FIXED CODE ###

#!/usr/bin/env python
from fractions import gcd

def ng(a, b, c, add):
    return 0 < (b-a)%add < (b-c)

def solve():
    a, b, c, d = map(int, input().split())
    # 自明
    if d < b or a < b:
        return 'No'
    if c > b:
        return 'Yes'
    a %= b
    if a > c:
        return 'No'

    if d-b == 0:
        return 'Yes'

    if gcd(b, d-b) < b-c:
        return 'No'
    else:
        return 'Yes'
    # if ng(a, b, c, d-b):
    #     return 'No'

    # # さんざんまわしたらアウトになる
    # t = (d-b)
    # if ng(a, b, c, :
    #     return 'No'
    
    # return 'Yes' 
    
T = int(input())
for _ in range(T):
    print(solve())
### BUGGY CODE ###

from collections import Counter,defaultdict
import sys,bisect,math,itertools,string,queue
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

n,w = inpl()
ww = [0] * n
vv = [0] * n
for i in range(n):
    ww[i],vv[i] = inpl()
dp = [[0 for i in range(w+1)] for j in range(n+1)]

for i in range(n):
    for j in range(w+1):
        if j >= ww[i]:
            dp[i+1][j] = max(dp[i][j], dp[i][j-ww[i]]+vv[i])
        else:
            dp[i+1][j] = dp[i][j]
print(dp[n][w])


            


### FIXED CODE ###

from collections import Counter,defaultdict
import sys,bisect,math,itertools,string,queue
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

n,w = inpl()
ww = [0] * n
vv = [0] * n
for i in range(n):
    ww[i],vv[i] = inpl()
dp = [[0 for i in range(w+1)] for j in range(n+1)]

for i in range(n):
    for j in range(w+1):
        if j >= ww[i]:
            dp[i+1][j] = max(dp[i][j], dp[i][j-ww[i]]+vv[i])
        else:
            dp[i+1][j] = dp[i][j]
print(dp[n][w])
### BUGGY CODE ###

N, M = map(int, input().split())
import sys
PY = [list(map(int,sys.stdin.readline().rstrip().split())) for _ in range(M)]

# ken = {p[0] for p in PY}
# ken_d = {k:[] for k in ken}
ken_d = [[] for _ in range(N+1)]

for p in PY:
    # print(p)
    ken_d[p[0]].append(p[1])

for k in range(N+1):
    ken_d[k].sort()

for p in PY:
    x = ken_d[p[0]].index(p[1]) + 1
    print(str(p[0]).zfill(6) + str(x).zfill(6))


### FIXED CODE ###

N, M = map(int, input().split())
import sys
PY = [list(map(int,sys.stdin.readline().rstrip().split())) for _ in range(M)]

# ken = {p[0] for p in PY}
# ken_d = {k:[] for k in ken}
ken_d = [[] for _ in range(N+1)]

rankdic = {} # 通し番号：県における順位

for i, p in enumerate(PY):
    # print(p)
    ken_d[p[0]].append([i, p[1]])

for k in range(N+1):
    ken_d[k].sort(key=lambda x:x[1])
    for i, v in enumerate(ken_d[k]):
        rankdic[v[0]] = i # 通し番号辞書に入れる

for i, p in enumerate(PY):
    x = rankdic[i] + 1
    print(str(p[0]).zfill(6) + str(x).zfill(6))
### BUGGY CODE ###

NK = list(map(int, input().split()))
a = [0]*NK[0]
for i in range(len(a)):
    a[i] = int(input())
a.sort()
N = NK[0]
K = NK[1]

b = [0]*K
offsets = [0]*(N-K+1)
for i in range(len(offsets)):
    for j in range(K):
        b[j] = a[i+j]
    offsets[i] = b[K-1] - b[0]

print(min(offsets))


### FIXED CODE ###

NK = list(map(int, input().split()))
a = [0]*NK[0]
for i in range(len(a)):
    a[i] = int(input())
a.sort()
N = NK[0]
K = NK[1]

minimum = a[N-1]
for i in range(N-K+1):
    offset = a[i+K-1] - a[i]
    if minimum > offset:
        minimum = offset

print(minimum)
### BUGGY CODE ###

from operator import itemgetter


class BIT():
    """一点加算、区間取得クエリをそれぞれO(logN)で答える
    add: i番目にvalを加える
    get_sum: 区間[l, r)の和を求める
    i, l, rは0-indexed
    """
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def _sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, val):
        """i番目にvalを加える"""
        i = i + 1
        while i <= self.n:
            self.bit[i] += val
            i += i & -i

    def get_sum(self, l, r):
        """区間[l, r)の和を求める"""
        return self._sum(r) - self._sum(l)



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

def solve(val):
    ruiseki = [0] * (n + 1)
    for i in range(n):
        if a[i] >= val:
            ruiseki[i + 1] = ruiseki[i] + 1
        else:
            ruiseki[i + 1] = ruiseki[i] - 1
    b = sorted(enumerate(ruiseki), key = itemgetter(1))
    bit = BIT(n + 1)
    res = 0
    for i, num in b:
        bit.add(i, 1)
        res += bit.get_sum(0, i)
    if res >= (cnt + 1) // 2:
        return True
    else:
        return False

ok = 0
ng = 10**9 + 1
cnt = 0
for i in range(n):
    cnt += n - i
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if solve(mid):
        ok = mid
    else:
        ng = mid
print(ok)

### FIXED CODE ###

from operator import itemgetter
import sys
input = sys.stdin.readline


class BIT():
    """一点加算、区間取得クエリをそれぞれO(logN)で答える
    add: i番目にvalを加える
    get_sum: 区間[l, r)の和を求める
    i, l, rは0-indexed
    """
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def _sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, val):
        """i番目にvalを加える"""
        i = i + 1
        while i <= self.n:
            self.bit[i] += val
            i += i & -i

    def get_sum(self, l, r):
        """区間[l, r)の和を求める"""
        return self._sum(r) - self._sum(l)



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


def solve(val):
    val = a_sorted[val]
    ruiseki = [0] * (n + 1)
    for i, num in enumerate(a):
        if num >= val:
            ruiseki[i + 1] = ruiseki[i] + 1
        else:
            ruiseki[i + 1] = ruiseki[i] - 1
    b = sorted(enumerate(ruiseki), key = itemgetter(1))
    for i in range(n + 1):
        bit.bit[i] = 0
    res = 0
    for i, _ in b:
        bit.add(i, 1)
        res += bit.get_sum(0, i)
        if res >= cnt:
            return True
    return False


cnt = 0
for i in range(n):
    cnt += n - i
cnt = (cnt + 1) // 2

bit = BIT(n + 1)
ok = 0
ng = n
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if solve(mid):
        ok = mid
    else:
        ng = mid
print(a_sorted[ok])
### BUGGY CODE ###

import time

start_time = time.time()

#input
D = int(input())
c_list = list(map(int, input().split()))

s_grid = []
for i in range(D):
    array = list(map(int, input().strip().split(' ')))
    s_grid.append(array)

t_list = [(i%26) for i in range(D)] #task_list

def calculate_score(t_list,score_list,last_grid,change_query_number):
    score_list = score_list[:change_query_number]
    last_grid = last_grid[:change_query_number]

    if len(score_list) > 1:
        score = score_list[change_query_number-1]
        last_list = last_grid[change_query_number-1]
    else:
        score = 0
        last_list = [0 for i in range(26)]

    for d in range(change_query_number,D):
        score += s_grid[d][t_list[d]]
        last_list = [n+1 for n in last_list]
        last_list[t_list[d]] = 0
        for i in range(26):
            score -= c_list[i]*last_list[i]
        score_list.append(score)
        last_grid.append(last_list)
    return score_list, last_grid

#first cal.
previous_s, previous_l = calculate_score(t_list,[],[[0 for i in range(26)]],0)
score = previous_s[-1]

for k in range(1,D):
    X = -1  # k-日目に変える番号を探す
    t_list_loop = t_list
    for i in range(26):  # 26通り試す
        t_list_loop[k] = i
        score_list_k, last_grid_k = calculate_score(t_list_loop, previous_s, previous_l, k)
        if score_list_k[-1] > score:
            X = i
            score = score_list_k[-1]
            score_list_t = score_list_k
            last_grid_t = last_grid_k

    if X != -1:
        t_list[k] = X
        previous_s = score_list_t
        previous_l = last_grid_t

    # print(k,X,score)

    if time.time() - start_time > 1.99:
        break

#final result
for j in range(len(t_list)):
    print(int(t_list[j]) + 1)

### FIXED CODE ###

t_list = [i % 26 for i in range(365)]
for i in range(365):
	print(t_list[i]+1)
### BUGGY CODE ###

s=list(input())
count=0
for i in range(1,len(s)):
    if s[i-1]==s[i]:
        count+=1
        if s[i]=='0':
            s.pop(i)
            s.insert(i,'1')
        else:
            s.pop(i)
            s.insert(i,'0')
print(count)

### FIXED CODE ###

s=list(input())
s1=[]
s2=[]

for i in range(len(s)):
    if i%2==0:
        s1.append('0')
        s2.append('1')
    else:
        s1.append('1')
        s2.append('0')
    
count1=0
count2=0
for i in range(len(s)):
    if s[i]!=s1[i]:
        count1+=1
    if s[i]!=s2[i]:
        count2+=1
        
print(min(count1,count2))
### BUGGY CODE ###

#import numpy as np
from sys import stdin
from copy import deepcopy
from functools import reduce
from fractions import gcd
import math
import itertools
from collections import Counter
from itertools import chain  ##list(chain.from_iterable(l)) ##flatten
from heapq import heappush, heappop
import bisect

"""
N = int(input())
A, B = map(int,input().split())
A = list(map(int,input().split())) ## 横一列
A = [int(input()) for _ in range(N)] ## 縦一列
lst = [list(map(int,input().split())) for i in range(M)] ## 二次元
"""

N = int(input())
S = [input() for _ in range(N)] ## 縦一列


cnt = list(Counter(S).items())
cnt = sorted(cnt, key=lambda x: (-x[1], x[0]))

max_cnt = cnt[0][1]
for i in range(len(cnt)):
  if cnt[i][1] == max_cnt:
    print(cnt[i][0])
  else:
    exit()

### FIXED CODE ###

from collections import Counter
import bisect

N = int(input())
S = [input() for _ in range(N)] ## 縦一列


cnt = list(Counter(S).items())
cnt = sorted(cnt, key=lambda x: (-x[1], x[0]))

max_cnt = cnt[0][1]

lst = [cnt[i][1] for i in range(len(cnt))][::-1]
n_print = len(cnt) - bisect.bisect_left(lst, max_cnt)

for i in range(n_print):
  print(cnt[i][0])
### BUGGY CODE ###

N,K=map(int,input().split())
A=N
for i in range(N+1):
    A=min(A,abs(N-K*i))
print(A)

### FIXED CODE ###

N,K=map(int,input().split())
B=int(N/K)
A=abs(N-(B-1)*K)
while A>=K/2:
    A=min(abs(A-K),abs(A+K),A)
print(A)
### BUGGY CODE ###

n = int(input())
arr = list(map(int,input().split()))
t = int(input())
su = 0
while t:
    t-=1
    k,r = map(int,input().split())
    p = arr.count(k)
    su = sum(arr)-sum([k]*p)+sum([r]*p)
    arr = list(filter((k).__ne__, arr))
    arr.extend([r]*p)
    print(su)

### FIXED CODE ###

n = int(input())
arr = list(map(int, input().split()))
su = sum(arr)
lst = [0]*100001
q = int(input())
for i in arr:
    lst[i] += 1
for _ in range(q):
    b, c = map(int, input().split())
    su += (c - b) * lst[b]
    print(su)
    lst[c] += lst[b]
    lst[b] = 0
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
nega=[i for i in a if i<0]
zera=[i for i in a if i==0]
posa=[i for i in a if i>0]

def cnt(x):
  y=0
  if x>=0:
    y+=n*len(zera)
  
  for i in posa:
    y+=len([j for j in a if j*i<=x])
  
  y+=n*len(nega)
  
  for i in nega:
    y-=len([j for j in a if j*i>x])
  
  y-=len([j for j in a if j*j<=x])
  return y//2

r=10**18
l=-r-1
while r-l>1:
  c=(r+l)//2
  if cnt(c)>=k:
    r=c
  else:
    l=c
print(r)

### FIXED CODE ###

import numpy as np
n,k=map(int,input().split())
a=list(map(int,input().split()))
a=np.array(a)
a.sort()
nega=a[a<0]
zera=a[a==0]
posa=a[a>0]

def cnt(x):
  y=0
  if x>=0:
    y+=n*len(zera)
  y+=np.searchsorted(a,x//posa,side="right").sum()
  y+=n*len(nega)-np.searchsorted(a,-(-x//nega)).sum() 
  y-=len(a[a*a<=x])
  return y//2

r=10**18
l=-r-1
while r-l>1:
  c=(r+l)//2
  if cnt(c)>=k:
    r=c
  else:
    l=c
print(r)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 1
for a in A:
    ans *= a
if ans > 10 ** 18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

#from collections import deque
def hanbun(L):
    N = len(L)
    flag = N % 2
    N = N // 2
    ans = []
    for i in range(N):
        ans.append(L[2 * i] * L[2 * i + 1])
    if flag == 1:
        ans.append(L[-1])
    return(ans)

N = int(input())
A = list(map(int, input().split()))
while len(A) > 1:
    A = hanbun(A)
ans = A[0]
if ans > 10 ** 18:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
from itertools import groupby,product
def resolve():
    h,w,n=map(int,input().split())
    S=[]
    for _ in range(n):
        a,b=map(int,input().split())
        for i,j in product(range(a-1,a+2),range(b-1,b+2)):
            if(2<=i<=h-1 and 2<=j<=w-1):
                S.append((i,j))
    S.sort()

    ans=[0]*10
    for key,iter in groupby(S):
        ans[len(tuple(iter))]+=1
    ans[0]=(h-2)*(w-2)-sum(ans)
    print(*ans,sep='\n')
resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
from itertools import product
from collections import defaultdict
def resolve():
    h,w,n=map(int,input().split())
    D=defaultdict(int)
    for _ in range(n):
        a,b=map(int,input().split())
        for i,j in product(range(a-1,a+2),range(b-1,b+2)):
            if(1<=i<=h and 1<=j<=w):
                D[(i,j)]+=1

    ans=[0]*10
    for k,v in D.items():
        i,j=k
        if(i==1 or i==h or j==1 or j==w): continue
        ans[v]+=1
    ans[0]=(h-2)*(w-2)-sum(ans)
    print(*ans,sep='\n')
resolve()
### BUGGY CODE ###

n=input()
sum=0

for i in range(len(n)):
  sum=sum+(int(n))
  
if sum%9==0:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

n=int(input())

if n%9==0:
  print('Yes')
else:
  print('No')
### BUGGY CODE ###

def main():
    N, K = map(int, input().split(' '))
    A = list(map(int, input().split(' ')))

    tmp1 = 1
    tmp2 = 1
    for i in range(K):
        tmp1 *= A[i]

    for i in range(1, N - K + 1):
        for j in range(i, i + K):
            tmp2 *= A[j] 
        if tmp1 < tmp2:
            print('Yes')
        else:
            print('No')
        tmp1 = tmp2
        tmp2 = 1
main()

### FIXED CODE ###

def main():
    N, K = map(int, input().split(' '))
    A = list(map(int, input().split(' ')))

    for i in range(N - K):
        if A[i] < A[i + K]:
            print('Yes')
        else:
            print('No')
main()
### BUGGY CODE ###

import numpy as np

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

if N>K:
    for i in range(K):
        H.remove(np.max(H))
    print(sum(H))
else:
    print(0)


### FIXED CODE ###

import numpy as np

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

if K==0:
    print(sum(H))
elif N>K:
    H=sorted(H)
    del H[-K:]
    print(sum(H))
else:
    print(0)
### BUGGY CODE ###

N,P=map(int,input().split())
S=input()

a=[0]*(N+1)
r=[0]*P

if P!=2 and P!=5:
    for i in range(N):
        a[i] = int(S[i:])
        temp=a[i]%P
        r[temp]+=1
    r[0]+=1
    ans=0
    for i in range(P):
        ans+=r[i]*(r[i]-1)//2
elif P==2:
    ans=0
    for i in range(N):
        if int(S[i])%2==0:
            ans+=i+1
elif P==5:
    ans=0
    for i in range(N):
        if int(S[i])==0 or int(S[i])==5:
            ans+=i+1

print(ans)



### FIXED CODE ###

N, P = map(int, input().split())
S = input()

a = [0] * (N + 1)

if P != 2 and P != 5:
    tenfactor=1
    for i in range(1,N+1):
        a[i] = ((int(S[N-i])*tenfactor+a[i-1])%P)
        tenfactor*=10
        tenfactor%=P

    ans = 0
    from collections import Counter
    C=Counter(a)
    for v,i in C.items():
        ans += (i * (i - 1) // 2)
elif P == 2:
    ans = 0
    for i in range(N):
        if int(S[i]) % 2 == 0:
            ans += i + 1
elif P == 5:
    ans = 0
    for i in range(N):
        if int(S[i]) == 0 or int(S[i]) == 5:
            ans += i + 1

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

n,m = map(int,input().split())
p_lists = [list(map(str,input().split())) for _ in range(m)]

# print(p_list)

AC_count = 0
WA_count = 0

AC_question = []
WA_question = {}

for p_list in p_lists:
    if p_list[0] in AC_question:
        continue

    if p_list[1] == 'AC':
        AC_count += 1

        if p_list[0] in WA_question:
            WA_count += WA_question[p_list[0]]

        AC_question.append(p_list[0])

    if p_list[1] == 'WA':
        if p_list[0] in WA_question:
            WA_question[p_list[0]] = WA_question[p_list[0]] + 1
        else:
            WA_question[p_list[0]] = 1

print(AC_count, WA_count)
    


### FIXED CODE ###

n,m = map(int,input().split())
p_lists = [list(map(str,input().split())) for _ in range(m)]

# print(p_list)

AC_count = 0
WA_count = 0

AC_question = set()
WA_question = dict()

for p_list in p_lists:
    if p_list[0] in AC_question:
        continue

    if p_list[1] == 'AC':
        AC_count += 1

        if p_list[0] in WA_question:
            WA_count += WA_question[p_list[0]]

        AC_question.add(p_list[0])

    if p_list[1] == 'WA':
        if p_list[0] in WA_question:
            WA_question[p_list[0]] = WA_question[p_list[0]] + 1
        else:
            WA_question[p_list[0]] = 1

print(AC_count, WA_count)
### BUGGY CODE ###

from collections import deque
h,w = map(int,input().split())
l = [list(input()) for i in range(h)]

dp = [[[-1]*(h*w) for i in range(w)] for i in range(h)]
q = deque([])
if l[0][0] == ".":
    q.append((0,0,0,"."))
else:
    q.append((0,0,1,"#"))
dx = [0,1]
dy = [1,0]
while q:
    
    bx,by,num,bef = q.popleft()
    for j in range(2):
        nx = bx+dx[j]
        ny = by+dy[j]
        if nx < h and ny < w:
            if bef == "." and l[nx][ny] == "#":
                if dp[nx][ny][num+1] == -1:
                
                    dp[nx][ny][num+1] = 1
                    q.append((nx,ny,num+1,l[nx][ny]))
            elif dp[nx][ny][num] == -1:
                dp[nx][ny][num] = 1
                q.append((nx,ny,num,l[nx][ny]))

print(dp[-1][-1].index(1))
              



### FIXED CODE ###

def main():
    from collections import deque
    h,w = map(int,input().split())
    l = [list(input()) for i in range(h)]

    dp = [[[-1]*(h*w) for i in range(w)] for i in range(h)]
    q = deque([])
    if l[0][0] == ".":
        q.append((0,0,0,"."))
    else:
        q.append((0,0,1,"#"))
    dx = [0,1]
    dy = [1,0]
    while q:
        
        bx,by,num,bef = q.popleft()
        for j in range(2):
            nx = bx+dx[j]
            ny = by+dy[j]
            if nx < h and ny < w:
                if bef == "." and l[nx][ny] == "#":
                    if dp[nx][ny][num+1] == -1:
                    
                        dp[nx][ny][num+1] = 1
                        q.append((nx,ny,num+1,l[nx][ny]))
                elif dp[nx][ny][num] == -1:
                    dp[nx][ny][num] = 1
                    q.append((nx,ny,num,l[nx][ny]))

    print(dp[-1][-1].index(1))
if __name__ == "__main__":
    main()