Harryxun/stf_run huggingface dataset:
import math
MOD = 10**9+7

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

MAX = 10**6
C = [0 for _ in range(MAX+1)]
A.sort()
for a in A:
  C[a] += 1
MAX = max(A[-1],2)

ans = 1
P = [1 for _ in range(MAX+1)] #素数かどうか
P[0] = 0
P[1] = 0
lim = min(math.sqrt(MAX) + 1,MAX-1)
S = [0 for _ in range(MAX+1)] #最小公倍数の素因数分解したもの
for i in range(2,int(lim+2)):
  #素数でないなら以下の手順を行わない
  if P[i] == 0:
    continue
  #エラトステネスの篩
  k = i*2
  while k <= MAX:
    P[k] = 0
    k += i
  ind = 0
  k = 1
  while k <= MAX:
    k *= i
    ind += 1
  k = k // i 
  ind -= 1
  #最大のべきを調べる
  while k > 1:
    l = k
    flag = False
    while l <= MAX:
      if C[l] > 0:
        flag = True
        break
      l += k
    if flag:
      break
    k = k // i
    ind -= 1
  S[i] = ind
  
ans = 1
for i in range(N+1):
  ans *= pow(i,S[i],MOD)
  ans %= MOD
  
#モジュラ逆数
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

def modinv(a, m):
    g, x, y = xgcd(a, m)
    #if g != 1:
        #raise Exception('modular inverse does not exist')
    #else:
    return x % m
      
B = [0 for _ in range(MAX+1)]
ans_2 = 0
for a in A:
  if B[a] > 0:
    ans_2 += B[a]
  else:
    B[a] = modinv(a, MOD)
    ans_2 += B[a]    
  ans_2 %= MOD 

#print(ans, ans_2, P, S, B)
print((ans * ans_2) % MOD)
  

    

### FIXED CODE ###

import math
MOD = 10**9+7

N = int(input())
A = list(map(int,input().split()))
A.sort()
MAX = max(A[-1],2)

C = [0 for _ in range(MAX+1)]

for a in A:
  C[a] += 1

ans = 1
P = [1 for _ in range(MAX+1)] #素数かどうか
P[0] = 0
P[1] = 0
S = [0 for _ in range(MAX+1)] #最小公倍数の素因数分解したもの
for i in range(MAX+1):
  #素数でないなら以下の手順を行わない
  if P[i] == 0:
    continue
  #エラトステネスの篩
  k = i*2
  while k <= MAX:
    P[k] = 0
    k += i
  ind = 0
  k = 1
  while k <= MAX:
    k *= i
    ind += 1
  k = k // i 
  ind -= 1
  #最大のべきを調べる
  while k > 1:
    l = k
    flag = False
    while l <= MAX:
      if C[l] > 0:
        flag = True
        break
      l += k
    if flag:
      break
    k = k // i
    ind -= 1
  S[i] = ind
  ans *= pow(i,ind,MOD)
  ans %= MOD
  
#モジュラ逆数
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

def modinv(a, m):
    g, x, y = xgcd(a, m)
    #if g != 1:
        #raise Exception('modular inverse does not exist')
    #else:
    return x % m
      
B = [0 for _ in range(MAX+1)]
ans_2 = 0
for a in A:
  if B[a] > 0:
    ans_2 += B[a]
  else:
    B[a] = modinv(a, MOD)
    ans_2 += B[a]    
  ans_2 %= MOD 

#print(ans, ans_2, P, S, B)
print((ans * ans_2) % MOD)
def main():
    s=input()
    q=int(input())
    queryy=[]
    sent="1"
    back="1"
    for i in range(q):
        queryy.append(tuple(input().split()))
    check=-1
    for query in queryy:
    #   print(query)
        if query[0]=="1":
            check*=-1
        else:
            if query[1]=="1":
                if check==-1:
                    sent+=query[2]
                  #  s=str(query[2])+s
                else:
                    back+=query[2]
                   # s+=str(query[2])
                    
            else:
                if check==-1:
                    back+=query[2]
                    #s+=str(query[2])
                else:
                    sent+=query[2]
                    #s=str(query[2])+s
    s=s[::-1]
   # print(type(sent))
    if sent[0]=="1"
        sent=sent[1:]
    sent=sent[::-1]
    if back[0]=="1"
        back=back[1:]

    if check==1:
        
        print((sent+s+back)[::-1]) 
    else:
        print(sent+s+back)

if __name__=="__main__":
    main()          


### FIXED CODE ###

def main():
    s=input()
    q=int(input())
    queryy=[]
    sent="a"
    back="a"
    for i in range(q):
        queryy.append(tuple(input().split()))
    check=-1
    for query in queryy:
    #   print(query)
        if query[0]=="1":
            check*=-1
        else:
            if query[1]=="1":
                if check==-1:
                    sent+=str(query[2])
                   # s=str(query[2])+s
                else:
                    back+=str(query[2])
                   # s+=str(query[2])
                    
            else:
                if check==-1:
                    back+=str(query[2])
                    #s+=str(query[2])
                else:
                    sent+=str(query[2])
                    #s=str(query[2])+s
   # print(type(sent))
    #if sent[0]=="1":
     #   sent=sent[1:]
    sent=sent[1:]
    sent=sent[::-1]   
    back=back[1:]

    if check==1:
        s=sent+s+back        
        print(s[::-1]) 
    else:
        s=sent+s+back
        print(s)

if __name__=="__main__":
    main()
n = int(input())
m = 0
lis = map(long,input().split())
while(1)
  for l in lis:
  	if l % 2 == 1:
      return(m)
    else:
      l = l // 2
  m++

### FIXED CODE ###

n = int(input())
lis = list(map(int,input().split()))
m = 0
b = True
while(b):
  for index,l in enumerate(lis):
    if l % 2 == 1:
      b = False
      m -= 1
      break
    else:
      lis[index] = l / 2
  m += 1
print(m)
x=map(int, input().split())
print(x[0]+x[1]+x[2])

### FIXED CODE ###

x=input().split()
print(x[0][0]+x[1][0]+x[2][0])
a,b,h = map(int,input().split())

answer = (a + b) * h / 2

print(answer)

### FIXED CODE ###

a =int(input())
b =int(input())
h = int(input())

answer = (a + b) * h / 2

print(int(answer))
a = list(int(i) for i in input().split())
k = int(input())

maximum_sum = a[0] + a[1] + a[2] + max(a)*((2**k)-1)
print('{}'.format(maximum_sum))


### FIXED CODE ###

a, b = map(int, input().split())

takahashi = a - 1
if b >= a :
    takahashi = takahashi + 1

print('{}'.format(takahashi))
from fractions import gcd
from functools import reduce

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)  

n = int(input())
aa = list(map(int,input().split()))
           
l = lcm(*aa)        
aal = [l//ai % MOD for ai in aa] 

print(sum(aal) % MOD)

### FIXED CODE ###

from fractions import gcd
from functools import reduce
MOD = 10**9+7
def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)  

n = int(input())
aa = list(map(int,input().split()))
           
l = lcm(*aa)        
ans = 0
for ai in aa:
  ans += l//ai

print(ans % MOD)
from math import sqrt
n,d=map(int, input().split())
x=[list(map(int, input().split())) for i in range(n)]

ans=0
tmp = 0

for i in range(n):
  for j in range(i+1, n):
    xi,xj = x[i],x[j]
    for k in range(d):
      tmp += (xi[k]-xj[k]) ** 2
      
    if sqrt(tmp)%1==0:
      ans += 1

print(ans)



### FIXED CODE ###

N, A, B = map(int, input().split())
if N*A<=B:
  print(N*A)
else:
  print(B)
#cording; UTF-8

x = raw_input().split()
y = map(int,x)

a = y[0]
b = y[1]
S = a*b
L  = 2*(a+b)
print(S' 'L)


### FIXED CODE ###

#cording; UTF-8
a,b=[int(x) for x in input().split()]

S = a*b
L = 2*(a+b)
print(S,L)
import math
from functools import reduce
N = int(input())
A = list(map(int, input().split()))
def func(x,y):
    return (x*y)//math.gcd(x,y)
AB = reduce(func, A, 1)
sum = 0
for ii in range(N):
    sum += AB/A[ii]%(10**9+7)
print(int(sum%(10**9+7)))

### FIXED CODE ###

import fractions
N = int(input())
A = list(map(int, input().split()))
AB = 1
for i in A:
    AB = AB*i//fractions.gcd(AB,i)
sumB = 0
for i in A:
    sumB += AB//i
print(int(sumB%(10**9+7)))
a,b,k=map(int,input().split())
if k>=a:
  A=0
  if k-a>=b:
    B=0
  else:
    B=b-(k-a)
else:
  A=a-k
  B=b
print('{}{}'.format(A,B))


### FIXED CODE ###

a,b=input().split()
print(b+a)
N=int(input())
ans=0
m=0
for i in range(N):
  A=int(input())
  if A%2==0:
    m=m+1
    if A%3==0 or A%5==0:
    　　ans=ans+1
if m==N:
  print('APPROVED')
else:
  print('DENIED')

### FIXED CODE ###

N=int(input())
M=list(map(int,input().split()))
S=[]
T=[]
for i in range(0,len(M))  :
  if M[i]%2==0:
    T.append(M[i])
    S.append(M[i])
for j in range(0,len(S)):
  if S[j]%3!=0 and S[j]%5!=0:
      T.remove(S[j])
    
if len(S)==len(T):
  print('APPROVED')
else:
  print('DENIED')
S = input()
K = int(input())

L = []
LS = []
ans = 0
streak = 1
s = ''

for i in range(len(S)-1):
    if i == 0:
        s = S[0]
        streak = 1
    
    if s == '':
        if S[i+1:i+2] == S[i:i+1]:
            s = S[i:i+1]
            streak += 1
    else:
        if S[i+1:i+2] == s:
            streak += 1
        else:
            L.append(streak)
            LS.append(s)
            s = ''
            streak = 1
    
    if i == len(S)-2:
        if streak >= 2:
            L.append(streak)
            LS.append(s)
        if streak == len(S):
            ans = K*(len(S)//2)
            print(ans)
            exit()

if LS[0] != LS[-1]:
    for l in L:
        if i >=2:
            ans += l//2
    ans *= K
elif LS[0] == LS[-1]:
    for i in range(1,len(L)-1):
        ans += L[i]//2
    ans = K*ans + L[0]//2 + (K-1)*(L[0]+L[-1])//2 + L[-1]//2
print(ans)

### FIXED CODE ###

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

if len(S) == 1:
    print(K//2)
    exit()
L = []
LS = []
ans = 0
streak = 1
s = ''

for i in range(len(S)-1):
    if i == 0:
        s = S[0]
        streak = 1
    
    if s == '':
        if S[i+1:i+2] == S[i:i+1]:
            s = S[i:i+1]
            streak += 1
    else:
        if S[i+1:i+2] == s:
            streak += 1
        else:
            L.append(streak)
            LS.append(s)
            s = ''
            streak = 1
    
    if i == len(S)-2:
        L.append(streak)
        LS.append(S[-1])
        # if streak == len(S):
        #     ans = K*(len(S)//2)
        #     print(ans)
        #     exit()

# print(LS)
# print(L)
if streak == len(S):
    ans = (len(S)*K)//2
    # print(len(S))
    print(ans)
    exit()

if LS[0] != LS[-1]:
    for l in L:
        # if l >=2:
        ans += l//2
    ans = K*ans
elif LS[0] == LS[-1]:
    for i in range(1,len(L)-1):
        ans += L[i]//2
    ans = K*ans + L[0]//2 + (K-1)*((L[0]+L[-1])//2) + L[-1]//2
print(ans)
import sys
import os
f = open("C:/Users/user/Documents/python/ant/import.txt","r")
sys.stdin = f

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

n = int(input())
if n%3 == 0:
    if n == 111:
        print 3
    else
        print 0
elif n%3 ==1:
    print 1
else
    print 2

### FIXED CODE ###

n = int(input())
if n%3 == 0:
    if n == 111:
        print(3)
    else:
        print (0)
elif n%3 ==1:
    print(1)
else:
    print(2)
A, B = map(float,input().split())

print(int((A*(B*100)//100))

### FIXED CODE ###

import decimal
A, B = map(decimal.Decimal,input().split())

print(A*B//1)
n=int(input())
s=[input() for i in range(n)]

d={}

for i in s:
  if i in d:
    d[i]+=1
  else:
    d[i]=1
d=sorted(d.items,reverse=True)



for i in d.key:
  print(i)


### FIXED CODE ###

#C
#入力
N=int(input())
S=[input() for i in range(N)]

#処理
result={}
for i in S:
    if i in result:
        result[i]+=1
    else:
        result[i]=1

x=max(result.values())

Z=[]
for i in result.items():
    if i[1]==x:
        Z.append(i[0])
Z.sort()
for i in Z:
    print(i)
import numpy as np

W, H, N = map(int, input().split())
l = np.zeros((H,W))

for i in range(N):
  x, y, a = map(int, input().split())
  if a==1:
    l[:,:x] = 1
  elif a==2:
    l[:,x:] = 1
  elif a==3:
    l[:y,:] = 1
  elif a==4:
    l[y:,:] = 1
    
print(H*W-int(l.sum().sum()))

### FIXED CODE ###

import numpy as np

W, H, N = map(int, input().split())
l = np.zeros((H,W))

for i in range(N):
  x, y, a = map(int, input().split())
  if a==1:
    l[:,:x] = 1
  elif a==2:
    l[:,x:] = 1
  elif a==3:
    l[:y,:] = 1
  elif a==4:
    l[y:,:] = 1
    
print(H*W-int(l.sum().sum()))
n = int(input())
import math

def getk(n):
    return int((1+math.sqrt(8*n-7))/2)

while(True):
    k = getk(n)
    print(k,end="")
    print(" ",end="")
    if k ==1:
        break
    n-=k

### FIXED CODE ###

n = int(input())
import math

def getk(num):
    return int((1+math.sqrt(8*num-7))/2)

while(True):
    k = getk(n)
    print(k)
    n-=k
    if k == 1 or n<=0:
        break
a, b = int(input().sprit(" "))

if a > b
  print("{} > {}".format(a, b))
elif a < b
  print("{} < {}".format(a, b))
elif a == b
  print("{} == {}".format(a, b))
   

### FIXED CODE ###

a, b = map(int, input().split())

if a > b:
  print("a > b")
elif a < b:
  print("a < b")
elif a == b:
  print("a == b")
a=input().split()
N=int(a[0])
M=int(a[1])
X=int(a[2])
list1=[]
for i in range(N) :
  k=input().split()
  k=[int(j) for j in k]
  list1.append(k)
flag1=True
def count(item,i) :
  count=0
  for a in item :
    count+=a[i]
  return count

import itertools
for i in range(1,N+1) :
  c=list(itertools.combinations(list1,i))

  value_list=[]
  for item in c :
    item1=list(item)


    if count(item,1)>=X and count(item,2)>=X and count(item,3)>=X :
      value_list.append(count(item,0))
  if value_list!=[] :
    print(min(value_list))
    flag1=False

    break
if flag1 :
  print('-1')

### FIXED CODE ###

a=input().split()
N=int(a[0])
M=int(a[1])
X=int(a[2])
list1=[]
for i in range(N) :
  k=input().split()
  k=[int(j) for j in k]
  list1.append(k)

flag1=True
def count(item,i) :
  count1=0
  for a in item :
    count1+=a[i]
  return count1

def algo(item,i) :

  for j in range(1,i+1) :
    if count(item,j)<X :
      return False
  return True


import itertools
value_list=[]
for i in range(1,N+1) :
  c=list(itertools.combinations(list1,i))


  for item in c :
    item1=list(item)


    if algo(item1,M) :
      value_list.append(count(item1,0))

if value_list!=[] :
  print(min(value_list))
else :
  print('-1')
n = int(input())
h = [int(i) for i in input().split()]
dp = [0,abs(h[0]-h[1])]
for i in range(2,n): 
dp.append(min(dp[-1]+abs(h[i]-h[i-1]),dp[-2]+abs(h[i]-h[i-2])))
print(dp[-1])

### FIXED CODE ###

from sys import stdin
n = int(stdin.readline())
h = [int(i) for i in stdin.readline().split(' ')]

minCosts = [0, abs(h[1]-h[0])]
for i in range(2, len(h)):
    minCosts.append(min(abs(h[i]-h[i-2])+minCosts[i-2], abs(h[i]-h[i-1])+minCosts[i-1]))

print(minCosts[-1])
import numpy as np
import itertools
from scipy.special import comb

n,p =input().split()
n = int(n)
p = int(p)

a_list = input().split()
a_list = [int(x) for x in a_list]
a_array = np.array(a_list)

amari = a_array % 2

zero_count = np.sum(amari == 0)
one_count = np.sum(amari == 1)

zero_pattern = 2**zero_count

if p == 0:
    if one_count >= 2:
        i = 1
        one_pattern = 1
        while i*2 <= one_count:
#             one_pattern  += len(list(itertools.combinations(np.arange(one_count),i*2)))
            one_pattern += comb(one_count,i*2)
            i += 1
    else:
        one_pattern = 1
else:
    if one_count >= 1:
        i = 1
        one_pattern = 0
        while i*2 - 1 <= one_count:
#             one_pattern  += len(list(itertools.combinations(np.arange(one_count),i*2-1)))
            one_pattern += comb(one_count,i*2-1)
            i += 1
    if one_count < 1:
        one_pattern = 0
        
print(int(zero_pattern * one_pattern))

### FIXED CODE ###

import numpy as np

n,p =input().split()
n = int(n)
p = int(p)

a_list = input().split()
a_list = [int(x) for x in a_list]
a_array = np.array(a_list)

amari = a_array % 2

zero_count = np.sum(amari == 0)
one_count = np.sum(amari == 1)

zero_pattern = 2**zero_count
if p == 0:
    if one_count >= 2:
        one_pattern = 2**one_count/2
    else:
        one_pattern = 1
else:
    if one_count >= 1:
        one_pattern = 2**one_count/2
    if one_count < 1:
        one_pattern = 0
        
print(int(zero_pattern * one_pattern))
def main():
    N, Q = map(int, input().split())
    E = [[] for i in range(N+1)]
    counter = [0] * (N+1)

    for i in range(N-1):
        a, b = map(int, input().split())
        E[a].append(b)
        E[b].append(a)

    def mktree(v, parent, E):
        children = E[v]
        children.remove(parent)
        for child in children:
            mktree(child, v, E)

    for child in E[1]:
        mktree(child, 1, E)

    for i in range(Q):
        # 頂点p を根とする部分木に含まれるカウンターにxを足す
        p, x = map(int, input().split())
        counter[p] += x

    def get(v, children, counter):
        c = counter[v]
        for child in children[v]:
            counter[child] += c
            get(child, children, counter)

    #get(1, E, counter)
    #print(" ".join(str(x) for x in counter[1:]))

main()






### FIXED CODE ###

def main():
    import sys
    sys.setrecursionlimit(2*10**5)
    N, Q = map(int, input().split())
    E = [[] for i in range(N+1)]
    counter = [0] * (N+1)

    for i in range(N-1):
        a, b = map(int, input().split())
        E[a].append(b)
        E[b].append(a)

    for i in range(Q):
        # 頂点p を根とする部分木に含まれるカウンターにxを足す
        p, x = map(int, input().split())
        counter[p] += x

    queue = []

    parent = [1]
    def mktree(v, parent, E):
        children = E[v]
        children.remove(parent)
        for child in children:
            mktree(child, v, E)

    while parent:
        p = parent.pop()
        for child in E[p]:
            E[child].remove(p)
            parent.append(child)

    def get(v, children, counter):
        c = counter[v]
        for child in children[v]:
            counter[child] += c
            get(child, children, counter)

    parent = [1]
    while parent:
        p = parent.pop()
        c = counter[p]
        for child in E[p]:
            counter[child] += c
            parent.append(child)

    print(" ".join(str(x) for x in counter[1:]))

main()
X=int(input())
while(True):
    k=breaknum=0
    for n in range(-118,120):
        x=n**5-(n-k)**5
        if X==x:
            print(n**5)
            breaknum=-1
            break
    k+=1
    if breaknum=-1:
        break

### FIXED CODE ###

X=int(input())
k=breaknum=1
while(True):
    for n in range(-118,120):
        x=n**5-(n-k)**5
        if X==x:
            print("{0} {1}".format(n,n-k))
            breaknum=-1
            break
    k+=1
    if breaknum==-1:
        break
import sys
input = sys.stdin.readline
N, Q = map(int, input().split())
*C, = map(int, input().split())

last = [-1]*N
P = []
for i, c in enumerate(C):
    if last[c] != -1:
        P.append((last[c], i+1))
    last[c] = i+1

queries = []
for i in range(Q):
    l, r = map(int, input().split())
    queries.append((l, r, i))

P.sort()
queries.sort(reverse=True)

class BIT():
    def __init__(self, n, x=1):
        self.n = n
        self.T = [0]*(n+1)

    def add(self, i, x):
        while i <= self.n:
            self.T[i] += x
            i += i & -i

    def sum(self, i):
        ret = 0
        while i:
            ret += self.T[i]
            i -= i & -i
        return ret

bit = BIT(N)
ans = [0]*Q
for l, r, i in queries:
    while P and P[-1][0] >= l:
        cl, cr = P.pop()
        bit.add(cr, 1)
    ans[i] = r-l+1-bit.sum(r)

print('\n'.join(map(str, ans)))


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.buffer.readline
    N, Q = map(int, input().split())
    *C, = map(int, input().split())

    last = [-1]*(N+1)
    P = [[] for _ in [0]*(N+1)]
    for i, c in enumerate(C):
        if last[c] != -1:
            P[last[c]].append(i+1)
        last[c] = i+1

    queries = [[] for _ in [0]*(N+1)]
    for i in range(Q):
        l, r = map(int, input().split())
        queries[l].append((r, i))

    def add(A, i, x):
        while i <= N:
            A[i] += x
            i += i & -i

    def sum(A, i):
        ret = 0
        while i:
            ret += A[i]
            i ^= i & -i
        return ret

    A = [0]*(N+1)
    ans = [0]*Q
    for l in range(N, 0, -1):
        for cr in P[l]:
            add(A, cr, 1)
        for r, i in queries[l]:
            ans[i] = r-l+1-sum(A, r)

    print(*ans, sep='\n')


if __name__ == '__main__':
    main()
a1 = max(a - k, 0)
if a1 >= 1:
    a2 = b
else:
    a2 = a + b - k
if a2 < 0:
    a2 = 0
print(a1, a2)


### FIXED CODE ###

a,b,k = map(int, input().split())
a1 = max(a - k, 0)
if a1 >= 1:
    a2 = b
else:
    a2 = a + b - k
if a2 < 0:
    a2 = 0
print(a1, a2)
h, w = map(int, input().split())
s = [input() for i in range(h)]

cnt = [[None] * w for i in range(h)]
for i in range(h):
    j = 0
    while j < w:
        if s[i][j] == '#':
            cnt[i][j] = 0
            j += 1
            continue
        l = 0
        while j+l < w:
            if s[i][j+l] == '#':
                break
            l += 1
        for k in range(l):
            cnt[i][j+k] = l
        j += l

for i in range(w):
    j = 0
    while j < h:
        if s[j][i] == '#':
            cnt[i][j] = 0
            j += 1
            continue
        l = 0
        while j+l < h:
            if s[j+l][i] == '#':
                break
            l += 1
        for k in range(l):
            cnt[j+k][i] += l
        j += l

ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, cnt[i][j])

### FIXED CODE ###

import sys
from bisect import bisect_left
sys.setrecursionlimit(10**7)
def lmi(): return list(map(int, input().split()))

h, w = lmi()
s = [input() for i in range(h)]

a = [[] for i in range(h)]
al = [[] for i in range(h)]
b = [[] for i in range(w)]
bl = [[] for i in range(w)]
for i in range(h):
    k = 0
    for j in range(w):
        if s[i][j] == '.':
            k += 1
            if j == w-1:
                a[i].append(k)
                al[i].append(j)
        elif j != 0 and s[i][j-1] == '.':
            a[i].append(k)
            al[i].append(j-1)
            k = 0

for i in range(w):
    k = 0
    for j in range(h):
        if s[j][i] == '.':
            k += 1
            if j == h-1:
                b[i].append(k)
                bl[i].append(j)
        elif j != 0 and s[j-1][i] == '.':
            b[i].append(k)
            bl[i].append(j-1)
            k = 0
'''
print(a)
print(al)
print(b)
print(bl)
'''

ans = 0
for i in range(h):
    k = 0
    c = -1
    for j in range(w):
        if s[i][j] == '.':
            c = a[i][k]
            d = b[j][bisect_left(bl[j], i)]
            #print(c,d)
            ans = max(ans, c+d-1)
        elif j != 0 and s[i][j-1] == '.' and c != -1:
                k += 1
print(ans)
import numpy as np

h, w = map(int ,input().split())
s = [list(input()) for _ in range(h)]
check = [[0] * w for _ in range(h)]
move = [[1, 0], [-1, 0], [0, 1], [0, -1]]
ans = 0

for i in range(h):
    for j in range(w):
        if check[i][j] == 1:
            continue
        black, white = 0, 0 

        stack = [[i, j]]
        check[i][j] = 1
        if s[i][j] == '#':
            black += 1
        else:
            white += 1

        while len(stack) > 0:
            x, y = stack.pop()
            tmp = s[x][y]
            for dx, dy in move:
                nx, ny = x + dx, y + dy
                if 0 <= nx < h and 0 <= ny < w and tmp != s[nx][ny] and check[nx][ny] == 0:
                    stack.append([nx, ny])
                    check[nx][ny] = 1
                    if s[nx][ny] == '#':
                        black += 1
                    else:
                        white += 1

        ans += black * white

print(ans)

# %%


### FIXED CODE ###

h, w = map(int ,input().split())
s = [list(input()) for _ in range(h)]
check = [[0] * w for _ in range(h)]
move = [[1, 0], [-1, 0], [0, 1], [0, -1]]
ans = 0

for i in range(h):
    for j in range(w):
        if check[i][j] == 1:
            continue
        black, white = 0, 0 

        stack = [[i, j]]
        check[i][j] = 1
        if s[i][j] == '#':
            black += 1
        else:
            white += 1

        while len(stack) > 0:
            x, y = stack.pop()
            tmp = s[x][y]
            for dx, dy in move:
                nx, ny = x + dx, y + dy
                if 0 <= nx < h and 0 <= ny < w and tmp != s[nx][ny] and check[nx][ny] == 0:
                    stack.append([nx, ny])
                    check[nx][ny] = 1
                    if s[nx][ny] == '#':
                        black += 1
                    else:
                        white += 1

        ans += black * white

print(ans)

# %%
N = int(input())

ans = 1
for i in range(7)
    if 2**i < N:
        ans = 2**i
    else:
        break

print(ans)

### FIXED CODE ###

N = int(input())

ans = 1
for i in range(7):
    if 2**i <= N:
        ans = 2**i
    else:
        break

print(ans)