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

N = 10**7


def f(x):
    return x


M = 10**5
arr = list(range(M))
for i in range(N):
    t = (i + i * i - i) % M  # 四則演算
    b = arr[t]  # 配列ランダムアクセス
    b = f(b)  # 関数呼び出し

# 答え
a = int(input())
print(a + a**2 + a**3)


### FIXED CODE ###

import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


def main():

    a = in_n()
    print(a + a**2 + a**3)


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

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

boxin = []
for cnt in range(N, 0, -1):
    a = ax[cnt-1]
    
    i = 2
    memo_cnt = 0
    while 1:
        test_val = i * cnt
        if test_val > N:
            break
        if test_val in boxin:
            memo_cnt += 1
        i += 1
    if a != memo_cnt % 2:
        boxin.append(cnt)

 
box = len(boxin)
print(box)
if box != 0:
    boxin.reverse()
    print(' '.join(map(str, boxin)))

### FIXED CODE ###

import math
N = int(input())
ax = list(map(int,input().split()))

M = 0
boxin = []
bx = [0 for _ in range(N+1)]
for cnt in range(N, 0, -1):
    a = ax[cnt-1]
    tmp = 0
    for tmp_cnt in range(cnt*2, N+1, cnt):
        if bx[tmp_cnt] != 0:
            tmp += 1
    
    if tmp % 2 != a:
        bx[cnt] = 1
        boxin.append(cnt)

box = len(boxin)
print(box)
if box != 0:
    boxin.reverse()
    print(' '.join(map(str, boxin)))
### BUGGY CODE ###

from math import ceil
N, A, B = map(int, raw_input().split())
h = [0] * N
for i in range(N):
  h[i], = map(int, raw_input().split())
h.sort()

l = 0
r = int(ceil(1.0*h[-1]/B))
while True:
  m = (l+r)//2
  if m==l:
    break
  c = 0
  for i in range(N):
    ai = int(ceil(1.0*max(0,h[i]-B*m)/(A-B)))
    c += ai
  if c>m:
    l = m
  else:
    r = m
print r

### FIXED CODE ###

from math import ceil
N, A, B = map(int, raw_input().split())
h = [0] * N
for i in range(N):
  h[i], = map(int, raw_input().split())
h.sort()

l = 0
r = int(ceil(1.0*h[-1]/B))
while True:
  m = (l+r)//2
  if m==l:
    break
  c = 0
  for i in range(N):
    ai = int(ceil(1.0*max(0,h[i]-B*m)/(A-B)))
    c += ai
  if c>m:
    l = m
  else:
    r = m
print r
### BUGGY CODE ###

import fractions
n=int(input())
a=list(map(int,input().split()))
for _ in range(n-1):
    a1=a.pop(0)
    a2=a.pop(0)
    a.append(fractions.gcd(a1,a2))
print(a[0])

### FIXED CODE ###

import fractions
n=int(input())
a=list(map(int,input().split()))
ans=[0]*(n+1)
ans[1]=a[0]
for i in range(2,n+1):
    ans[i]=fractions.gcd(ans[i-1],a[i-1])
print(ans[-1])
### BUGGY CODE ###

n,t=map(int,input().split())
a=list(map(int,input().split()))
max=0
ans=1
for i in range(len(a)-1):
  for j in range(i+1,len(a)):
    if (a[j]-a[i])>max:
      max=a[j]-a[i]
      ans=1
    elif (a[j]-a[i])==max:
      ans+=1
    else:
      pass
print(ans)
  

### FIXED CODE ###

n,t=map(int,input().split())
a=list(map(int,input().split()))
max=0
min=1000000000000000000000000000000000000
ans=1
for i in range(len(a)-1):
  if a[i]<min:
    min=a[i]
  elif min==a[i] or max==a[i]-min:
    ans+=1
  elif max<a[i]-min:
    ans=1
    max=a[i]-min
if a[len(a)-1]-min==max:
  ans+=1
print(ans)
### BUGGY CODE ###

from collections import defaultdict, Counter
import sys
input = sys.stdin.readline
def main():
    # Load data
    N = int(input())
    A = list(map(int, input().split()))
    p = 10**9 + 7
    # LCM: dict 最小公倍数の素因数分解
    LCM = defaultdict(int)
    # A2Factor: list A[i]の素因数分解
    A2Factor = []
    
    def factorization(n):
        arr = []
        temp = n
        for i in range(2, int(-(-n**0.5//1))+1):
            if temp%i==0:
                # cnt=0
                while temp%i==0:
                    # cnt+=1
                    temp //= i
                    arr.append(i)

        if temp!=1:
            # arr[temp] = 1
            arr.append(temp)

        if not arr:
            # arr[n] = 1
            arr.append(n)

        return arr

    for idx in range(N):
        arr = factorization(A[idx])
        arr = Counter(arr)
        for key, value in arr.items():
            LCM[key] = max(LCM[key], value)
        A2Factor.append(arr)
    ans = 0
    for i in range(N):
        tmp = 1
        for key, value in LCM.items():
            cnt = 0 if key not in A2Factor[i].keys() else A2Factor[i][key]
            tmp *= pow(key, value-cnt, p)
            tmp %= p
        ans += tmp % p
        ans %= p

    print(ans % p)

main()

### FIXED CODE ###

from math import gcd

def lcm(a, b):
    return a*b//gcd(a,b)
def main():
    N = int(input())
    A = list(map(int, input().split()))
    mod = 10**9 + 7
    LCM = 1
    for a in A:
        LCM = lcm(LCM, a)
    ans = 0
    for a in A:
        ans += (LCM//a)
        

    print(ans % mod)
main()
### BUGGY CODE ###

import bisect
from collections import deque
n,m = map(int,input().split())
ab=[]
for i in range(n):
    ab.append(list(map(int,input().split())))

lis = [[]for i in range(m)]

for i in range(n):
    if ab[i][0]<=m:
        lis[ab[i][0]-1].append(ab[i][1])

pys = []
sum = 0
for i in range(m):
    tmp = lis[i]
    if tmp:
        for j in tmp:
            bisect.insort(pys,j)
    if pys:
        sum+=pys.pop()

print(sum)


### FIXED CODE ###

#import bisect
import heapq
from collections import deque
n,m = map(int,input().split())
ab=[]
for i in range(n):
    ab.append(list(map(int,input().split())))

lis = [[]for i in range(m)]

for i in range(n):
    if ab[i][0]<=m:
        lis[ab[i][0]-1].append(ab[i][1])

pys = []
heapq.heapify(pys)
sum = 0
for i in range(m):
    tmp = lis[i]
    if tmp:
        for j in tmp:
            heapq.heappush(pys,-j)
    if pys:
        sum-=heapq.heappop(pys)

print(sum)
### BUGGY CODE ###

from itertools import combinations
from functools import reduce
from operator import xor

def checkxor(a,b):
    zero = set()
    one = set()
    for i in range(1,len(a)+1):
        for x in combinations(a,i):
            zero.add(reduce(xor,x))
    for i in range(1,len(b)+1):
        for x in combinations(b,i):
            one.add(reduce(xor,x))
    if zero == one:
        return True
    else:
        return False

T = int(input())
for i in range(T):
    N = int(input())
    A = list(map(int, input().split()))
    S = input()
    if S[-1] == '1':
        print('1')
    elif S.count('0') == len(S):
        print('0')
    else:
        zeros = []
        ones = []
        for j in range(len(S)):
            if S[j] == '1':
                ones.append(A[j])
                current = 1
                break
        for k in range(j+1,len(S)):
            if S[k] == '1':
                if current == 1:
                    ones.append(A[k])
                else:
                    if checkxor(zeros,ones) == False:
                        print('1')
                        break
                    else:
                        ones.append(A[k])
                        current = 1
            else:
                if current == 0:
                    zeros.append(A[k])
                else:
                    zeros.append(A[k])
                    current = 0
        if checkxor(zeros,ones) == False:
            print('1')
        else:
            print('0')

### FIXED CODE ###

T = int(input())
for i in range(T):
    N = int(input())
    A = list(map(int, input().split()))
    S = input()
    base = []
    for i in range(1,N+1):
        temp = A[-i]
        for x in base:
            temp = min(temp,temp^x)
        if temp != 0:
            if S[-i] == '1':
                print('1')
                break
            else:
                base.append(temp)
    else:
        print('0')
### BUGGY CODE ###

def isort(A, n, g):
    global cnt
    for i in range(g, n):
        v = A[i]
        j = i - g
        while j >= 0 and A[j] > v:
            A[j + g] = A[j]
            j -= g
            cnt += 1
        A[j + g] = v

def ssort(A, n):
    global cnt
    cnt = 0
    m = max(min(int(n / 3), 100), 1)
    G = [m * 3 - 3 * (i + 1) + 1 for i in range(m - 1)]
    G.append(1)
    print(m)
    print(" ".join([str(g) for g in G]))
    for g in G:
        isort(A, n, g)

n = int(input())
A = [int(input()) for _ in range(n)]
ssort(A, n)
print(cnt)
for a in A:
    print(a)

### FIXED CODE ###

import sys

def isort(A, n, g):
    cnt = 0
    for i in range(g, n):
        v = A[i]
        j = i - g
        while j >= 0 and A[j] > v:
            A[j + g] = A[j]
            j -= g
            cnt += 1
        A[j + g] = v
    return cnt

def ssort(A, n):
    cnt = 0
    G = []
    h = 1
    while h <= n:
        G.append(h)
        h = 3 * h + 1
    m = len(G)
    G.reverse()
    print(m)
    print(*G, sep = " ")
    for g in G:
        cnt += isort(A, n, g)
    return cnt

n = int(input())
A = list(map(int, sys.stdin.readlines()))
cnt = ssort(A, n)
print(cnt)
print(*A, sep = "\n")
### BUGGY CODE ###

n,k=(int(i) for i in input().split())

e = [[int(i) for i in input().split()] for j in range(n)]
#print(e)

dp=[[0 for i in range(k+1)] for j in range(n)]

for j in range(k+1):
    if j >= e[0][0]:
      dp[0][j]=e[0][1]

for i in range(1,n):
  for j in range(k+1):
    if j < e[i][0]:
      dp[i][j]=dp[i-1][j]
    else:
      dp[i][j]=max(dp[i-1][j],dp[i-1][j-e[i][0]]+e[i][1])

print(max(dp[n-1]))


### FIXED CODE ###

n,k=(int(i) for i in input().split())
e = [[int(i) for i in input().split()] for j in range(n)]
#print(n,k,e)
maxv=0
for i in range(n):
    maxv+=e[i][1]
#print(maxv)

dp = [[0 for i in range(maxv+1)] for j in range(n+1)]
#print(dp)

for i in range(1, maxv+1):
    dp[0][i] = float('inf')
#print(dp)

for j in range(n):
    for i in range(1, maxv+1):
        if i < e[j][1] :
            dp[j + 1][i] = dp[j][i]
        else:
            dp[j + 1][i] = min(dp[j][i], dp[j][i - e[j][1]] +e[j][0])
#print(dp)
ans = 0
for i in range(maxv+1):
    if dp[n][i] <= k and ans < i:
        ans = i
        
print(ans)
### BUGGY CODE ###

m=int(input())
d,c=[],[]
ans=-1
for i in range(m):
  dd,cc=map(int,input().split())
  d.append(dd)
  c.append(cc)
  ans+=cc
a=0
ds=lambda n:sum(list(map(int,list(str(n)))))
for i in range(m):
  if d[i]*c[i]+a<10:a+=d[i]*c[i]
  else:
    if c[i]*d[i]>9:
      ci,di=c[i],d[i]
      while ci*di>9:
        cd=(0--10//di)
        ci,di,cci,ddi=ci//cd,ds(cd*di),ci-(ci//cd*cd),di
        ans+=ci
        if ddi*cci+a>9:ans+=1
        a=ds(ddi*cci+a)
      if di*ci+a>9:ans+=1
      a=ds(di*ci+a)
    else:
      ans+=1
      a=ds(a+c[i]*d[i])
print(ans)

### FIXED CODE ###

m=int(input())
d,c=[],[]
ans=-1
for i in range(m):
  dd,cc=map(int,input().split())
  d.append(dd)
  c.append(cc)
  ans+=cc
a=0
for i in range(m):
  a+=d[i]*c[i]
  dd=(a-1)//9
  ans+=dd
  a-=dd*9
print(ans)
### BUGGY CODE ###

n = int(input())
s = []
b = []
count = 0
for i in range(n):
  s.append(input())
  a = (list(s[0]))
  a.sort()
    
  
  s.pop(0)
  b.append("".join(a))
  a.clear()

  
  
for i in range(n):
  for j in range(n-i-1):
    if b[i] == b[i+j+1]:
      count += 1

print(count)


### FIXED CODE ###

n = int(input())
d = {}
sum = 0

for i in range(n):
  s = list(input())
  s.sort()
  t = "".join(s)
  s.clear()
  if t in d:
    d[t] += 1
  else:
    d[t] = 1
    
for i in d:
  if d[i] > 1:
    sum += (d[i]*(d[i]-1))/2

print(int(sum))
### BUGGY CODE ###

n = int(input())
L = sorted(map(int,input().split()))
ans = 0

for i in range(n):
    for j in range(i+1,n):
        for k in range(j+1,n):
            a = L[i]
            b = L[j]
            c = L[k]
            
            if a < b + c:
                if b < c + a:
                    if c < a + b:
                        ans += 1
                    else:
                        break
                else:
                    break
            else:
                break
            
print(ans)


### FIXED CODE ###

import bisect
#二分探索をするライブラリ

n = int(input())
L = sorted(map(int,input().split()))
ans = 0

# c <= b <= a とする

for i in range(n-2):
    for j in range(i+1,n-1):
        a = L[n-1-i]
        b = L[n-1-j]
        
        if a-b < b:
            ans += (n-1-j) - bisect.bisect_left(L,a-b+1)
        
print(ans)
### BUGGY CODE ###

s = input()
pos = 0
cnt = 0
acnt = 0
if len(s) < 3:
    print(0)
else:
    while(True):
        if s[pos:pos+3] == "ABC":
            s = s[:pos-acnt] + "BCA"+ s[pos-acnt:pos] + s[pos+3:]
            pos += 2
            cnt += acnt+1
            # print(s, cnt)
        else:
            if s[pos] == "A":
                acnt += 1
            else:
                acnt = 0
            pos += 1
        if pos >= len(s)-2:
            break
    print(cnt)


### FIXED CODE ###

s = input()
pos = 0
cnt = 0
acnt = 0
if len(s) < 3:
    print(0)
else:
    while(True):
        if s[pos:pos+2] == "BC" and acnt > 0:
            pos += 2
            cnt += acnt
            # print(s, s[pos:pos+2], cnt, pos)
        else:
            if s[pos] == "A":
                acnt += 1
            else:
                acnt = 0
            pos += 1
        if pos >= len(s)-1:
            break
    print(cnt)
### BUGGY CODE ###

from collections import deque,Counter
n,*a = map(int,open(0).read().split())
c = Counter(a)
c = sorted(c.items())
a = deque(c)
p_set = set()
ans = 0
while a:
    f,count = a.popleft()
    if count == 1:
        for ff in p_set:
            if f%ff == 0: 
                break
        else:
            ans += 1
    p_set.add(f)
print(ans)


### FIXED CODE ###

_,*a = map(int,open(0).read().split())
a.sort()
ans = 0
#M = 30
M = 10**6 + 1
l = [0] * (M)
ans = 0
for i in range(len(a)):
    if l[a[i]] == 0:
        l[a[i]] = 2
        ans += 1
        for x in range(a[i]*2, M, a[i]):
            l[x] = 1
    elif l[a[i]] == 2:
        ans -= 1
        l[a[i]] -= 1
print(ans)
### BUGGY CODE ###

from collections import deque
n = int(input())
p = list(map(int,input().split()))
p_cutted = []
p_cutted = deque(p_cutted)
ans = 0
for i in range(n):
    p_cutted.append(p[i])
    if min(p_cutted) == p[i]:
        ans += 1
print(ans)


### FIXED CODE ###

from collections import deque
n = int(input())
p = list(map(int,input().split()))
p_cutted = []
p_cutted = deque(p_cutted)
min_p_cutted = p[0]
ans = 0
for i in range(n):
    p_cutted.append(p[i])
    if min_p_cutted >= p[i]:
        min_p_cutted = p[i]
        ans += 1
print(ans)
### BUGGY CODE ###

[x,y]=list(map(int,input().split()))
if ((x%3)+(y%3))%3!=0:
	print(0)
else:
	dansu=int((x+y)/3)
	r=y-dansu
	if r>dansu-r:
		r=dansu-r
	mod=1000000007
	d=1
	rr=1
	nr=1
	for i in range(1,dansu+1):
		d=d*(i%mod)
	for i in range(1,r+1):
		rr=rr*(i%mod)
	for i in range(1,dansu-r+1):
		nr=nr*(i%mod)
	
	kotae=int((d%mod)*pow(rr,mod-2,mod)*pow(nr,mod-2,mod))
	kotae=int(kotae%(10**9+7))
	
	print(kotae)

### FIXED CODE ###

[x,y]=list(map(int,input().split()))
if ((x%3)+(y%3))%3!=0:
	print(0)
else:
	n=int((x+y)/3)
	r=y-n
	if r<0 or r>n:
		print(0)
	else:
		if r>n-r:
			r=n-r
		mod=1000000007
		kaijo=[1]
		for i in range(1,n+1):
			kaijo.append(kaijo[-1]*i%mod) #これで、kaijo[i]=i!となる。
		gyakugen=[pow(kaijo[n-r],mod-2,mod)]
		for i in reversed(range(1,n-r+1)):
			gyakugen.append(gyakugen[-1]*i%mod) #これで、gyakugen[i]=n-r-iの逆元となる
		kotae=kaijo[n]*gyakugen[0]*gyakugen[n-2*r]%mod

		print(kotae)
### BUGGY CODE ###

n = int(input())
s = input()

from collections import Counter

ct = Counter(s)
res = ct['R'] * ct['G'] * ct['B']

for ni,i in enumerate(s[:-2]):
    lst3 = ['R','G','B']
    lst3.remove(i)
    for nj in range(ni+1,n):
        nk = nj + (nj - ni)
        if nk < n:
            if set(lst3) == set([s[nj],s[nk]]):
                res -= 1
        else:
            break

print(res)

### FIXED CODE ###

n = int(input())
s = input()

res = s.count('R') * s.count('G') * s.count('B')

for i in range(n):
    for j in range(i+1, n-1):
        k = j + (j - i)
        if k < n:
            if s[i]!=s[j] and s[j]!=s[k] and s[k]!=s[i]:
                res -= 1
        else:
            break

print(res)
### BUGGY CODE ###

import sys


def read():
    return sys.stdin.buffer.readline().rstrip()


def main():
    n, q = map(int, read().split())
    a = [int(i) for i in read().split()]
    for _ in range(q):
        query = [int(i) for i in read().split()]
        if query[0] == 0:
            a[query[1]] += query[2]
        else:
            print(sum(a[query[1]:query[2]]))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys


def read():
    return sys.stdin.buffer.readline().rstrip()


class FenwickTree:
    def __init__(self, n):
        self._n = n
        self._a = [0] * n

    def add(self, i, x):
        i += 1
        while i <= self._n:
            self._a[i - 1] += x
            i += i & -i

    def sum(self, l, r):
        return self._sum(r) - self._sum(l)

    def _sum(self, r):
        s = 0
        while r > 0:
            s += self._a[r - 1]
            r -= r & -r
        return s


def main():
    n, q = map(int, read().split())
    fw = FenwickTree(n)
    for i, ai in enumerate(map(int, read().split())):
        fw.add(i, ai)
    for _ in range(q):
        query = [int(i) for i in read().split()]
        if query[0] == 0:
            fw.add(query[1], query[2])
        else:
            print(fw.sum(query[1], query[2]))


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

import math

def readInt():
	return int(input())

def readInts():
	return list(map(int, input().split()))

def readChars():
	return input().split()

s = input()[::-1]

ai = [0]*len(s)
si = [0]*len(s)

p = 2019

for i, j in enumerate(s):
	ai[i] = (int(j)*pow(10,i,p))%p
	si[i] = sum(ai[:i+1])%p
countarr = [0]*2019
for i in si:
	countarr[i]+=1

res = countarr[0]
for i in range(p):
	c = countarr[i]
	res += c*(c-1)//2

print(res)

### FIXED CODE ###

import math

def readInt():
	return int(input())

def readInts():
	return list(map(int, input().split()))

def readChars():
	return input().split()

s = reversed(input())

ai = 0
si = 0

p = 2019
countarr = [0]*2019

for i, j in enumerate(s):
	ai = (int(j)*pow(10,i,p))%p
	si = (si+ai)%p
	countarr[si]+=1

res = countarr[0]
for i in range(p):
	c = countarr[i]
	res += c*(c-1)//2

print(res)
### BUGGY CODE ###

# 2020/05/03
# AtCoder Beginner Contest 166 - D

# Input
x = int(input())

# Calc
eflg = False
for a in range(10**8):
    wk_a = a ** 5
    b = 0
    sav = 10 ** 10
    for b in range(10**8):
        val_1 = wk_a - (b ** 5)
        val_2 = wk_a - (-b ** 5)

        if val_1 == x:
            ans1 = a
            ans2 = b
            eflg = True
            break

        if val_2 == x:
            ans1 = a
            ans2 = -b
            eflg = True
            break
        
        sav = abs(val_2) - x

        if sav > x:
            break

    if eflg == True:
        break

# Output
print(ans1, ans2)


### FIXED CODE ###

# 2020/05/03
# AtCoder Beginner Contest 166 - D

# Input
x = int(input())

# Calc
eflg = False
for a in range(200):
    wk_a = a ** 5
    for b in range(200):
        if wk_a - (b ** 5) == x:
            ans1 = a
            ans2 = b
            eflg = True
            break

        if wk_a - (-b ** 5) == x:
            ans1 = a
            ans2 = -b
            eflg = True
            break

    if eflg == True:
        break

# Output
print(ans1, ans2)
### BUGGY CODE ###

import queue

N,M = map(int, input().split())
G = [[] for i in range(3*N+1)]

for i in range(M):
  u,v = map(int, input().split())
  G[u].append(v+N)
  G[u+N].append(v+2*N)
  G[u+2*N].append(v)
S,T = map(int, input().split())

def bfs(s):
  que = queue.Queue()
  que.put(s)
  d = [-1 for _ in range(3*N+1)]
  d[s] = 0

  while not que.empty():

    p = que.get()
    if (T == p):
      return d[p]

    for pp in G[p]:
      if d[pp] == -1:
        que.put(pp)
        d[pp] = d[p]+1

  return -1

ans = bfs(S)
if (-1 == ans):
  print(-1)
else:
  print(ans//3)


### FIXED CODE ###

import collections

N,M = map(int, input().split())
G = [[] for i in range(3*N+1)]

for i in range(M):
  u,v = map(int, input().split())
  G[u].append(v+N)
  G[u+N].append(v+2*N)
  G[u+2*N].append(v)
S,T = map(int, input().split())

def bfs(s):
  que = collections.deque()
  que.append(s)
  d = [-1 for _ in range(3*N+1)]
  d[s] = 0

  while (0 < len(que)):

    p = que.popleft()
    if (T == p):
      return d[p]

    for pp in G[p]:
      if d[pp] == -1:
        que.append(pp)
        d[pp] = d[p]+1

  return -1

ans = bfs(S)
if (-1 == ans):
  print(-1)
else:
  print(ans//3)
### BUGGY CODE ###

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

for i in range(N):
  ans *= A[i]
  
if ans > 10**18:
  print("-1")
else:
  print(ans)

### FIXED CODE ###

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

if 0 in A:
  print(0)
  exit(0)

for i in range(N):
  ans *= A[i]
  if ans > 10**18:
    print("-1")
    exit(0)

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

import sys
from collections import deque

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

h,w = nm()
g = [list(map(lambda s:s=='#', list(input()))) for _ in range(h)]
dp = [[h*w]*w for _ in range(h)]
q = deque()
q.append((0,g[0][0]))
while q:
    v,d = q.popleft()
    if v == h*w-1: print(int(d)); break
    y,x = divmod(v,w)
    if dp[y][x] < d: continue
    dp[y][x] = d
    if y < h-1:
        if g[y+1][x] < g[y][x]:
            q.append((v+w, d+1))
        else:
            q.appendleft((v+w, d))
    if x < w-1:
        if g[y][x+1] < g[y][x]:
            q.append((v+1, d+1))
        else:
            q.appendleft((v+1, d))


### FIXED CODE ###

import sys

stdinr = sys.stdin.readline

ns = lambda: stdinr().rstrip()
ni = lambda: int(stdinr().rstrip())
nm = lambda: map(int, stdinr().split())
nl = lambda: list(map(int, stdinr().split()))

h,w = nm()
g = [list(map(lambda s:s=='#', list(input()))) for _ in range(h)]
dp = [[h*w]*w for _ in range(h)]
dp[0][0] = g[0][0]
for i in range(h):
    for j in range(w):
        if i < h-1:
            d = dp[i][j] + (g[i][j] < g[i+1][j])
            if dp[i+1][j] > d: dp[i+1][j] = d
        if j < w-1:
            d = dp[i][j] + (g[i][j] < g[i][j+1])
            if dp[i][j+1] > d: dp[i][j+1] = d
print(dp[-1][-1])
### BUGGY CODE ###

def digitSum(n):
    # 数値を文字列に変換
    s = str(n)
    # １文字ずつ数値化し配列にする。
    array = list(map(int, s))
    # 合計値を返す
    return sum(array)
S = input()
Scount = 0
for i in range(len(S)-1):
    for j in range(1,len(S)):
        if (i+j)<=len(S):
            part_S = S[i:i+j]
            num = int(part_S)
            if num % 673 == 0:
                num = num//673
                sum3 = digitSum(num)
                while sum3 != digitSum(sum3):
                    sum3 = digitSum(sum3)
                if sum3 == 3 or sum3 == 6 or sum3 ==9:
                    Scount += 1
print(Scount)

### FIXED CODE ###

S = input()
from collections import defaultdict
d = defaultdict(int)
before = 0
for i in range(1,len(S)+1):
    now = (int(S[-i])*pow(10,i,2019)+before) % 2019
    d[now] += 1
    before = now
d[0] += 1
ans = 0
for i in d.values():
    ans += i*(i-1)//2
print(ans)
### BUGGY CODE ###

n = int(input())
count = 0
for i in range(1,n+1):
    i_str = str(i)
    three = i_str.count('3')
    five = i_str.count('5')
    seven = i_str.count('7')
    sum_number = three + five + seven
    if len(i_str) == sum_number and three>0 and five>0 and seven>0:
        count += 1
print(count)


### FIXED CODE ###

n = int(input())
ans = []
count = 0
def dfs(s):

    if int(s)>n:
        return 0
    ans.append(s)
    for c in '753':
        dfs(s+c)
dfs('0')
for i in ans:
    if all(i.count(j)>0 for j in '753'):
        count += 1
print(count)