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

import fractions
A, B = map(int, input().split())
C = fractions.gcd(A, B)
D = C
ans = 1
primes = [2]

if C % 2 == 0:
  ans += 1
  while C % 2 == 0:
    C //= 2

p = 1
while C > 1:
  p += 2
  if p ** 2 >= D:
    ans += 1
    primes.append(C)
    break
  for prime in primes:
    if p % prime == 0:
      break
  else:
    primes.append(p)
    if C % p == 0:
      ans += 1
    while C % p == 0:
      C //= p
print(ans)

### FIXED CODE ###

import fractions
import math

A, B = map(int, input().split())
C = fractions.gcd(A, B)
pfac = []

def get_primes(n):
  primes = [2]
  for i in range(3, (n+1), 2):
    for p in primes:
      if i % p == 0:
        break
      if i < p ** 2:
        primes.append(i)
        break
    else:
      primes.append(i)
  return primes

def get_primes2(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n == 1:
        return []
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

for q in get_primes2(min(C, 10**6)):
  if q ** 2 > C:
    break
  if C % q == 0:
    pfac.append(q)
    while C % q == 0:
      C //= q
if C != 1:
  pfac.append(C)


print(len(pfac) + 1)
### BUGGY CODE ###

S = input().strip()
N = len(S)
cur = 0
flag = 0
while cur<N:
    if S[cur:cur+5]=="dream":
        if cur+5==N:
            cur += 5
        elif cur+5<N and S[cur+5]=="d":
            cur += 5
        elif S[cur:cur+7]=="dreamer":
            if cur+7==N:
                cur += 7
            elif S[cur+7] in ["d","e"]:
                cur += 7
            elif S[cur+7]=="a":
                cur += 5
            else:
                flag = 1
                break
    elif S[cur:cur+5]=="erase":
        if cur+5==N:
            cur += 5
        elif cur+5<N and S[cur+5]=="r":
            cur += 6
        elif cur+5<N and S[cur+5] in ["d","e"]:
            cur += 5
        else:
            flag = 1
            break
    else:
        flag=1
        break
if flag==0:
    print("YES")
else:
    print("NO")

### FIXED CODE ###

S = input().strip()
cur = 0
flag = 0
while cur<len(S):
    if S[cur:cur+11]=="dreameraser":
        cur += 11
    elif S[cur:cur+10]=="dreamerase":
        cur += 10
    elif S[cur:cur+7]=="dreamer":
        cur += 7
    elif S[cur:cur+6]=="eraser":
        cur += 6
    elif S[cur:cur+5]=="dream" or S[cur:cur+5]=="erase":
        cur += 5
    else:
        flag = 1
        break
if flag==0:
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A

#B

#C
s = S()
n = len(s)
while len(s)>1:
    i = 0
    f = True
    while s[i] == s[i+1]:
        if i+1 == len(s)-1:
            f = False
            break
        i += 1
    if not f:break
    s.pop(i)
    s.pop(i)
print(n-len(s))
#D

#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T


### FIXED CODE ###

#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
"""
a,b,c = LI()
print(min(b//a,c))
"""

#B
"""
a,b,k = LI()
i = 1
ans = [1]
while i <= min(a,b):
    i += 1
    if a%i == 0 and b%i == 0:
        ans.append(i)
print(ans[-k])
"""

#C
s = list(map(int,S()))
print(2*min(sum(s),len(s)-sum(s)))

#D
"""
def root(x):
    if par[x] == x:
        return x
    par[x] = root(par[x])
    return par[x]
def unite(x,y):
    x = root(x)
    y = root(y)
    if x == y:
        ans.append(ans[-1])
        return
    sx = s[x]
    sy = s[y]
    if rank[x] < rank[y]:
        par[x] = y
        s[y] += sx
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1
        s[x] += sy
    ans.append(ans[-1]+sx*sy)
n,m  = LI()
v = LIR(m)
v = v[::-1]
par = [i for i in range(n)]
rank = [0 for i in range(n)]
s = [1 for i in range(n)]
ans = [0]
k = n*(n-1)//2
v.pop(-1)
for a,b in v:
    if ans[0] == k:
        ans.append(k)
        continue
    a -= 1
    b -= 1
    unite(a,b)
for i in ans[::-1]:
    print(k-i)
"""
#E
"""
n,a,b = LI()
s = input()
ans = 0
i = 0
while i < n:
    j = i+1
    if s[i:j] in s[:i]:
        while s[i:j] in s[:i]:
            j += 1
            if j >= n-1:break
        ans += min(b,a*(j-i))
    else:
        ans += a*(j-i)
    i = j
print(ans)
"""
#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
ans = 0
for i in A:
    for j in B:
        for k in C:
            if i < j < k:
                ans += 1
print(ans)

### FIXED CODE ###

import bisect
N = int(input())
A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())))
ans = 0

for i in B:
    ans += bisect.bisect_left(A,i)*(N-bisect.bisect_right(C,i))
print(ans)
### BUGGY CODE ###

from sys import setrecursionlimit
setrecursionlimit(1000000) 
_ = input()
H = list(map(int, input().split()))

def jump(i):
    if i == 0:
        return 0
    a = abs(H[i] - H[i - 1]) + jump(i - 1)
    if i == 1:
        return a
    b = abs(H[i] - H[i - 2]) + jump(i - 2)
    return min(a, b)

print(jump(len(H) - 1))



### FIXED CODE ###

N = int(input())

H = [int(v) for v in input().strip().split(' ')]

dp = [int(10 ** 10)] * N

dp[0] = 0
dp[1] = abs(H[0] - H[1])

for i in range(2, N):
    dp[i] = min(dp[i], dp[i - 1] + abs(H[i] - H[i - 1]))
    dp[i] = min(dp[i], dp[i - 2] + abs(H[i] - H[i - 2]))

print(dp[-1])
### BUGGY CODE ###

N,M = map(int,input().split())
a,b = map(int, input().split())
former_set = { i for i in range(a,b+1)}
for i in range(M-1):
  a,b =  map(int, input().split())
  tmp_set = { i for i in range(a,b+1)}
  former_set = tmp_set & former_set
print(len(former_set))

### FIXED CODE ###

N,M = map(int,input().split())
a = list()
b = list()
for i in range(M):
  tmp_a,tmp_b =  map(int, input().split())
  a.append(tmp_a)
  b.append(tmp_b)
print(min(b)-max(a)+1 if min(b)-max(a) >= 0 else 0)
### BUGGY CODE ###

s=input()
ans=1000
for i in range(26):
  if chr(97+i) not in s:continue
  S=s
  cnt=0
  while(len(set(S)))!=1:
    cnt+=1
    t=""
    for j in range(len(S)-1):
      if S[j] == chr(97+i) or S[j+1] == chr(97+i):
        t+=chr(97+i)
      else:
        t+=S[j]
  ans=min(cnt,ans)
print(ans)

### FIXED CODE ###

s=input()
ans=1000
for i in range(26):
  if chr(97+i) not in s:continue
  S=s
  cnt=0
  while(len(set(S)))!=1:
    cnt+=1
    t=""
    for j in range(len(S)-1):
      if S[j] == chr(97+i) or S[j+1] == chr(97+i):
        t+=chr(97+i)
      else:
        t+=S[j]
    S=t
  ans=min(cnt,ans)
print(ans)
### BUGGY CODE ###

n,W=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(n)]
dp=[[0 for _ in range(W+1)] for _ in range(n+1)]
for i in range(n):
    weight,value=a[i]
    for j in range(W+1):
        dp[i+1][j]=max(dp[i][j],dp[i+1][j])
        if j+weight<=W:
            dp[i+1][j+weight]=max(dp[i][j+weight],dp[i][j]+value)
print(dp[-1][-1])

### FIXED CODE ###

n,w=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(n)]
dp=[[0 for _ in range(w+1)] for _ in range(n+1)]
for i in range(n):
    for j in range(w+1):
        weight,value=a[i]
        dp[i+1][j]=max(dp[i][j],dp[i+1][j])
        if j+weight<=w:
            dp[i+1][j+weight]=max(dp[i][j+weight],dp[i][j]+value)
print(dp[-1][-1])
### BUGGY CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

from collections import Counter, defaultdict
c = Counter(a)
n1, n2, n3 = c[1], c[2], c[3]
n0 = c[0]
def glist(*l):
    for num in l:
        []
sub = {}
count = 0
S = sum(a)
for s in range(S+1):
    for i1 in range(s+1):
        for i2 in range((s-i1)//2+1):
            d,m = divmod((s-i1-2*i2), 3)
            if m:
                continue
            i3 = d
            count += 1
            if i1==i2==i3==0:
                sub[i1,i2,i3] = 0
                continue
            ans = 1
            p = 0
            if i1>0:
                ans += i1/n * sub[i1-1,i2,i3]
                p += i1/n
            if i2>0:
                ans += i2/n * sub[i1+1,i2-1,i3]
                p += i2/n
            if i3>0:
                ans += i3/n * sub[i1,i2+1,i3-1]
                p += i3/n
            ans = ans/p
            sub[i1,i2,i3] = ans
print(sub[n1,n2,n3])

### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

from collections import Counter, defaultdict
c = Counter(a)
n1, n2, n3 = c[1], c[2], c[3]
n0 = c[0]
def glist(*l, fill=None):
    if len(l)==1:
        return [fill]*l[0]
    ll = l[1:]
    return [glist(*ll) for _ in range(l[0])]

count = 0
S = sum(a)
sub = glist(n1+n2+n3+1,n2+n3+1,n3+1)
sub[0][0][0] = 0
#     for i1 in range(min(n+1, s+1)):
#         for i2 in range(min(n+1, (s-i1)//2+1)):
for i3 in range(n3+1):
    for i2 in range(n2+n3+1-i3):
        for i1 in range(n1+n2+n3 - (i2+i3) + 1):
            if i1==i2==i3==0 or i1+i2+i3>n:
                continue
#             print(i1,i2,i3)
            ans = n
            p = 0
            if i1>0:
                ans += i1 * sub[i1-1][i2][i3]
                p += i1
            if i2>0:
                ans += i2 * sub[i1+1][i2-1][i3]
                p += i2
            if i3>0:
                ans += i3 * sub[i1][i2+1][i3-1]
                p += i3
            ans = ans/p
            sub[i1][i2][i3] = ans
print(sub[n1][n2][n3])
### BUGGY CODE ###

s = input()
t = input()
q = int(input())

def check(x, y):
	xa = len(list(filter(lambda i: i == "A", x)))
	ya = len(list(filter(lambda i: i == "A", y)))
	if (2 * xa - len(x)) % 3 == (2 * ya - len(y)) % 3:
		print("YES")
	else:
		print("NO")

for _ in range(q):
	a, b, c, d = map(int, input().split())
	check(s[a - 1 : b], t[c - 1 : d])


### FIXED CODE ###

s = input()
t = input()
q = int(input())

sa_pre = [s[i] == "A" for i in range(len(s))]
ta_pre = [t[i] == "A" for i in range(len(t))]

sa = [0, sa_pre[0]]
ta = [0, ta_pre[0]]

for i in range(1, len(s)):
	sa.append(sa[-1] + sa_pre[i])

for i in range(1, len(t)):
	ta.append(ta[-1] + ta_pre[i])

def check(a, b, c, d):
	xa = sa[b] - sa[a - 1]
	ya = ta[d] - ta[c - 1]
	if (2 * xa - (b - a + 1)) % 3 == (2 * ya - (d - c + 1)) % 3:
		print("YES")
		return
	else:
		print("NO")
		return

for _ in range(q):
	a, b, c, d = map(int, input().split())
	check(a, b, c, d)
### BUGGY CODE ###

#/usr/bin/env python

n = int(input())
a = [int(input()) for _ in range(n)]

lighted = [0] 
ans = 0 

while True:
    u = lighted[-1]
    v = a[u]-1
    ans += 1
    if v == 1:
        print(ans)
        exit()
    if v not in lighted:
        lighted.append(v)
    else:
        print(-1)
        exit()


### FIXED CODE ###

#/usr/bin/env python

n = int(input())
a = [int(input()) for _ in range(n)]

lighted = [0] 
ans = 0 

for i in range(n):
    u = lighted[-1]
    v = a[u]-1
    ans += 1
    if v == 1:
        print(ans)
        exit()
    lighted.append(v)

print(-1)
### BUGGY CODE ###

import sys

input = sys.stdin.readline

n = int(input())

e = [[] for _ in range(n)]
for i in range(n):
    a = map(int, input().split())
    for aa in a:
        aa -= 1
        e[i].append(aa)
# print(e)

inds = [0] * n
cur = [e[i][0] for i in range(n)]
# print(cur)
cnt = 0
while sum(cur) != -n:
    flg = False
    bls = [False] * n
    for ind, target in enumerate(cur):
        if bls[ind] or bls[target]:
            continue
        if cur[target] == ind:
            flg = True
            inds[ind] += 1
            inds[target] += 1
            bls[ind] = True
            bls[target] = True
            cur[ind] = e[ind][inds[ind]] if inds[ind] < n - 1 else -1
            cur[target] = e[target][inds[target]] if inds[target] < n - 1 else -1
    if not flg:
        print(-1)
        exit()
    cnt += 1
    # print(cur, cnt)

print(cnt)


### FIXED CODE ###

def check(player):
    if not a[player]:
        return
    opponent = a[player][-1]
    if not a[opponent]:
        return
    if a[opponent][-1] == player:
        tpl = (player, opponent)
        q.add((min(tpl), max(tpl)))


n = int(input())

a = []
for _ in range(n):
    t = list(map(lambda x: int(x) - 1, input().split()))
    t.reverse()
    a.append(t)

q = set()
for i in range(n):
    check(i)

day = 0
while q:
    day += 1
    prev_q = set()
    q, prev_q = prev_q, q
    for player, opponent in prev_q:
        a[player].pop()
        a[opponent].pop()
    for player, opponent in prev_q:
        check(player)
        check(opponent)

if any(a[player] for player in range(n)):
    print(-1)
    exit()

print(day)
### BUGGY CODE ###

def main():
    H, W = map(int, input().split())
    A = []
    for _ in range(H):
        a = input()
        A.append(a)
    bl = set()
    wl = set()
    for i in range(H):
        for j in range(W):
            if A[i][j] == '#':
                bl.add((i, j))
            else:
                wl.add((i, j))
    r = 0
    while wl:
        bln = set()
        for i in bl:
            if (i[0] + 1, i[1]) in wl:
                wl.remove((i[0] + 1, i[1]))
                bln.add((i[0] + 1, i[1]))
            if (i[0] - 1, i[1]) in wl:
                wl.remove((i[0] - 1, i[1]))
                bln.add((i[0] - 1, i[1]))
            if (i[0], i[1] + 1) in wl:
                wl.remove((i[0], i[1] + 1))
                bln.add((i[0], i[1] + 1))
            if (i[0], i[1] - 1) in wl:
                wl.remove((i[0], i[1] - 1))
                bln.add((i[0], i[1] - 1))
        bl = bln
        r += 1
    return r
print(main())


### FIXED CODE ###

def main():
    H, W = map(int, input().split())
    A = []
    for _ in range(H):
        a = input()
        A.append(a)
    bl = []
    wl = set()
    for i in range(H):
        for j in range(W):
            if A[i][j] == '#':
                bl.append((i, j))
            else:
                wl.add((i, j))
    r = 0
    while wl:
        bln = []
        for i in bl:
            if (i[0] + 1, i[1]) in wl:
                wl.remove((i[0] + 1, i[1]))
                bln.append((i[0] + 1, i[1]))
            if (i[0] - 1, i[1]) in wl:
                wl.remove((i[0] - 1, i[1]))
                bln.append((i[0] - 1, i[1]))
            if (i[0], i[1] + 1) in wl:
                wl.remove((i[0], i[1] + 1))
                bln.append((i[0], i[1] + 1))
            if (i[0], i[1] - 1) in wl:
                wl.remove((i[0], i[1] - 1))
                bln.append((i[0], i[1] - 1))
        bl = bln
        r += 1
    return r
print(main())
### BUGGY CODE ###

A,B,N=map(int,input().split())
result=0
if N>=B:
	N=B
for x in range(0,N+1):
	a=int(A*x/B)-A*int(x/B)
	if a>result:
		result=a
print(result)

### FIXED CODE ###

A,B,N=map(int,input().split())
if B!=1:
	p=(N+1)//B
	result=0
	if p!=0:
		for a in range(1,p+1):
			x=a*B-1
			s=(A*x)//B - A*(a-1)
			if result < s:
				result=s
	else:
		result=A*N//B -A*(N//B)
	print(result)
else:
	print(0)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline


def dfs(v, par):
    for nv in tree[v]:
        if nv != par:
            adds[nv] += adds[v]
            dfs(nv, v)


n,q = map(int, input().split())
tree = [[]for _ in range(n)]
for i in range(n-1):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    tree[a].append(b)
    tree[b].append(a)

adds = [0] * n
for i in range(q):
    p,x = map(int, input().split())
    p -= 1
    adds[p] += x
dfs(0, -1)
print(*adds)


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline


def dfs(v, par):
    for nv in tree[v]:
        if nv != par:
            adds[nv] += adds[v]
            dfs(nv, v)


n,q = map(int, input().split())
tree = [[]for _ in range(n)]
for i in range(n-1):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    tree[a].append(b)
    tree[b].append(a)

adds = [0] * n
for i in range(q):
    p,x = map(int, input().split())
    p -= 1
    adds[p] += x
dfs(0, -1)
print(*adds)
### BUGGY CODE ###

from decimal import Decimal


def solve(n, d, x):
    ans = 0
    while n:
        ans += d + (2 * n - 1) * x / 2
        d = ((n + 1) * d + 5 * x / 2) / n
        x *= (n + 2) / n
        n -= 1
    return ans


print(solve(*map(Decimal, input().split())))


### FIXED CODE ###

def solve(n, d, x):
    ans = 0
    while n:
        ans += d + (2 * n - 1) * x / 2
        d = ((n + 1) * d + 5 * x / 2) / n
        x *= (n + 2) / n
        n -= 1
    return ans


print('{:.10f}'.format(solve(*map(float, input().split()))))
### BUGGY CODE ###

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

lcm = 1
from fractions import gcd
for i in range(n):
    lcm *= a[i] // gcd(a[i], lcm)

ans = 0
for i in a:
    ans += lcm // i

print(ans % (10**9+7))

### FIXED CODE ###

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

lcm = 1
from fractions import gcd
for i in range(n):
    lcm *= a[i] // gcd(a[i], lcm)

ans = 0
for i in a:
    ans += lcm // i

print(ans % (10**9+7))
### BUGGY CODE ###

a, b, x = map(int, input().split())
num = 0
for t in range(a, b + 1):
    if t % x == 0:
        num += 1
print(num)

### FIXED CODE ###

a, b, x = map(int, input().split())
if a == 0:
    num = b // x + 1
else:
    num = b // x - (a - 1) // x
print(num)
### BUGGY CODE ###

import numpy as np
N = int(input())
S = np.array([list(input()) for _ in range(N)], dtype="U1")
S = np.concatenate([S, S], axis=1)
S = S.tolist()


def check(x):
    for i in range(N):
        for j in range(i+1, N):
            if S[i][j + x] != S[j][i + x]:
                return 0
    return N


ans = 0
for x in range(N):
    ans += check(x)

print(ans)


### FIXED CODE ###

import numpy as np
N = int(input())
S = [[ord(i) for i in input()] * 2 for _ in range(N)]
S = np.array(S)

ans = 0
for i in range(N):
    tmp = S[:, i: i + N]
    if (tmp == tmp.T).all():
        ans += 1

ans = ans * N
print(ans)
### BUGGY CODE ###

import sys

ri = lambda: int(sys.stdin.readline())
rl = lambda: list(map(int, sys.stdin.readline().split()))

a = ri()
li = sorted(rl(), reverse=True)
cnt = 0
for i in range(a-2):
    for j in range(i+1, a-1):
        left = j+1
        right = a
        lii = li[i]
        lij = li[j]
        if lii >= lij + li[j+1]:
            continue
        while right-left > 1:
            t = (left + right)//2
            lit = li[t]
            if lii < lij + lit:
                left = t
            else:
                right = t
        cnt += left-j
print(cnt)



















### FIXED CODE ###

import sys

ri = lambda: int(sys.stdin.readline())
rl = lambda: list(map(int, sys.stdin.readline().split()))

a = ri()
li = sorted(rl(), reverse=True)
cnt = 0
for i in range(a-2):
    for j in range(i+1, a-1):
        left = j+1
        right = a
        lii = li[i]
        lij = li[j]
        if lii >= lij + li[j+1]:
            continue
        while right-left > 1:
            t = (left + right)//2
            lit = li[t]
            if lii < lij + lit:
                left = t
            else:
                right = t
        cnt += left-j
print(cnt)
### BUGGY CODE ###

N, K = map(int, input().split())
A = [int(x) for x in input().split()]

A_past = 1
for Ai in A[:K]:
  A_past *= Ai

for i in range(N-K):
  A_now = 1
  A_now = A_past*A[i+K]/A[i]
  if A_now > A_past:
    print("Yes")
  else:
    print("No")
  A_past = A_now



### FIXED CODE ###

N, K = map(int, input().split())
A = [int(x) for x in input().split()]

for i in range(N-K):
  t = A[i+K]/A[i]
  if t > 1:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

h,w=map(int,input().split())
D=[list(input()) for i in range(h)]
# D[i][j]はD[h-1][w-1]まで
#dfs
stack=[]
stack.append((0,0,0))
da=[0,1]
db=[1,0]
infi=10**10
ans=infi
while stack:
    a,b, cnt=stack.pop()
    if D[a][b]=='#':
        cnt+=1
    if a+b==(h+w-2):
        ans=min(ans,cnt)
    for i in range(2):
        p=a+da[i]
        q=b+db[i]
        if 0<=p and p<=h-1 and 0<=q and q<=w-1:
            stack.append((p,q,cnt))
print(ans)

### FIXED CODE ###

# import sys
# input = sys.stdin.readline
h,w=map(int,input().split())
infi=10**10
D=[list(input()) for i in range(h)]
kotae=[[infi]*(w) for _ in range(h)]
# D[i][j]はD[h-1][w-1]まで

cnt=0
if D[0][0]=='.':
    kotae[0][0]=0
else:
    kotae[0][0]=1
    cnt+=1
for i in range(1,h):
    if D[i][0]=='#' and D[i-1][0]=='.':
        cnt+=1
    kotae[i][0]=cnt

cnt=0
if D[0][0]=='.':
    kotae[0][0]=0
else:
    kotae[0][0]=1
    cnt+=1
for j in range(1,w):
    if D[0][j]=='#' and D[0][j-1]=='.':
        cnt+=1
    kotae[0][j]=cnt
for i in range(h-1):
    for j in range(w-1):
        kouho1 = kotae[i][j+1]
        if D[i][j+1]=='.' and D[i+1][j+1]=='#':
            kouho1+=1
        kouho2=kotae[i+1][j]
        if D[i+1][j]=='.' and D[i+1][j+1]=='#':
            kouho2+=1
        kotae[i+1][j+1]=min(kouho1,kouho2)
print(kotae[h-1][w-1])
### BUGGY CODE ###

import sys
import itertools

def resolve(in_):
    N = int(next(in_))
    A = list(map(int, next(in_).split()))

    mod = 10 ** 9 + 7
    ans = 0
    for i, a in enumerate(A):
        v = sum(A[i + 1:])
        ans += a * v
        ans %= mod

    return ans
    

def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys


def resolve(in_):
    N = int(next(in_))
    A = tuple(map(int, next(in_).split()))

    mod = 10 ** 9 + 7
    ans = 0
    v = sum(A)
    for a in A:
        v -= a
        ans += a * v
        ans %= mod

    return ans
    

def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


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

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

flg = True
for q in Q:
    if q[0] == "1":
        flg = not flg
    else:
        F = int(q[1])
        if not flg:
            F = 3 - F
        if F == 1:
            S = q[2] + S
        if F == 2:
            S = S + q[2]

if not flg:
    S = S[::-1]
print(S)

### FIXED CODE ###

s = input()
q = int(input())
Q = [list(map(str, input().split())) for _ in range(q)]

t = ''
for qi in Q:
  if int(qi[0]) == 1:
    s, t = t, s
  else:
    if int(qi[1])  == 1:
      t += qi[2]
    else:
      s += qi[2]
      
t = t[::-1]
t += s
print(t)