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

import itertools
import heapq
import sys
import functools
import operator
input = sys.stdin.readline
#-------------
n,k = map(int,input().split())
a = list(map(int,input().split()))
#-------------
comb = itertools.combinations(a,k)
  
l = [list(i) for i in comb]
  
A = [functools.reduce(operator.mul,l[i]) for i in range(len(l))]
 
l_max = max(A)
waru = 10**9 + 7
print(l_max % waru)

### FIXED CODE ###

import sys
 
n, k = map(int, input().split())
a = [int(x) for x in input().split()]
mod = pow(10, 9)+7
zero = 0
plus = []
minus = []
for i in range(n):
  if a[i] == 0:
    zero += 1
  elif a[i] > 0:
    plus.append(a[i])
  else:
    minus.append(a[i])
 
P, M = len(plus), len(minus)
plus.sort(reverse=True)
minus.sort()
ans = 1
if n == k:
  for i in range(n):
    ans *= a[i]
    ans %= mod
elif P+M < k:
  ans = 0
elif P == 0:
  if zero and k%2:
    ans = 0
  else:
    if k%2:
      minus.reverse()
    for i in range(k):
      ans *= minus[i]
      ans %= mod
else:
  q = 0
  if k%2:
    ans *= plus[0]
    ans %= mod
    q = 1
  judge = []
  for i in range((len(plus)-q)//2):
    judge.append(plus[2*i+q]*plus[2*i+q+1])
  for i in range(len(minus)//2):
    judge.append(minus[2*i]*minus[2*i+1])
  judge.sort(reverse=True)
  for i in range(k//2):
    ans *= (judge[i]%mod)
    ans %= mod
 
print(ans)
### BUGGY CODE ###

import numpy as np
N, K = list(map(int,input().split()))
a = list(map(int,input().split()))

a = np.array(a)

s = 0
e = 0

arr = []
for s in range(N):
    for e in range(s+1, N+1):
        arr.append(a[s:e])

max_len = len(bin(np.sum(a))[2:])

su = 0
b = [bin(np.sum(aa))[2:] for aa in arr]
b = ['0' * (max_len - len(bb)) + bb for bb in b]
while True:
    c = [bb for bb in b if bb[0] == '1']
    if len(c) >= K:
        su += 2 ** (len(c[0]) - 1)
        b = [cc[1:] for cc in c]
    else:
        b = [bb[1:] for bb in b]
    if len(b[0]) == 0:
        break
print(su)

### FIXED CODE ###

import numpy as np
N, K = list(map(int,input().split()))
a = list(map(int,input().split()))

a = np.array(a)

s = 0
e = 0

arr = []
aa = np.append(0,np.cumsum(a))
for s in range(len(aa)):
    for e in range(s+1, len(aa)):
        arr.append(aa[e] - aa[s])

max_len = len(bin(np.sum(a))[2:])

su = 0
b = [bin(aa)[2:] for aa in arr]
b = ['0' * (max_len - len(bb)) + bb for bb in b]
while True:
    c = [bb for bb in b if bb[0] == '1']
    if len(c) >= K:
        su += 2 ** (len(c[0]) - 1)
        b = [cc[1:] for cc in c]
    else:
        b = [bb[1:] for bb in b]
    if len(b[0]) == 0:
        break
print(su)
### BUGGY CODE ###

L, R = map( int, input().split() )
result = 2019

for i in range(L, R+1):
    for j in range(i+1,R+1):
        tmp = (i*j) % 2019
        if tmp < result:
            result = tmp

print(result)

### FIXED CODE ###

L, R = map( int, input().split() )
result = 2019

for i in range(L, R+1):
    for j in range(i+1,R+1):
        tmp = (i*j) % 2019
        if tmp < result:
            result = tmp
        if result == 0:
            break;
    if result == 0:
        break;

print(result)
### BUGGY CODE ###

import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N, M = map(int, input().split())
ABC = [list(map(int, input().split())) for _ in range(M)]

INF = 1 << 28
ds = [[INF] * (N + 1) for _ in range(N + 1)]
for i in range(N + 1):
    ds[i][i] = 0

for abc in ABC:

    ds[abc[0]][abc[1]] = ds[abc[1]][abc[0]] = min(ds[abc[0]][abc[1]], abc[2])

for k in range(N + 1):
    for i in range(N + 1):
        for j in range(N + 1):
            ds[i][j] = ds[j][i] = min(ds[i][j], ds[i][k] + ds[k][j])
cnt = 0
for abc in ABC:
    used = False
    for i in range(N + 1):
        for j in range(N + 1):
            if ds[i][j] == ds[i][abc[0]] + abc[2] + ds[abc[1]][j]:
                used = True
    if not used:
        cnt += 1

print(cnt)


### FIXED CODE ###

import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N, M = map(int, input().split())
ABC = [list(map(int, input().split())) for _ in range(M)]

INF = 1 << 28
ds = [[INF] * (N + 1) for _ in range(N + 1)]
for i in range(N + 1):
    ds[i][i] = 0

for abc in ABC:

    ds[abc[0]][abc[1]] = ds[abc[1]][abc[0]] = min(ds[abc[0]][abc[1]], abc[2])

for k in range(N + 1):
    for i in range(N + 1):
        for j in range(N + 1):
            ds[i][j] = ds[j][i] = min(ds[i][j], ds[i][k] + ds[k][j])
cnt = 0
for abc in ABC:
    used = False
    for i in range(N + 1):
        for j in range(N + 1):
            if ds[i][j] == ds[i][abc[0]] + abc[2] + ds[abc[1]][j]:
                used = True
    if not used:
        cnt += 1

print(cnt)
### BUGGY CODE ###

def main():
    """"ここに今までのコード"""
    N, K = map(int, input().split())
    dice_list = list(map(int, input().split()))
    expected_values = [sum(range(1, i + 1)) / i for i in dice_list]
    max_sum = -1

    for i in range(N - K + 1):
        s = sum([n for n in expected_values[i:i+K]])
        if s > max_sum:
            max_sum = s
    
    print(max_sum)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    """"ここに今までのコード"""
    N, K = map(int, input().split())
    dice_list = list(map(int, input().split()))
    max, s = 0, 0

    for i in range(K):
        s += (dice_list[i] + 1) / 2
    
    max = s

    for i in range(N-K):
        s -= (dice_list[i] + 1) / 2
        s += (dice_list[i+K] + 1) / 2
        if s > max:
            max = s
    
    print(max)


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

import sys
input = sys.stdin.buffer.readline

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return float(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()



def main():
	nn=II()
	A=LI()
	ans="pairwise coprime"

	n = 500005
	primes = set(range(2, n+1))
	for i in range(2, int(n**0.5+1)):
		primes.difference_update(range(i*2, n+1, i))
	primes=set(primes)

	#print(primes)


	B=set(range(1,5*10**6+5))
	C=set()
	for i in A:
		a=set()
		while i%2==0:
			a.add(2)
			i//=2
		f=3
		while f*f<=i:
			if i in primes:
				break
			elif i%f==0:
				a.add(f)
				i//=f
			else:
				f+=2
		if i!=1:
			a.add(i)
		B&=a
		if C&a:
			ans="setwise coprime"
		C|=a

	if B:
		ans="not coprime"

	print(ans)





















if __name__ == "__main__":
	main()


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return float(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()



def main():
	nn=II()
	A=LI()
	ans="pairwise coprime"

	n = 500005
	primes = set(range(2, n+1))
	for i in range(2, int(n**0.5+1)):
		primes.difference_update(range(i*2, n+1, i))
	primes=set(primes)

	#print(primes)


	B=set(range(1,5*10**5+5))
	C=set()
	for i in A:
		a=set()
		while i%2==0:
			a.add(2)
			i//=2
		f=3
		while f*f<=i:
			if i in primes:
				break
			elif i%f==0:
				a.add(f)
				i//=f
			else:
				f+=2
		if i!=1:
			a.add(i)
		B&=a
		if C&a:
			ans="setwise coprime"
		C|=a

	if B:
		ans="not coprime"

	print(ans)





















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

import bisect

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

ans = 0
for i in range(n-1, 1, -1):
    for j in range(i-1, 0, -1):
        S = L[:j]
        ans += j - bisect.bisect_right(S, L[i]-L[j])

print(ans)


### FIXED CODE ###

import bisect

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

ans = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        ans += bisect.bisect_left(L, L[i]+L[j]) - (j+1)

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

# inputを高速化する。
import sys
import numpy as np

input = sys.stdin.readline

N,K = map(int, input().split())

blocks = list(map(int, input().split()))

route = [10 ** 9] * N
route[0] = 0

blocks = np.array(blocks)

for i in range(1, N):
    count = max(0, i-K)
    route[i] = min(route[count:i] + np.abs(blocks[count:i] - blocks[i]))

print(route[-1])

### FIXED CODE ###

# inputを高速化する。
import sys
import numpy as np

input = sys.stdin.readline

N,K = map(int, input().split())
blocks = list(map(int, input().split()))

route = np.zeros(N, dtype=int)

blocks = np.array(blocks)

for i in range(1, N):
    count = max(0, i-K)
    route[i] = min(route[count:i] + np.abs(blocks[count:i] - blocks[i]))

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

N, Q = map(int, input().split())
S = input()
for i in range(Q):
    l, r = map(int, input().split())
    print((r - l + 1 - len(S[l-1:r].replace('AC','')))//2)


### FIXED CODE ###

N, Q = map(int, input().split())
S = list(input())
t = [0] * (N+1)
cnt = 0
for i in range(1,N):
    if S[i-1] == 'A' and S[i] == 'C':
        cnt += 1
    t[i] = cnt
t[-1] = t[-2]
for i in range(Q):
    l, r = map(int, input().split())
    print(t[r-1] - t[l-1])
### BUGGY CODE ###

from collections import Counter


def main():
    N = int(input()) # 5人
    An = list(map(int, input().split(' '))) # A2, A3,...
    
    # N = 10
    # An = [1,1, 1, 1, 1, 1, 1, 1, 1]
    
    counter = []
    count = 0
    start_index = 0
    
    for n in range(1, N+1):
        an = Counter(An[start_index:])
        print(an[n])
        
    
    # for i in counter:
    #     print(i)
            


    
main()


### FIXED CODE ###

from collections import Counter


def main():
    N = int(input()) # 5人
    An = list(map(int, input().split(' '))) # A2, A3,...
    
    # N = 10
    # An = [1,1, 1, 1, 1, 1, 1, 1, 1]
    
    # out = [0] *
    
    an = Counter(An)
    for n in range(1, N+1):  
        print(an[n])
            


    
main()
### BUGGY CODE ###

N,X,Y = map(int,input().split())
for k in range(1,N):
    S = 0
    for i in range(1,N):
        for j in range(i+1,N+1):
            A = abs(X-i)+abs(Y-j)+1
            if j-i <= A:
                if j-i == k:
                    S += 1
            else:
                if A == k:
                    S += 1
    print(S)

### FIXED CODE ###

N,X,Y = map(int,input().split())
A = [0 for i in range(N)]
for i in range(N-1):
    a = i+1
    for j in range(i+1,N):
        b = j+1
        A[min([b-a,abs(X-a)+abs(Y-b)+1])] += 1
for i in range(1,N):
    print(A[i])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun Apr 26 22:28:26 2020

@author: Kanaru Sato
"""

s = input()
n = len(s)
s = int(s)
dic = {}
mod = 2019
count = 0

for i in range(1,n+1):
    num = s%(10**i)
    num %= mod
    if num in dic:
        count += 1
    if num not in dic:
        dic[num] = 1

if 0 in dic:
    count += 1

print(count)

### FIXED CODE ###

s = list(map(int, list(input())))
n = len(s)

countdic = {}
mod = 2019

num = 0
d = 1
for i in range(1,n+1):
    num += s[n-i]*d
    num %= mod
    if num in countdic:
        countdic[num] += 1
    if num not in countdic:
        countdic[num] = 1
    d = (10*d)%mod

ans = 0
for key in countdic:
    ans += countdic[key]*(countdic[key]-1)//2

if 0 in countdic:
    ans += countdic[0]

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

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from heapq import heapify, heappop, heappush
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, X, Y = MAP()
dic = defaultdict(int)
for i in range(1, N+1):
    for j in range(1, N+1):
        tmp = min(abs(i - j), abs(X-i)+1+abs(j-Y), abs(Y-i)+1+abs(X-j))
        dic[tmp] += 1
for i in range(1, N):
    print(dic[i]//2)        



### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from heapq import heappop, heappush, heapify
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
 
def dijkstra(E, start):
    N_d = len(E)
    dist = [INF] * N_d
    dist[start] = 0
    q = [(0, start)]
    while q:
        dist_v, v = heappop(q)
        if dist[v] != dist_v:
            continue
        for u, dist_vu in E[v]:
            dist_u = dist_v + dist_vu
            if dist_u < dist[u]:
                dist[u] = dist_u
                heappush(q, (dist_u, u))
    return dist
 
N, X, Y = MAP()
 
graph = defaultdict(list)
 
for i in range(N-1):
    graph[i].append((i+1, 1))
    graph[i+1].append((i, 1))
 
graph[X-1].append((Y-1, 1))
graph[Y-1].append((X-1, 1))
 
a = dijkstra(graph, 0)
count = defaultdict(int)
for i in range(N):
    a = dijkstra(graph, i)
    
    # print(a[i+1:])
    for c in a[i+1:]:
        count[c] += 1
# print(count)
 
for i in range(1, N):
    print(count[i])
### BUGGY CODE ###

from bisect import bisect_left

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

for _ in range(m):
  b, c = map(int, input().split())
  i = bisect_left(alist, c)
  if i + 1 > b:
    alist = alist[b:] + [c]*b
  else:
    alist = alist[i:] + [c]*i
  alist.sort()

print(sum(alist))



### FIXED CODE ###

n, m = map(int, input().split())
alist = list(sorted(map(int, input().split())))
bc = []
total = 0
for _ in range(m):
  bc.append(tuple(map(int, input().split())))

lim = n-1
total = 0
ans = 0
for b, c in sorted(bc, key=lambda x: -x[1]):
  while lim >= 0 and alist[lim] >= c:
    ans += alist[lim]
    lim -= 1
    total += 1
  ans += c * min(b, n-total)
  total += min(b, n-total)
  if total == n:
    break
if total == n:
  print(ans)
else:
  print(ans + sum(alist[total:]))
### BUGGY CODE ###

def main():
    n = int(input())
    a_tuple = tuple(map(int, input().split()))

    answer = 1
    for a in a_tuple:
        answer *= a
    print(answer if answer <= 10**18 else -1)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main() -> None:
    n = int(input())
    a_tuple = tuple(map(int, input().split()))

    if 0 in a_tuple:
        print(0)
        return
    boader = 10 ** 18
    answer = 1
    for a in a_tuple:
        answer *= a
        if answer > boader:
            print(-1)
            return
    print(answer)


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

import numpy as np

mod=10**9+7

def inverse(r):
    tmp=mod
    ks=[]
    while True:
        ks.append(tmp//r)
        tmp%=r
        t=tmp
        tmp=r
        r=t
        if r==0:
            break

    x=np.array([[1,0],[0,1]])
    for k in ks:
        x=np.array([[0,1],[1,-k]]).dot(x)

    if x[0,1]<0:
        return x[0,1]+mod
    else:
        return x[0,1]
        

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

fact=[1]
for i in range(1,N+1):
    fact.append(fact[i-1]*i%mod)

ifact=[0]
for i in range(1,N+1):
    ifact.append((ifact[i-1]+inverse(i))%mod)

ans=0
for j in range(1,N+1):
    ans+=(ifact[j]+ifact[N-j+1]-1)*A[j-1]
    ans%=mod
    

ans*=fact[N]
ans%=mod
print(ans)

### FIXED CODE ###

import itertools
mod=10**9+7

def inverse(r,inv):
    return -(mod//i)*inv[mod%i]%mod
        

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

fact=[1,1]
inv=[0,1]
for i in range(2,N+1):
    fact.append(fact[i-1]*i%mod)
    inv.append(inverse(i,inv)%mod)
ifact = list(itertools.accumulate(inv))

ans=0
for j in range(1,N+1):
    ans+=(ifact[j]+ifact[N-j+1]-1)*A[j-1]*fact[N]%mod
    ans%=mod
    
ans%=mod
print(ans)
### BUGGY CODE ###

def main():
  N = int(input())
  Sp = []
  Sm = []
  total = 0
  for i in range(N):
    l = input()
    u = 0
    h = 0
    for j in range(len(l)):
      if l[j] == '(':
        h += 1
      else:
        h -= 1
      u = min(u, h)
    if h > 0:
      Sp.append([u, h])
    else:
      Sm.append([u-h, -h])
    total += h
  if total != 0:
    print('No')
    exit()
  if len(Sp) < len(Sm):
    Sp.sort(reverse=True)
    p = check(Sp)
    if not p:
      print('No')
      exit()
    Sm.sort(reverse=True)
    m = check(Sm)
    if not m:
      print('No')
      exit()
  else:
    Sm.sort(reverse=True)
    m = check(Sm)
    if not m:
      print('No')
      exit()
    Sp.sort(reverse=True)
    p = check(Sp)
    if not p:
      print('No')
      exit()
  print('Yes')

def check(S):
  h = 0
  for i in range(len(S)):
    if h + S[i][0] < 0:
      return False
    else:
      h += S[i][1]
  return True

if __name__ == '__main__':
  main()

### FIXED CODE ###

import sys
readline = sys.stdin.readline

def main():
  N = int(readline())
  Sp = []
  Sm = []
  total = 0
  bm = 0
  for i in range(N):
    l = readline().strip()
    b = 0
    h = 0
    for j in range(len(l)):
      if l[j] == '(':
        h += 1
      else:
        h -= 1
      b = min(b, h)
    if h == 0 and b != 0:
      bm = min(bm, b)
    elif h > 0:
      Sp.append([b, h])
    elif h < 0:
      Sm.append([b-h, -h])
    total += h
  Sp.append([bm, 0])
  if total != 0:
    print('No')
    exit()
  Sp.sort(key=lambda x:x[0], reverse=True)
  p = check(Sp)
  if p < 0:
    print('No')
    exit()
  Sm.sort(key=lambda x:x[0], reverse=True)
  m = check(Sm)
  if m < 0:
    print('No')
    exit()
  print('Yes')

def check(S):
  h = 0
  for i in range(len(S)):
    if h + S[i][0] < 0:
      return -1
    else:
      h += S[i][1]
  return h

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

n, c = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
MOD = 10 ** 9 + 7

dp = [[0] * (c + 1) for i in range(n + 1)]
dp[0][0] = 1

for ni in range(n):
    for cnt in range(c + 1):
        ru = 0
        for x in range(a[ni], b[ni] + 1):
            ru += pow(x, cnt, MOD)
            ru %= MOD
        for ci in range(cnt, c + 1):
            dp[ni + 1][ci] += ru * dp[ni][ci - cnt] 
            dp[ni + 1][ci] %= MOD
print(dp[-1][-1])

### FIXED CODE ###

n, c = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
MOD = 10**9 + 7

dp = [[0]*(c+1) for i in range(n+1)]
dp[0][0] = 1

ruiseki = [[0] * (410) for _ in range(c+1)]
for i in range(c + 1):
    for j in range(409):
        ruiseki[i][j + 1] = ruiseki[i][j] + pow(j, i, MOD)
        ruiseki[i][j + 1] %= MOD
  
for i in range(n):
    for all_num in range(c + 1):
        for j in range(all_num + 1):
            # i番目の子供に、j個の飴を配る
            dp[i+1][all_num] += (ruiseki[j][b[i]+1] - ruiseki[j][a[i]]) * dp[i][all_num - j]
            dp[i+1][all_num] %= MOD
print(dp[-1][-1])
### BUGGY CODE ###

from bisect import bisect_left, bisect_right
import math
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()

def check(t):
    res = 0
    tr = math.sqrt(abs(t))
    for ai in a:
        if ai:
            aj = t // ai
            if ai > 0:
                res += bisect_right(a, aj)
            else:
                if t % ai:
                    res += n - bisect_right(a, aj)
                else:
                    res += n - bisect_left(a, aj)
        else:
            if t >= 0:
                res += n
        if t >= 0 and abs(ai) <= tr:
            res -= 1
    return res // 2


m = max(max(a)**2, min(a)**2)
l = -m
r = m

while r - l > 1:
    mid = (l + r) // 2
    if check(mid) < k:
        l = mid
    else:
        r = mid

if check(l) == k:
    print(l)
else:
    print(r)

### FIXED CODE ###

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

a.sort()

def check(t):
    j = n - 1 if t > 0 else 0
    res = 0
    f = 1

    cond = lambda x, t, f:x <= t if f * t > 0 or (t == 0 and f == -1) else x > t
    shift = lambda x, t:x-1 if t > 0 else x+1
    count = lambda x, n, f:n-x if f == 1 else x

    for ai in a:
        if f == 1 and ai > 0:
            f = -1
            j = n - 1 if t > 0 else 0
        if ai:
            while j >= 0 and j < n and cond(ai * a[j], t, f):
                j = shift(j, t)
            if t > 0:
                res += count(j+1, n, f)
            else:
                res += count(j, n, f)
        else:
            if t >= 0:
                res += n
        if ai * ai <= t:
            res -= 1
    return res // 2
            

m = max(max(a)**2, min(a)**2)
l = -m
r = m

while r - l > 1:
    mid = (l + r) // 2
    if check(mid) < k:
        l = mid
    else:
        r = mid

if check(l) == k:
    print(l)
else:
    print(r)
### BUGGY CODE ###

import sys
from itertools import accumulate

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def solve():
    n, k = nm()
    a = nl()
    for _ in range(k):
        b = [0]*n
        for i in range(n):
            if i > a[i]:
                b[i-a[i]] += 1
            else:
                b[0] += 1
            if i + a[i] + 1 < n:
                b[i + a[i] + 1] -= 1
        a = list(accumulate(b))
        if min(a) >= n:
            break
    print(*a)
    return

solve()


### FIXED CODE ###

import sys

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def solve():
    n, k = nm()
    if k > 45:
        k = 45
    a = nl()
    b = [0]*n
    for _ in range(k):
        for i in range(n):
            b[max(0, i - a[i])] += 1
            if i + a[i] + 1 < n:
                b[i + a[i] + 1] -= 1
        for i in range(n-1):
            b[i+1] += b[i]
            a[i] = 0
        a[-1] = 0
        b, a = a, b
    print(*a)
    return

solve()
### BUGGY CODE ###

while True:
    n = int(input())
    if n == 0:
        break
    inp = []
    for i in range(n):
        inp.append(list(input()))
    
    sum_dot = [[0 for i in range(n + 1)] for j in range(n + 1)]
    for y in range(n):
        for x in range(n):
            sum_dot[y + 1][x + 1] = sum_dot[y][x + 1] + inp[y][:x + 1].count(".")
    
    ans = 0
    for i in range(n)[::-1]:
        p = [(x, y) for y in range(n - i) for x in range(n - i)]
        for x, y in p:
            s = sum_dot[y + i + 1][x + i + 1] - sum_dot[y][x + i + 1] - sum_dot[y + i + 1][x] + sum_dot[y][x]
            if s == (i + 1)*(i + 1):
                ans = i + 1
                break
        else:
            continue
        break
    print(ans)



### FIXED CODE ###

while True:
    n = int(input())
    if n == 0:
        break
    inp = []
    for i in range(n):
        inp.append(list(input()))
    
    sq_max = [[0 for i in range(n + 1)] for j in range(n + 1)]
    
    for y in range(n):
        for x in range(n):
            if inp[y][x] == ".":
                sq_max[y + 1][x + 1] = min(sq_max[y][x + 1], sq_max[y + 1][x], sq_max[y][x]) + 1
            else:
                sq_max[y + 1][x + 1] = 0
    ans = max(map(max, sq_max))
    print(ans)