Harryxun/stf_run huggingface dataset:
w, h, n = map(int,input().split())

#とりうるx,yの範囲
y_min = 0
y_max = h

x_min = 0
x_max = w

for i in range(n):
  x, y, a = map(int,input().split())

  if a == 1:
    x_min = max(x_min, x)

  if a == 2:
    x_max = min(x_max, x)

  if a == 3:
    y_min = max(y_min, y)

  if a == 4:
    y_max = min(y_max, y)

white = (y_max - y_min) * (x_max - x_min)
if (y_max - y_min)>=0 and (x_max - x_min)>=0:
  print(max(white, 0))
else:
  print(0)

### FIXED CODE ###

s=input()

ans=0
bef=s[0]
for i in s[1:]:
  if bef!=i:
    ans+=1
  bef=i
print(ans)
N,M=map(int,input().split())
A=[]
for i in range(M):
    A.append(list(map(int,input().split())))
P=list(map(int,input().split()))
ans=0
for i in range(2**N,2**(N+1)):
        B=bin(i)
        count=0
        for j in range(M):
            tet=0
            for l in range(A[j][0]):
                tet+=int(B[A[j][l+1]+2])
            if tet//2==P[j]:
                  count+=1
        if count==M:
            ans+=1
print(ans)
N,M=map(int,input().split())
A=[]
for i in range(M):
    A.append(list(map(int,input().split())))
P=list(map(int,input().split()))
ans=0
for i in range(2**N,2**(N+1)):
        B=bin(i)
        count=0
        for j in range(M):
            tet=0
            for l in range(A[j][0]):
                tet+=int(B[A[j][l+1]+2])
            if tet%2==P[j]:
                  count+=1
        if count==M:
            ans+=1
print(ans)


### FIXED CODE ###

N,M=map(int,input().split())
A=[]
for i in range(M):
    A.append(list(map(int,input().split())))
P=list(map(int,input().split()))
ans=0
for i in range(2**N,2**(N+1)):
        B=bin(i)
        count=0
        for j in range(M):
            tet=0
            for l in range(A[j][0]):
                tet+=int(B[A[j][l+1]+2])
            if tet%2==P[j]:
                  count+=1
        if count==M:
            ans+=1
print(ans)
import math
import heapq
import sys
from collections import Counter

#N,K=map(int, input[0].split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
#x=list(map(int, input[1].split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき

N=int(input[0])
a=list(map(int,input[1].split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき

cnt=0
for i in range(len(a)-1):
    if a[i]==a[i+1]:
        a[i+1]=-1
        cnt+=1
        #print(a)


print(cnt)


### FIXED CODE ###

import math
import heapq
import sys
from collections import Counter

#N,K=map(int, input[0].split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
#x=list(map(int, input[1].split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき

N=int(input())
a=list(map(int,input().split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき

cnt=0
for i in range(len(a)-1):
    if a[i]==a[i+1]:
        a[i+1]=-1
        cnt+=1
        #print(a)


print(cnt)
import sys
a=[0,0]+[1]*10**6
for i in range(999):
 if a[i]:
  for j in range(i*2,m,i):a[j]=0
for e in sys.stdin:print(sum(a[:int(e)+1]))


### FIXED CODE ###

import sys
m=500000;a=[1]*m
for i in range(3,999,2):
 if a[i//2]:a[i*i//2::i]=[0]*len(a[i*i//2::i])
p=[]
for i in range(m*2):p+=[i-1 if i<4 else p[i-1]+[0,a[i//2]][i%2]]
for e in sys.stdin:print(p[int(e)])
A, B = map(int, input().split())
print(int(A*B/math.gcd(A, B)))

### FIXED CODE ###

A, B = map(int, input().split())
min = min(A, B)
max = max(A, B)

cnt = 1
while True:
    if max * cnt % min == 0:
        print(max * cnt)
        exit()
    cnt += 1
r=int(input)
print(r*r)

### FIXED CODE ###

r=int(input())
print(r*r)
#!/usr/local/bin/python3
# coding: utf-8
n = input()
hairu = input()
kita = hairu.split(" ")
a = []
int seki = 1
for c in kita:
    a.append(c)
try:
    for c in a:
        c = c * int(c)
    if c > 10**18:
        print("-1")
    else:
        print(c)
except:
    print("-1")

### FIXED CODE ###

#!/usr/local/bin/python3
# coding: utf-8
n = input()
hairu = input()
kita = hairu.split(" ")
seki = 1

for c in kita:
    if c == "0":
        kita[0] = "0"

for c in kita:
    seki = seki * int(c)
    if seki > 10**18:
        break

if seki > 10**18:
    print("-1")
else:
    print(seki)
s = input().split()
s = [i for i in s]

if s[2]==s[3] and s[4]==s[5]:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

s = input()

if s[2]==s[3] and s[4]==s[5]:
  print('Yes')
else:
  print('No')
if X >= 30:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

if int(input()) >= 30:
    print('Yes')
else:
    print('No')
# -*- coding: utf-8 -*-

def parse_input():

    # 出力
    params = []
    nm = input().split(" ")
    n = int(nm[0])
    m = int(nm[1])
    params.append(n)
    params.append(m)

    for i in range(0, n):
        params.append(input())   

    rows = []
    for line in lines:
        rows.append([int(e) for e in line.split(" ")])

    return (n, m, rows)

def solve(n, m, rows):

    result = []
    for k in range(1, m + 1):
        tmp = []
        for i in range(0, n):
#            print(rows[i])
            r = rows[i]
#            print(r[1:r[0] + 1])
            if k in r[1:r[0]+1]:
               tmp.append(i+1)
        if len(tmp) == n:
            result.append(k)

    return str(len(result))

def main():

    print(solve(parse_input()))

if __name__ == '__main__':

    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-

def solve(n, m, *lines):

    
    rows = []
    for line in lines:
        rows.append([int(e) for e in line.split(" ")])

    # print(n)
    # print(m)
    # print(rows)

    result = []
    for k in range(1, m + 1):
        tmp = []
        for i in range(0, n):
#            print(rows[i])
            r = rows[i]
#            print(r[1:r[0] + 1])
            if k in r[1:r[0]+1]:
               tmp.append(i+1)
        if len(tmp) == n:
            result.append(k)

    return str(len(result))

def main():
    # 出力
    params = []
    nm = input().split(" ")
    n = int(nm[0])
    m = int(nm[1])
    params.append(n)
    params.append(m)

    for i in range(0, n):
        params.append(input())   
    print(solve(*params))

if __name__ == '__main__':

    main()
# - coding : utf-8 -*-
 
n, m = input().split()
xs_str = input().split()
xs = list(map(int, xs_str))
sortted(xs)
 
ys = []
for i in range(int(m) - 1):
    ys.append(abs(xs[i+1] - xs[i]))
sorted(ys)
 
out = sum(ys[0:-(int(n)-1)])
print(out)

### FIXED CODE ###

# - coding : utf-8 -*-
 
n, m = list(map(int, input().split()))
xs_str = input().split()
xs = list(map(int, xs_str))
xs.sort()
 
ys = []
for x1, x2 in zip(xs[0:-1], xs[1:]):
    ys.append(abs(x2 - x1))
ys.sort()

for i in range(n - 1):
    if ys == []:
        break
    else:
        ys.pop()
print(sum(ys))
def main():
    import sys
    input = sys.stdin.readline
    
    a,b = map(int,input().split())

    def make_two_divisors(a,b):
        lower_divisors,upper_divisors = [],[]
        prime_li = [True]*(max(a,b)+1)
        i = 1
        while i*i<=max(a,b):
            if prime_li[i]:
                if a%i==0 and b%i==0:
                    lower_divisors.append(i)
                    #if i != max(a,b)//i and a%(max(a,b)//i)==0 and b%(max(a,b)//i)==0:
                    #    upper_divisors.append(b//i)
                    if i!=1:
                        for j in range(i+i,max(a,b)+1,i):
                            prime_li[j]=False 
            i+=1
        return lower_divisors
    print(len(make_two_divisors(a,b)))

if __name__=='__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    
    a,b = map(int,input().split())

    #gcd(a,b)の素因数分解
    import math
    gcd = math.gcd(a,b)

    p = []
    for i in range(2,int(math.sqrt(gcd))+1):
        while gcd % i == 0:
            gcd /= i
            p.append(i)
            
    p.append(int(gcd))
    p.append(1)
    print(len(list(set(p))))

if __name__=='__main__':
    main()
def memoize(f):
    cache={}
    def helper(*args):
        if args not in cache:
            cache[args] = f(*args)
        return cache[args]
    return helper

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

@memoize
def f(n):
    if n==1:
        return 0
    elif n==2:
        return abs(h[1]-h[0])
    elif n==3:
        return abs(h[2]-h[0])
    else:
        a = f(n-1)+abs(h[n-1]-h[n-2])
        b = f(n-2)+abs(h[n-1]-h[n-3])
        return min(a,b)

print(f(N))


### FIXED CODE ###

def memoize(f):
    cache={}
    def helper(*args):
        if args not in cache:
            cache[args] = f(*args)
        return cache[args]
    return helper

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

import sys
sys.setrecursionlimit(1000000)

@memoize
def f(n):
    if n==1:
        return 0
    elif n==2:
        return abs(h[1]-h[0])
    elif n==3:
        return abs(h[2]-h[0])
    else:
        return min(f(n-1)+abs(h[n-1]-h[n-2]),f(n-2)+abs(h[n-1]-h[n-3]))

print(f(N))
#=map(int,input().strip().split())
#=int(input().strip())
#=list(map(int,input().strip().split()))
S = input()

subs = []
tmp = []
for s in S:
    if "A" == s or "C" == s or "G"== s or "T" == s:
        tmp.append(s)
    else:
        subs.append(tmp)
        tmp = []
rs = sorted(subs,key=lambda x: len(x),reverse=True)
print(len(rs[0]))



### FIXED CODE ###

#N,Q =map(int,input().strip().split())
#=int(input().strip())
#=list(map(int,input().strip().split()))
S = input()

#for i in range(0,Q):


subs = []
tmp = []
for s in S:
    if "A" == s or "C" == s or "G"== s or "T" == s:
        tmp.append(s)
    else:
        subs.append(tmp)
        tmp = []

subs.append(tmp)
if len(subs) == 0:
    print("0")
    exit()

rs = sorted(subs,key=lambda x: len(x),reverse=True)
print(len(rs[0]))
A,B=map(int,input().split())

if ( A < 10 and B < 10 ):
  print ( A * B )
else:
  print ( -1 ):

### FIXED CODE ###

A,B=map(int,input().split())
 
if ( A < 10 and B < 10 ):
  print ( A * B )
else:
  print ( -1 )
n, m = map(int, input().split())
edges = [[] for _ in range(n)]
revEdges = [[] for _ in range(n)]
for _ in range(n - 1 + m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append(b)
    revEdges[b].append(a)

visited = [False] * n
lst = []
def search(x):
    if not visited[x]:
        visited[x] = True
        for to in edges[x]:
            search(to)
        lst.append(x)

for i in range(n):
    search(i)
lst.reverse()
dic = {}
for i in range(n):
    dic[lst[i]] = i

parent = [-1] * n
for i in lst:
    if not revEdges[i]:
        continue
    maxScore = n
    index = n
    for fr in revEdges[i]:
        if maxScore <= dic[fr]:
            maxScore = dic[fr]
            index = fr
    parent[i] = fr

for i in range(n):
    print(parent[i] + 1)

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

n, m = map(int, input().split())
edges = [[] for _ in range(n)]
revEdges = [[] for _ in range(n)]
for _ in range(n - 1 + m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append(b)
    revEdges[b].append(a)

visited = [False] * n
lst = []
def search(x):
    if not visited[x]:
        visited[x] = True
        for to in edges[x]:
            search(to)
        lst.append(x)

for i in range(n):
    search(i)
lst.reverse()
dic = {}
for i in range(n):
    dic[lst[i]] = i

parent = [-1] * n
for i in lst:
    if not revEdges[i]:
        continue
    maxScore = -1
    index = -1
    for fr in revEdges[i]:
        if maxScore <= dic[fr]:
            maxScore = dic[fr]
            index = fr
    parent[i] = index

for i in range(n):
    print(parent[i] + 1)
import math
def lcm_base(x, y):
    return int((x * y) / math.gcd(x, y))
def lcm_list(numbers):
    answer=numbers[0]
    for number in numbers:
        answer=lcm_base(answer,number)
    return answer
nm=list(map(int, input().split()))
a=list(map(int, input().split()))
n=nm[0]
m=nm[1]
b=0
while a[0]%2==0:
    for i in range(len(a)):
        if a[i]%2==0:
            a[i]=int(a[i]/2)
        else:
            b=1
            break
if b==1:
    print(0)
else:
    amc=lcm_list(a)
    print(int((m+amc)/(2*amc)))



### FIXED CODE ###

import fractions
from functools import reduce
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
nm=list(map(int, input().split()))
a=list(map(int, input().split()))
n=nm[0]
m=nm[1]
b=0
c=a[0]
dnum=0
while c%2==0:
    dnum+=1
    c=c//2
for i in range(len(a)):
    c=a[i]
    dnum1=0
    while c%2==0:
        dnum1+=1
        c=c//2
    #print(dnum)
    if dnum1!=dnum:
        b=1
        break

#print(a)
if b==1:
    print(0)
else:
    for i in range(len(a)):
        a[i]=a[i]//2
    #print(a)
    amc=lcm_list(a)
    #print(amc)
    # version3.5にてgcdがfractionsからmathに移動した
    print(int((m+amc)/(2*amc)))
import sys
sys.setrecursionlimit(10000)
n = int(input())
X = input()
pc = X.count('1')
nx = int(X, 2)

dp = [-1] * ((2*10**5)+1)
pcs = [-1] * ((2*10**5)+1)
pcs[0] = 0
pcs[1] = 1
pcs[2] = 1
dp[0] = 0
def f(n):
    if dp[n] >= 0:
        return dp[n]
    if pcs[n] >= 0:
        pc = pcs[n]
    else:
        pc = bin(n).count('1')
        pcs[n] = pc
    nn = n%pc
    d = f(nn)+1
    dp[n] = d
    return d

tmp = pow(2, n)
for i in range(n-1, -1, -1):
    # ibit目を反転させる # つまりi**2を引く
    tmp //= 2
    if (nx>>i)&1:
        r = (nx-tmp)%(pc-1)
    else:
        r = (nx+tmp)%(pc+1)

    if r > 0:
        print(f(r) + 1)
    else:
        print(1)

### FIXED CODE ###

n = int(input())
X = input()
pc = X.count('1')
nx = int(X, 2)

def f(n):
    c = 0
    while n > 0:
        n %= bin(n).count('1')
        c += 1
    return c

nxp = nx%(pc+1)
nxm = nx%(pc-1) if pc > 1 else 0
for i in range(n-1, -1, -1):
    if (nx>>i)&1:
        # 2**iを引く
        if pc-1 == 0:
            print(0)
            continue
        p = pow(2, i, pc-1)
        r = (nxm-p)%(pc-1)
    else:
        # 2**iを足す
        r = (nxp+pow(2, i, pc+1))%(pc+1)

    print(f(r) + 1)
if 0 <= X - A <= B:
    print('YES')
else:
    print('NO')

### FIXED CODE ###

A, B, X = map(int, input().split())

if 0 <= X - A <= B:
    print('YES')
else:
    print('NO')
t, x = map(int input().split())

print(t / x)

### FIXED CODE ###

t, x = map(int, input().split())

print(t / x)
K = int(input())
S = str(input())

if len(S) <= K:
    print(S)
else:

    print(S[:K+1]+...)

### FIXED CODE ###

K = int(input())
S = str(input())

if len(S) <= K:
    print(S)
else:
    print(S[:K] + "...")
print(int(input())+1)

### FIXED CODE ###

n,k=map(int,input().split())
print(n-k+1)
def 解():
    sS = input().rstrip()
    dsS = set()
    for s in sS:
        if s not in dsS:
            dsS.add(s)
    iK = int(input())
    iL = len(sS)
    iC = 0
    for s in sorted(list(dsS)):
        sDic = set()
        indexes = []
        for i in range(iL):
            if sS[i] == s:
                indexes.append(i)
        if iK < iL // len(indexes) + 1:
            for i in indexes:
                for j in range(1,iK+1):
                    if i+j <= iL:
                        sDic.add(sS[i:i+j])
            aS = sorted(list(sDic))
            print(aS[iK -1])
            exit()
        for i in indexes:
            for j in range(1,iL -i+1):
                sDic.add(sS[i:i+j])
        aS = sorted(list(sDic))
        iLS = len(aS)
        if iC + iLS < iK:
            iC += iLS
            continue
        else:
            print(aS[iK -iC-1])
            exit()
解()



### FIXED CODE ###

def 解():
    sS = input().rstrip()
    dsS = set()
    for s in sS:
        if s not in dsS:
            dsS.add(s)
    iK = int(input())
    iL = len(sS)
    iC = 0
    for s in sorted(list(dsS)):
        sDic = set()
        indexes = []
        for i in range(iL):
            if sS[i] == s :
                if i != 0 and i != iL-1:
                    if sS[i-1] != s or sS[i+1] != s:
                        indexes.append(i)
                else:
                    indexes.append(i)
        if iK < iL :
            for i in indexes:
                for j in range(1,iK+1):
                    if i+j <= iL:
                        sDic.add(sS[i:i+j])
            aS = sorted(list(sDic))
            if iK <= len(aS) :
                print(aS[iK - iC -1])
                exit()
            else:
                iC += len(aS)
        else:
            for i in indexes:
                for j in range(1,iL -i+1):
                    sDic.add(sS[i:i+j])
            aS = sorted(list(sDic))
            iLS = len(aS)
            if iC + iLS < iK:
                iC += iLS
                continue
            else:
                print(aS[iK -iC-1])
                exit()
解()
import math


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


mi_stamina = math.inf
for i in range(-1000, 1000):
    def _distance(x):
        return (x-i)**2
    double_list = list(map(lambda x: _distance(x), x_list))
    stamina = sum(double_list)
    if mi_stamina > stamina:
        mi_stamina = stamina

print(mi_stamina)

### FIXED CODE ###

import math


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


mi_stamina = 1000000000
for i in range(-1000, 1000):
    def _distance(x):
        return (x-i)**2
    double_list = list(map(_distance, x_list))
    stamina = sum(double_list)
    if mi_stamina > stamina:
        mi_stamina = stamina

print(mi_stamina)
from math import factorial
import sys
input = sys.stdin.readline
def ncr(n,r):
 if n <= 1:
  return 0
 else:
  return  factorial(n) / factorial(r) / factorial(n - r)

n= int(input())
a = list(int(i) for i in input().split())
s = [0]
for i in range(n):
  s.append(s[i]+a[i])
s = sorted(s,reverse =True)
ans = 0
tmp = 1

for i in range(n+1):
  if s[i-1] == s[i]:
   tmp += 1
  else:
   ans += ncr(tmp,2)
   tmp = 1
ans += ncr(tmp,2)
print(int(ans))


### FIXED CODE ###

from math import factorial
import sys
input = sys.stdin.readline
def ncr(n):
 if n <= 1:
  return 0
 elif n == 2:
  return 1
 else:
  return  (factorial(n) // 2) // factorial(n - 2)

n= int(input())
a = list(int(i) for i in input().split())
s = [0]
for i in range(n):
  s.append(s[i]+a[i])
s = sorted(s,reverse =True)
ans = 0
tmp = 1
for i in range(len(s)-1):
  if s[i] == s[i+1]:
   tmp += 1
  else:
   ans += ncr(tmp)
   tmp = 1
ans += ncr(tmp)
print(ans)
a,b = input().split()
print("error" if a+b>=10 else a+b)

### FIXED CODE ###

a,b = map(int,input().split())
print("error" if a+b>=10 else a+b)
L = int(input())
print((L/3)**3

### FIXED CODE ###

L = float(input())
print((L/3)**3)
dp = [[100000000]*(10000*2)]*(N+1)
dp[0][0] = 0

for i in range(0, N):
    for h in range(0, H+1):
        dp[i+1][h] = min(dp[i+1][h], dp[i][h])
        dp[i+1][min(h+AB[i][0], H)] = min(dp[i+1][min(h+AB[i][0], H)], dp[i+1][h]+AB[i][1])

ans = {}
for i in range(N):
    ans[i] = dp[i][H]
print(min(ans.values()))

### FIXED CODE ###

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

    dp = [[100000000]*(10000*2)]*(N+1)
    dp[0][0] = 0

    for i in range(0, N):
        for h in range(0, H+1):
            dp[i+1][h] = min(dp[i+1][h], dp[i][h])
            dp[i+1][min(h+AB[i][0], H)] = min(dp[i+1][min(h+AB[i][0], H)], dp[i+1][h]+AB[i][1])

    ans = {}
    for i in range(N):
        ans[i] = dp[i][H]
    print(min(ans.values()))
    
if __name__ == "__main__":
    main()
a,b = map(int, input().split())
tap = a
while tap < b:
  tap = tap + a-1
return (i + 1)


### FIXED CODE ###

a,b = map(int, input().split())
tap = a
i = 0
if b != 1:
	while tap < b:
		tap = tap + a-1
		i += 1
	print(i + 1)
else:
  	print(0)
N, K = map(int, input().split())
A = list(map(int, input().split()))
Kn = [0]*N
l = []
p = 0
i = 1
while True:
    Kn[p] = 1
    # print(p)
    if Kn[A[p]-1] == 1:
        break
    elif i == K:
        print(p+1)
    l.append(A[p])
    p = A[p]-1
    i += 1
if N % len(l) == 0:
    print(l[len(l)-1])
else:
    print(l[N % len(l)-1])


### FIXED CODE ###

from collections import Counter
n, k = map(int, input().split())
A = list(map(int, input().split()))
C = Counter([])
X, Y = [], []
m = 0
for _ in range(n):
    a = A[m]-1
    C[m] += 1
    X.append(m)
    if C[a] != 0:
        Y = X[X.index(a):]
        X = X[:X.index(a)]
        break
    m = a
# print(X,Y)
x = len(X)
y = len(Y)
if k <= x-1:
    print(X[k]+1)
else:
    k -= x
    print(Y[k-(k//y)*y]+1)
from collections import defaultdict
import itertools
import math

def dfs(vum,s,visit,depth):
    # print('first')
    # print(s,depth,visit)
    if visit[s-1] >= 0:
        return visit
    visit[s-1] = depth
    # print(vum[s])
    for u in vum[s]:
        # print('now', str(u))
        if visit[u-1] >= 0:
            # print('skip', str(u))
            if visit[u-1] > depth:
                visit[u-1] = depth
                # print('update', str(u))
            continue
        s = u
        depth += 1
        visit = dfs(vum,s,visit,depth)
    return visit


def main():
    N,M = [int(x) for x in input().split()]
    vum = defaultdict(list)
    for i in range(M):
        a,b = [int(x) for x in input().split()]
        vum[a].append(b)
        vum[b].append(a)
        
    s = 1 # 現在地 (初期値はゴールを設定)
    visit = [-1]*N # 訪問リスト
    depth = 0 # 移動数(深さ)
    visit = dfs(vum,s,visit,depth)
    if -1 in visit:
        print('No')
        return
    else:
        print('Yes')
    for v in visit[1:]:
        print(v)

if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import defaultdict
import queue

def main():
    N,M = [int(x) for x in input().split()]
    vum = defaultdict(list)
    for i in range(M):
        a,b = [int(x) for x in input().split()]
        vum[a].append(b)
        vum[b].append(a)
        
    ### bfs ###
    q = queue.Queue()
    F = [-1]*N # 道標の先の部屋
    s = 1 # 始点
    step = 0
    while True:
        # print('s',str(s))
        for v in vum[s]:
            # print('v',str(v))
            if F[v-1] < 0:
                q.put(v)
                F[v-1] = s
        if q.empty():
            break
        # print(list(q.queue),V)
        s = q.get()

    if -1 in F[1:]:
        print('No')
    else:
        print('Yes')
        for d in F[1:]:
            print(d)

if __name__ == '__main__':
    main()
from collections import deque
from itertools import chain

ADS = [(0, 1), (1, 0), (-1, 0), (0, -1)]

h, w = map(int, input().split(" "))
s = [list(input()) for _ in range(h)]

l = [[None for _ in range(w)] for _ in range(h)]
l[0][0] = 0

q = deque([(0, 0)])
while q:
	this_x, this_y = q.popleft()
	this_num = l[this_y][this_x]
	if (this_x, this_y) == (w, h):
		break

	for ad_x, ad_y in ADS:
		x, y = this_x+ad_x, this_y+ad_y
		if not (0 <= x < w and 0 <= y < h):
			continue
		
		square = s[y][x]
		if square == "#":
			continue

		num = l[y][x]
		if num != None:
			continue
		l[y][x] = this_num + 1

		q.append((x, y))

print(sum(s_i.count(".") for s_i in s) - l[h-1][w-1] - 1)


### FIXED CODE ###

from collections import deque
from itertools import chain
ads = [(0, 1), (1, 0), (0, -1), (-1, 0)]

h, w = map(int, input().split(" "))
s = [list(input()) for _ in range(h)]

def find_shortest(m):
	q = deque([(0, 0)])
	i = 0
	while q:
		for j in range(len(q)):
			this_x, this_y = q.popleft()
			# this_square = m[this_y][this_x]
			if (this_x, this_y) == (w-1, h-1):
				return i
			m[this_y][this_x] = i

			for ad_x, ad_y in ads:
				x, y = this_x+ad_x, this_y+ad_y
				if not (0 <= x < w and 0 <= y < h):
					continue
				
				square = m[y][x]
				if square == "#" or type(square) == int:
					continue
					
				q.append((x, y))
				m[y][x] = "#"
		i += 1
	return None


white_num = "".join(chain(*s)).count(".")
shortest_lenght = find_shortest(s)
if shortest_lenght:
	print(white_num - 1 - shortest_lenght)
else:
	print(-1)
# しろます - 1 - 最短ルートの長さ