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

import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


n = 60
N = read_a_int()
A = read_ints()


def ret_binary(a: int):  # 逆順で返すことに注意
    tmp = bin(a)[2:]
    ret_r = [0] * n
    for i, t in enumerate(tmp[::-1]):
        ret_r[i] = int(t)
    return ret_r


def calc_sum(a, n_1_ls, n_1_max):
    '''
    aはxorしてから和を取りたい数
    n_1_lsは各桁の1の数
    n_1_maxは最大1は何個あり得るか
    '''
    a_binary = ret_binary(a)
    ret = 0
    for i, (aa, n_1) in enumerate(zip(a_binary, n_1_ls)):
        if aa == 0:
            ret += (((2**i) % MOD) * (n_1 % MOD)) % MOD
        else:
            ret += (((2**i) % MOD) * ((n_1_max - n_1) % MOD)) % MOD
    return ret


def add_koko(lsa, lsb):
    return [a + b for a, b in zip(lsa, lsb)]


MOD = 10**9 + 7

n_1_max = 0
n_1_ls = [0] * n
ans = 0
a_pre = A[N - 1]
for i in range(N - 2, -1, -1):
    a = A[i]
    n_1_ls = add_koko(n_1_ls, ret_binary(a_pre))
    n_1_max += 1
    tmp = calc_sum(a, n_1_ls, n_1_max)
    ans += tmp
    ans %= MOD
    a_pre = a

print(ans)


### FIXED CODE ###

import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


n = 60
N = read_a_int()
A = read_ints()


def ret_binary(a: int):  # 逆順で返すことに注意
    ret_r = [0] * n
    for i in range(n):
        bit = a % 2
        a = a // 2
        ret_r[i] = bit
    return ret_r


MOD = 10**9 + 7

n_1_max = 0
n_1_ls = [0] * n
ans = 0
for a in A:
    tmp = ret_binary(a)
    for i in range(n):
        n_1_ls[i] += tmp[i]


for i, n_1 in enumerate(n_1_ls):
    num_sonoketa = n_1 * (N - n_1)
    ans += (((2**i) % MOD) * num_sonoketa)
    ans %= MOD
print(ans)
### BUGGY CODE ###

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

list_result = []
# どこを選ぶか
for i in range(n):
    
    result = 0
    # その条件で何回移動可能かを調べる
    for j in range(i, n - 1):
        #移動可能かを調べる
        if list_H[j] >= list_H[j+1]:
            result = result + 1
        else:
            break
    list_result.append(result)
    # print(i, result)
    
print(max(list_result))
        

### FIXED CODE ###

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

#右の数字よりもおっきいときに１，ちっさいときに０
list_H_01 = []
for i in range(n-1):
    if list_H[i] >= list_H[i+1]:
        list_H_01.append(1)
    else:
        list_H_01.append(0)
        
count = 0
list_result=[]
for i in list_H_01:
    
    if i == 0:
        list_result.append(count)
        count = 0
    if i == 1:
        count = count+1
        
list_result.append(count)
        
print(max(list_result))
### BUGGY CODE ###

from collections import deque
N,M = map(int,input().split())
E = [[] for _ in range(N+1)]
for i in range(M):
    x,y,z = map(int,input().split())
    E[x].append(y)
    E[y].append(x)

d = [-1]*(N+1)

def dfs(start,num):
    q = deque([start])
    while(q):
        v = q.pop()
        if(d[v] == -1):
            d[v] = num
        for s in E[v]:
            if(d[s] == -1):
                q.append(s)

group_num = 0
for i in range(1,N+1):
    if(d[i] == -1):
        group_num += 1
        dfs(i,group_num)

print(group_num)    


### FIXED CODE ###

from collections import deque
N,M = map(int,input().split())
E = [[] for _ in range(N+1)]
for i in range(M):
    x,y,z = map(int,input().split())
    E[x].append(y)
    E[y].append(x)

d = [-1]*(N+1)

def dfs(start,num):
    q = deque([start])
    d[start] = num
    while(q):
        v = q.pop()
        for s in E[v]:
            if(d[s] == -1):
                d[s] = num
                q.append(s)

group_num = 0
for i in range(1,N+1):
    if(d[i] == -1):
        group_num += 1
        dfs(i,group_num)

print(group_num)
### BUGGY CODE ###

N = int(input())
a = list(map(int, input().split()))
cnt = 0
while True:
    dfrag = 0
    for i in range(N):
        if a[i]%2 == 0 and dfrag == 0 :
            a[i] = a[i]//2
            dfrag = 1
    if dfrag == 0:
        break
    cnt += 1
print(cnt)
        

### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
cnt = 0
while True:
    dfrag = 0
    for i in range(N):
        if a[i]%2 == 0:
            a[i] = a[i]//2
            dfrag = 1
            cnt += 1
    if dfrag == 0:
        break
print(cnt)
### BUGGY CODE ###

n = int(input())
a_lst = input().split()
b = []

for i, a in enumerate(a_lst):
  if i % 2 == 0:
    b.append(a)
  else:
    b = [a] + b
if n % 2 == 0:
  print(' '.join(b))
else:
  print(' '.join(list(reversed(b))))

### FIXED CODE ###

n = int(input())
a_lst = input().split()
odd = [a for i, a in enumerate(a_lst) if i % 2 != 0]
even = [a for i, a in enumerate(a_lst) if i % 2 == 0]

if n % 2 == 0:
  b = list(reversed(odd)) + even
else:
  b = list(reversed(even)) + odd
print(' '.join(b))
### BUGGY CODE ###

s=list(reversed(input()))
mod=10**9+7
memo=[0 for _ in [0]*13]
m13=[(10**i)%13 for i in range(12)]
memo[0]=1
for i in range(len(s)):
    memo2=[0 for _ in [0]*13]
    a=m13[i%12]
    if s[i]=="?":
        list_=[0,1,2,3,4,5,6,7,8,9]
    else:
        list_=[int(s[i])]
    list_=[(a*j)%13 for j in list_]
    for l in list_:
        for j in range(13):
            memo2[(l+j)%13]+=memo[j]
    memo=[j%mod for j in memo2]
print(memo[5])

### FIXED CODE ###

s=list(reversed(input()))
mod=10**9+7
memo=[0 for _ in [0]*13]
m13=[(10**i)%13 for i in range(12)]
memo[0]=1
for i in range(len(s)):
    memo2=[0 for _ in [0]*13]
    a=m13[i%12]
    if s[i]=="?":
        list_=[0,1,2,3,4,5,6,7,8,9]
    else:
        list_=[int(s[i])]
    list_=[(a*j)%13 for j in list_]
    for l in list_:
        for j in range(13):
            memo2[(l+j)%13]+=memo[j]
    memo=[j%mod for j in memo2]
print(memo[5])
### BUGGY CODE ###

N = int(input())
S = [list(input()) for _ in range(N)]
for i in range(N):
    S[i] = sorted(S[i])
S = sorted(S)

count = 0
for i in range(N):
    for j in range(i+1, N):
        if S[i] == S[j]:
            count += 1
        else:
            i = j+1
            break

print(count)

### FIXED CODE ###

N = int(input())
dic = {}
s = 0
for n in range(N):
  v = ''.join(sorted(input()))
  if dic.get(v) is None:
    dic[v] = 1
  else:
    s += dic[v]
    dic[v] += 1
print(s)
### BUGGY CODE ###

import itertools
n = int(input())
p = list(map(int,input().split()))
li = []
count = 0
for i in range(n):
    min_p = 0
    li.append(p[i])
    for j in range(len(li)):
        min_p = min(p[i],li[j])
        if min_p != p[i]:
            break
    if min_p == p[i]:
        count+=1
print(count)

### FIXED CODE ###

n = int(input())
p = list(map(int,input().split()))
count = 0
p_min = p[0]
for i in range(n):
    if p_min >= p[i]:
        count+=1
    p_min = min(p[i],p_min)
print(count)
### BUGGY CODE ###

N = int(input())
A = []
for i in range(N):
    n = int(input())
    if not (n in A):
        A.append(n)
    else:
        A.remove(n)
print(len(A))

### FIXED CODE ###

N = int(input())
A = set()
for i in range(N):
    n = int(input())
    if not (n in A):
        A.add(n)
    else:
        A.remove(n)
print(len(A))
### BUGGY CODE ###

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

N, K = map(int, input().split())
MOD = 10**9+7
ans = 0
for i in range(N-K,N+1):
  m = cmb(N,i,MOD)
  m *= cmb(N-1,i-1, MOD)
  ans += m
  ans %= MOD
print(ans)

### FIXED CODE ###

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

N, K = map(int, input().split())
MOD = 10**9+7
n = min(N,K)
ans = 0
for i in range(max(1,N-n),N+1):
  m = cmb(N,i,MOD)
  m *= cmb(N-1,i-1, MOD)
  ans += m
  ans %= MOD
print(ans)
### BUGGY CODE ###

a, b, c, d = map(int, input().split())
ans = float('inf')*-1
for i in range(a, b+1):
  for j in range(c, d+1):
    ans = max(ans, i*j)

print(ans)

### FIXED CODE ###

a, b, c, d = map(int, input().split())
ans = float('inf')*-1
ans = max(ans, a*c)
ans = max(ans, a*d)
ans = max(ans, b*c)
ans = max(ans, b*d)
print(ans)
### BUGGY CODE ###

# coding: utf-8

# 標準入力 <int>
N = int(input())

# 標準入力<str>
S = input()

ans = 0

for i in range(N - 2):
  for j in range(N - i - 2):
    if S[i] == S[i + j + 1]:
      continue
    for k in range(N - i - j - 2):
      if j == k:
        continue
      if S[i + j + 1] != S[i + j + k + 2] and S[i + j + k + 2] != S[i]:
        ans += 1

print(ans)


### FIXED CODE ###

# coding: utf-8

# 標準入力 <int>
N = int(input())

# 標準入力<str>
S = input()

R = S.count("R")
G = S.count("G")
B = S.count("B")

cnt = 0

for i in range(N - 2):
  for j in range(i + 1, N - 1):
    k = i + ((j - i) * 2)
    if k < N:
      if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
        cnt += 1

print(R * G * B - cnt)
### BUGGY CODE ###

from collections import deque

n, m = map(int, input().split())
roots = [[] for _ in range(n)]
signs = [-1 for _ in range(n)]

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

queue = deque([(0, 0)])

while queue:
    room, org = queue.popleft()
    if signs[room] == -1:
        signs[room] = org
    for root in roots[room]:
        if signs[root] == -1:
            queue.append((root, room))

print('Yes')
for i in signs[1:]:
    print(i + 1)


### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
roots = [[] for _ in range(n)]
signs = [-1 for _ in range(n)]

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

queue = deque([0])
signs[0] = 0

while queue:
    room = queue.popleft()
    for root in roots[room]:
        if signs[root] == -1:
            signs[root] = room
            queue.append(root)

print('Yes')
for i in signs[1:]:
    print(i + 1)
### BUGGY CODE ###


N = int(input())
L = list(map(int, input().split()))
L = sorted(L, reverse=True)

x = 0


for i in range(len(L)):
    
    for j in range(i+1, len(L)):
        if L[i] > 2 * L[j]:
            break
        for k in range(j+1, len(L)):
            if L[i] > L[j] + L[k]:
                break
            
            if (L[k] < L[i] + L[j]):
                if (L[i] < L[j] + L[k]):
                    if  (L[j] < L[k] + L[i]):
                        x += 1

print(x)



### FIXED CODE ###

import bisect

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

cnt = 0
for i in range(n-1):
    for j in range(i+1,n):
        up = l[j] + l[i]
        #l[k] = up となるようなkのうち最小のものを見つけろ
        k = bisect.bisect_left(l, up)
        cnt += k - j - 1
print(cnt)
### BUGGY CODE ###

# https://atcoder.jp/contests/abc138/tasks/abc138_d

from collections import deque

def dfs(graph, start, ans, n):
    queue = deque([])
    queue.append(start)
    visited = [False] * n
    visited[start] = True

    while queue:
        parent = queue.popleft()
        for child in graph[parent].keys():
            if visited[child]:
                continue
            visited[child] = True
            ans[child] += ans[parent]
            queue.append(child)
    
    print(' '.join(map(str, ans)))

n,q = map(int, input().split())
tree = {}
start = 0
for i in range(n-1):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    if a not in tree:
        tree[a] = {}
    tree[a][b] = 1
    if b not in tree:
        tree[b] = {}
    tree[b][a] = 1

ans = [0]*n
for _ in range(q):
    p, x = map(int,input().split())
    p -= 1
    ans[p] += x
dfs(tree, start, ans, n)


### FIXED CODE ###

# https://atcoder.jp/contests/abc138/tasks/abc138_d

from collections import deque

def bfs(graph, start, query, n):
    queue = deque([])
    acc = query[start] if start in query else 0
    queue.append([start, acc])
    ans = [-1] * n
    ans[start] = acc

    while queue:
        idx, acc = queue.popleft()
        for child in graph[idx].keys():
            if ans[child] >= 0:
                continue
            ans[child] = acc
            if child in query:
                ans[child] += query[child]
            queue.append([child, ans[child]])
    
    print(' '.join(map(str, ans)))

n,q = map(int, input().split())
tree = {}
start = 0
for i in range(n-1):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    if a not in tree:
        tree[a] = {}
    tree[a][b] = 1
    if b not in tree:
        tree[b] = {}
    tree[b][a] = 1

query = {}
for _ in range(q):
    p, x = map(int,input().split())
    p -= 1
    if p not in query:
        query[p] = x
    else:
        query[p] += x
bfs(tree, start, query, n)
### BUGGY CODE ###

# coding: utf-8
# Your code here!

N, K = map(int, input().rstrip().split(' '))
X = sorted(list(map(int, input().rstrip().split(' '))) + [0])

i = 0
while True:
    if X[i] == 0:
        break
    i += 1

memo = [[-1] * (N + 1) for _ in range(K)]

def recursive(current_k, cost, i, left_i, right_i):
    if K == current_k:
        return cost
    if memo[current_k][i] != -1:
        return memo[current_k][i]
       
    left_cost = 1e10 
    if left_i >= 0:
        left_cost = recursive(current_k + 1, cost + X[i] - X[left_i], left_i, left_i - 1, right_i)
        
    right_cost = 1e10
    if right_i <= N:
        right_cost = recursive(current_k + 1, cost + X[right_i] - X[i], right_i, left_i, right_i + 1)
        
    min_cost = min(left_cost, right_cost)
    
    memo[current_k][i] = min_cost
    
    return min_cost
    
print(recursive(0, 0, i, i - 1, i + 1))


### FIXED CODE ###

# coding: utf-8
# Your code here!

N, K = map(int, input().rstrip().split(' '))
X = list(map(int, input().rstrip().split(' ')))

min_cost = int(1e10)
for i in range(K, N+1):
    min_cost = min(min_cost, X[i-1] - X[i-K] + min(abs(X[i-1]), abs(X[i-K])))
    
print(min_cost)
### BUGGY CODE ###

k=int(input())

def judge(s):
    flag = 1
    if len(s)<=1: return 1
    for i in range(len(s)-1):
        s1, s2 = int(s[i]),int(s[i+1])
        if abs(abs(s1)-abs(s2)) <= 1: continue
        else:
            flag = 0 
            break
    return flag


def bfs1(k, cnt=1, now=1):
    while True:
        s=str(now)
        if judge(s) and k==cnt: return now
        elif judge(s):
            cnt+=1
            now+=1
        else: now+=1

def bfs2(k, cnt=100000, now=3234566667):
    while True:
        s=str(now)
        if judge(s) and k==cnt: return now
        elif judge(s):
            cnt-=1
            now-=1
        else: now-=1    

if k<1000: print(bfs1(k,1,1))
else: print(bfs2(k))


### FIXED CODE ###

from collections import deque
k=int(input())
stack = deque([1,2,3,4,5,6,7,8,9])

def lunlun():
    cnt=0
    while True:
        now = stack.popleft()
        cnt += 1
        if cnt == k: return now
        s = str(now)
        for i in range(-1,2):
            temp=int(s[-1]) + i 
            if temp>=0 and temp<10: 
                temp1=int(s + str(temp))
                stack.append(temp1)
print(lunlun())
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
i=0
j=0
c=0
for i in range(len(a)):
    print(a.count(i+1))
    print('\n')
print(0)

### FIXED CODE ###

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

def comb(n,k,p):
  """power_funcを用いて(nCk) mod p を求める"""
  from math import factorial
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=factorial(n) %p
  b=factorial(k) %p
  c=factorial(n-k) %p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
 
def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p
  
B, W = map(int,input().split())
Mod = 10**9+7
magick = 500000004

p, q = 0, 0
inv = 1
for i in range(B+W):
  print((1-p+q)*magick%Mod)
  inv *= magick
  p += comb(i,B-1,Mod)*inv
  q += comb(i,W-1,Mod)*inv

### FIXED CODE ###

B, W = map(int,input().split())
Mod = 10**9+7
magick = 500000004

inv_t = [0]+[1]
inv_2 = [0]+[magick]
for i in range(2,B+W+1):
  inv_t += [inv_t[Mod % i] * (Mod - int(Mod / i)) % Mod]
  inv_2 += [inv_2[-1]*magick % Mod]

consts_B, consts_W = [0]*(B-1)+ [1], [0]*(W-1)+[1]
for i in range(B+W):
  if i >= B: consts_B += [consts_B[-1]*(i)*inv_t[i-B+1]%Mod]
  if i >= W: consts_W += [consts_W[-1]*(i)*inv_t[i-W+1]%Mod]

p, q = 0, 0
for i in range(B+W):
  print((1-p+q)*magick%Mod)
  p += consts_B[i]*inv_2[i+1]
  q += consts_W[i]*inv_2[i+1]
### BUGGY CODE ###

def resolve():
    '''
    code here
    '''

    N, K = [int(item) for item in input().split()]
    queries = [[int(item) for item in input().split()] for _ in range(N)]

    queries.sort(key=lambda x:x[0])

    temp_que = []
    for num, val in queries:
        temp_que = [num]*val
        K -= val
        if K <= 0:
            break

    print(temp_que[K-1])

if __name__ == "__main__":
    resolve()


### FIXED CODE ###

def resolve():
    '''
    code here
    '''

    N, K = [int(item) for item in input().split()]
    queries = [[int(item) for item in input().split()] for _ in range(N)]

    queries.sort(key=lambda x:x[0])

    temp_que = []
    for num, val in queries:
        temp_que = num
        K -= val
        if K <= 0:
            break

    print(temp_que)

if __name__ == "__main__":
    resolve()
### BUGGY CODE ###

import math


def max_index(list, max_index):
    r = -1
    max = -1
    for i in range(max_index + 1):
        v = list[i]
        if v > max:
            max = v
            r = i
    return r


def use_coupon(a, m):
    current_index = 0
    for _ in range(m):
        index = max_index(a, current_index)
        a[index] /= 2
        current_index += index + 1
        if current_index >= len(a):
            current_index = len(a)-1


def sum(a):
    s = 0
    for v in a:
        s += math.floor(v)
    return s


n, m = list(map(int, input().split(" ")))
a = list(map(int, input().split(" ")))
a.sort(reverse=True)

use_coupon(a, m)

print(sum(a))


### FIXED CODE ###

import math
from heapq import heappush, heappop


def rint(s):
    return -int(s)


def sum(a):
    s = 0
    for v in a:
        s += math.floor(-v)
    return s


n, m = list(map(int, input().split(" ")))
a = list(map(rint, input().split(" ")))
a.sort()

for i in range(m):
    v = heappop(a)
    heappush(a, v/2)

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

from bisect import bisect_left
A, B, Q = map(int, input().split())
BIG = 10**10 + 1
S = [-BIG] + [int(input()) for _ in range(A)] + [BIG*2]
T = [-BIG] + [int(input()) for _ in range(B)] + [BIG*2]
S.sort()
T.sort()
for _ in range(Q):
  x = int(input())
  shrine_b = bisect_left(S, x)
  dsl = x-S[shrine_b-1]
  dsr = S[shrine_b]-x
  temple_b = bisect_left(T, x)
  dtl = x-T[temple_b-1]
  dtr = T[temple_b]-x

  print(min(
    dsl if dsl > dtl else dtl,
    dsr if dsr > dtr else dtr,
    dsl * 2 + dtr,
    dsl + dtr * 2,
    dsr * 2 + dtl,
    dsr + dtl * 2
  ))

### FIXED CODE ###

from bisect import bisect_right
A, B, Q = map(int, input().split())
BIG = 10**10 + 1
S = [-BIG] + [int(input()) for _ in range(A)] + [BIG*2]
T = [-BIG] + [int(input()) for _ in range(B)] + [BIG*2]
for _ in range(Q):
  x = int(input())
  shrine_b = bisect_right(S, x)
  dsl = x-S[shrine_b-1]
  dsr = S[shrine_b]-x
  temple_b = bisect_right(T, x)
  dtl = x-T[temple_b-1]
  dtr = T[temple_b]-x

  print(min(
    dsl if dsl > dtl else dtl,
    dsr if dsr > dtr else dtr,
    dsl * 2 + dtr,
    dsl + dtr * 2,
    dsr * 2 + dtl,
    dsr + dtl * 2
  ))
### BUGGY CODE ###

n , m  = list(map(int,input().split()))
count = 0
while n >= 1 and m >= 2:
    count = count + 1
    n = n -1
    m = m -2

while m >= 4:
    count = count + 1
    m = m-4
    
    
print(count)

### FIXED CODE ###

n , m  = list(map(int,input().split()))
counter = 0
if n <= m // 2:
    counter = n
    m = m - 2* n
    n = 0
else:
    counter = m //2
    n = n - m //2
    m = 0

counter = counter + m //4 

kouho = m //4
print(max(counter,kouho))
### BUGGY CODE ###

N, M = [int(nm) for nm in input().split()]
A = []
for m in range(M):
  A.append(int(input()))

mod = 10**9 + 7

if N == 1:
  print(1)
else:
  i1 = 1
  if 1 in A:
    i2 = 0
  else:
    i2 = 1
  for n in range(2, N+1):
    i3 = (i1 + i2) % mod
    if n in A:
      i3 = 0
    if (n-1 in A) and (n in A):
      print(0)
      break
    i1, i2 = i2, i3
  else:
    ans = i3
    print(ans)

### FIXED CODE ###

N, M = [int(nm) for nm in input().split()]
if M != 0:
  a = int(input())

C = [1, 0] # [-2段目, -1段目]
C += [0]*(N+10) # C = [-2段目, -1段目, 0段目, 1段目, 2段目, ...]
for n in range(0, N+1):
  if M == 0:
    C[n+2] = (C[n] + C[n+1]) % 1000000007
  else: # M > 0:
    if n != a:
      C[n+2] = (C[n] + C[n+1]) % 1000000007
    else: # n == a:
      C[n+2] = 0
      M -= 1
      if M > 0:
        a = int(input())

ans = C[N+2]  % 1000000007
print(ans)
### BUGGY CODE ###

from collections import deque
h,w = map(int,input().split())
#0が進めるところ、1は無理
lis = [[1 if l == '#' else 0 for l in list(input())] for _ in range(h)]
#ゴールは9
lis[h-1][w-1] = 9
#print(lis)
#[[0, 0, 1], [1, 0, 0], [0, 0, 9]]

#この問題ではbfsを始める前に、もともと移動可能だったところの数を記録しておく
road = 0
for row in lis:
    for column in row:
        if column != 1:
            road +=1

count = 0
#(開始x,開始y,移動回数)
que = deque([])
que.append([0,0,0])
while len(que)>0:
    x,y,depth = que.popleft()

    if lis[x][y] == 9:
        count = depth
        break

    #探索済みのところは、1にする
    lis[x][y] = 1

    #遷移先は0or9なので、1以外なら行ける
    if x-1>=0 and lis[x-1][y] != 1:
        que.append([x-1,y,depth+1])
    if x+1<h and lis[x+1][y] != 1:
        que.append([x+1,y,depth+1])
    if y-1>=0 and lis[x][y-1] != 1:
        que.append([x,y-1,depth+1])
    if y+1<w and lis[x][y+1] != 1:
        que.append([x,y+1,depth+1])

#そもそも行けない
if count == 0:
    print(-1)
#(移動可能マス数) - (移動する道順上のマスの数 ＝ 最短の移動回数＋１）
else:
    print(road-(count+1))

### FIXED CODE ###

h,w = (int(x) for x in input().split())
ab = []
count = 0
for _ in range(h):
    a = input()
    a = a+'#'
    ab.append(list(a))
    for i in a:
        if i == '.':
            count += 1
ab.append(list('#'*w))
dp = [[0 for i in range(w)] for j in range(h)]
 
step = [[0, 0]]
dp[0][0] = 1
 
while len(step) > 0:
    y, x = step.pop(0)
    if y == h-1 and x == w-1:
        print(count-dp[y][x])
        exit()
    if ab[y+1][x] == '.' and dp[y+1][x] == 0 :
        step.append([y+1, x])
        dp[y+1][x] = dp[y][x] + 1
    if ab[y][x+1] == '.' and dp[y][x+1] == 0 :
        step.append([y, x+1])
        dp[y][x+1] = dp[y][x] + 1
    if ab[y-1][x] == '.' and dp[y-1][x] == 0 :
        step.append([y-1, x])
        dp[y-1][x] = dp[y][x] + 1
    if ab[y][x-1] == '.' and dp[y][x-1] == 0 :
        step.append([y, x-1])
        dp[y][x-1] = dp[y][x] + 1
 
 
print(-1)