Mr K has a rectangular plot of land which may have marshes where fenceposts cannot be set. He wants you to find the perimeter of the largest rectangular fence that can be built on this land.

For example, in the following $m\times n=4\times4$ grid, $\boldsymbol{x}$ marks a marsh and $\boldsymbol{.}$ marks good land.

....
..x.
..x.
x...

If we number the rows and columns starting with $\mbox{1}$, we see that there are two main areas that can be fenced: $(1,1)-(3,2)$ and $(1,2)-(4,4)$.  The longest perimeter is $10$.  

Function Description

Complete the kMarsh function in the editor below.  It should print either an integer or impossible.

kMarsh has the following parameter(s):  

grid: an array of strings that represent the grid  

Input Format

The first line contains two space-separated integers $m$ and $n$, the grid rows and columns. 

Each of the next $m$ lines contains $n$ characters each describing the state of the land. 'x' (ascii value: 120) if it is a marsh and '.' ( ascii value:46) otherwise.  

Constraints

$2\leq m,n\leq500$ 

Output Format

Output contains a single integer - the largest perimeter. If the rectangular fence cannot be built, print impossible.

Sample Input 0

4 5
.....
.x.x.
.....
.....

Sample Output 0

14

Explanation 0  

The fence can be put up around the entire field. The perimeter is 
$2*(4-1)+2*(5-1)=14$.

Sample Input 1

2 2
.x
x.

Sample Output 1

impossible

Explanation 1

We need a minimum of 4 points to place the 4 corners of the fence. Hence, impossible. 

Sample Input 2

2 5
.....
xxxx.

Sample Output 2

impossible

Source: hackerrank | Difficulty: MEDIUM
Tags: Dynamic programming


Solutions:
import sys
(m, n) = map(int, sys.stdin.readline().split(' '))
land = []
for _ in range(m):
	l = sys.stdin.readline()
	land.append([0 if c == '.' else 1 for c in l])
next_free_below = [[-1] * n for _ in range(m)]
for i in range(n):
	last_free = m - 1
	for j in range(m - 1, -1, -1):
		if land[j][i] == 1:
			last_free = j - 1
		else:
			next_free_below[j][i] = last_free
	next_free_below[m - 1][i] = -1
next_free_right = [[-1] * n for _ in range(m)]
for i in range(m):
	last_free = n - 1
	for j in range(n - 1, -1, -1):
		if land[i][j] == 1:
			last_free = j - 1
		else:
			next_free_right[i][j] = last_free
	next_free_right[i][n - 1] = -1
max_so_far = 0
for i1 in range(m - 1):
	for j1 in range(n - 1):
		if land[i1][j1] == 1:
			continue
		for i2 in range(next_free_below[i1][j1], i1, -1):
			if 2 * (i2 - i1) + 2 * (next_free_right[i1][j1] - j1) < max_so_far:
				continue
			for j2 in range(next_free_right[i1][j1], j1, -1):
				if land[i1][j1] == 0 and land[i2][j2] == 0 and (next_free_below[i1][j1] >= i2) and (next_free_right[i1][j1] >= j2) and (next_free_below[i1][j2] >= i2) and (next_free_right[i2][j1] >= j2):
					max_so_far = max(max_so_far, 2 * (i2 - i1) + 2 * (j2 - j1))
print(max_so_far if max_so_far else 'impossible')


get_int = lambda : int(input())
get_list = lambda : [int(s) for s in input().split()]
(m, n) = get_list()
land = [list(input()) for _ in range(m)]
right = [[0] * n + [n] for _ in range(m)]
down = [[0] * n for _ in range(m)] + [[m] * n]
for i in reversed(range(m)):
	for j in reversed(range(n)):
		right[i][j] = j if land[i][j] == 'x' else right[i][j + 1]
		down[i][j] = i if land[i][j] == 'x' else down[i + 1][j]
res = 0
for bi in range(m):
	for bj in range(n):
		if land[bi][bj] == '.':
			for ej in range(bj + 1, right[bi][bj]):
				for ei in range(bi + 1, min(down[bi][bj], down[bi][ej])):
					if right[ei][bj] > ej:
						res = max(res, 2 * (ei + ej - bj - bi))
print(res or 'impossible')


from itertools import combinations, product
from bisect import *

def circumference(i1, j1, i2, j2):
	return 2 * (i2 - i1) + 2 * (j2 - j1)
(m, n) = map(int, input().split())
(mp, np) = ([[] for _ in range(m)], [[] for _ in range(n)])
for i in range(m):
	for (j, c) in enumerate(input()):
		if c == 'x':
			mp[i].append(j)
			np[j].append(i)
cm = -1

def bwrap(L, j, m):
	b = bisect_left(L, j)
	if b < len(L):
		return L[b] - 1
	return m
for i in range(0, m - 1):
	for j in range(0, n - 1):
		(v1, v2) = (bwrap(np[j], i, m - 1), bwrap(mp[i], j, n - 1))
		if v1 > i and v2 > j and (circumference(i, j, v1, v2) > cm):
			for vis in range(v1, i, -1):
				for vjs in range(v2, j, -1):
					(v1d, v2d) = (bwrap(np[vjs], i, m - 1), bwrap(mp[vis], j, n - 1))
					if v1d >= vis and v2d >= vjs:
						cm = max(circumference(i, j, vis, vjs), cm)
if cm == -1:
	print('impossible')
else:
	print(cm)


import sys

def cal_peri(x, y):
	return 2 * (x + y)

def combine_marshes(line1, line2):
	marsh_count = 0
	output = ['.'] * len(line1)
	for i in range(len(line2)):
		if line2[i] == 'x' or line1[i] == 'x':
			output[i] = 'x'
			marsh_count += 1
	return (output, marsh_count)

def dp(m, n, land):
	max_peri = 0
	for x1 in range(m - 1):
		internal_marshes = ['.'] * n
		for x2 in range(x1 + 1, m):
			(edge_marshes, edge_marsh_count) = combine_marshes(land[x1], land[x2])
			if edge_marsh_count == n:
				continue
			if x2 - x1 >= 2:
				(internal_marshes, internal_marsh_count) = combine_marshes(internal_marshes, land[x2 - 1])
				if internal_marsh_count == n:
					break
			cur_length = -1
			for i in range(n):
				if edge_marshes[i] == 'x':
					cur_length = -1
				else:
					cur_length += 1
					if cur_length == 0 and internal_marshes[i] == 'x':
						cur_length = -1
					if cur_length >= 1 and internal_marshes[i] != 'x':
						max_peri = max(max_peri, cal_peri(cur_length, x2 - x1))
	if max_peri > 0:
		return max_peri
	else:
		return 'impossible'
(m, n) = [int(x) for x in sys.stdin.readline().split()]
land = sys.stdin.read().splitlines()
for i in range(m):
	land[i] = [x for x in land[i]]
print(dp(m, n, land))


(m, n) = map(int, input().strip().split(' '))
land = []
for j in range(0, m):
	land.append(input())
fence = 0
for j in range(0, m - 1):
	for i in range(0, n - 1):
		if land[j][i] == '.' and land[j][i + 1] == '.' and (land[j + 1][i] == '.'):
			w = 1
			while i + w < n and land[j][i + w] == '.':
				h = 1
				while j + h < m and land[j + h][i] == '.' and (land[j + h][i + w] == '.'):
					check = 1
					for x in range(0, w):
						if land[j + h][i + x] != '.':
							check = 0
							break
					if check:
						l = 2 * w + 2 * h
						if l > fence:
							fence = l
					h = h + 1
				w = w + 1
if fence == 0:
	print('impossible')
else:
	print(fence)


def printArray(arr):
	for row in arr:
		print(' '.join(list(map(str, row))))
(h, w) = list(map(int, input().split()))
lis = [[False] * (w + 2)]
for _ in range(h):
	temp = input()
	temp = list(map(lambda c: True if c == '.' else False, temp))
	lis.append([False] + temp + [False])
lis.append([False] * (w + 2))
L = [[0] * (w + 2) for _ in range(h + 2)]
R = [[0] * (w + 2) for _ in range(h + 2)]
U = [[0] * (w + 2) for _ in range(h + 2)]
D = [[0] * (w + 2) for _ in range(h + 2)]
for y in range(1, h + 1):
	for x in range(1, w + 1):
		if not lis[y][x]:
			L[y][x] = -1
			U[y][x] = -1
		else:
			U[y][x] = U[y - 1][x] + 1 if lis[y - 1][x] else 0
			L[y][x] = L[y][x - 1] + 1 if lis[y][x - 1] else 0
for y in range(h, 0, -1):
	for x in range(w, 0, -1):
		if not lis[y][x]:
			R[y][x] = -1
			D[y][x] = -1
		else:
			D[y][x] = D[y + 1][x] + 1 if lis[y + 1][x] else 0
			R[y][x] = R[y][x + 1] + 1 if lis[y][x + 1] else 0
res = 0
for y1 in range(1, h):
	for x1 in range(1, w):
		if not lis[y1][x1]:
			continue
		bestCase1 = 2 * (D[y1][x1] - 1) + 2 * (R[y1][x1] - 1) + 4
		if bestCase1 < res:
			continue
		for y2 in range(y1 + D[y1][x1], y1, -1):
			for x2 in range(x1 + R[y1][x1], x1, -1):
				if not lis[y2][x2]:
					continue
				bestCase2 = 2 * (y2 - y1 - 1) + 2 * (x2 - x1 - 1) + 4
				if bestCase2 < res:
					continue
				dx = x2 - x1
				dy = y2 - y1
				if U[y2][x2] >= dy and L[y2][x2] >= dx:
					res = bestCase2
print(res if res > 0 else 'impossible')


def main():
	(N, M) = map(int, input().split())
	up = [[0 for i in range(M)] for n in range(N)]
	left = []
	land = [[x for x in input()] for i in range(N)]
	for i in range(N):
		left.append([0 for x in range(M)])
		for j in range(M):
			if j == 0:
				left[i][j] = 0 if land[i][j] != 'x' else -1
			elif land[i][j] == 'x':
				left[i][j] = -1
			else:
				left[i][j] = left[i][j - 1] + 1
	for i in range(M):
		for j in range(N):
			if j == 0:
				up[j][i] = 0 if land[j][i] != 'x' else -1
			elif land[j][i] == 'x':
				up[j][i] = -1
			else:
				up[j][i] = up[j - 1][i] + 1
	max_perimeter = -1
	for row in range(N - 1, 0, -1):
		for column in range(M - 1, 0, -1):
			for k in range(column - left[row][column], column):
				for temp in range(1, min(up[row][column], up[row][k]) + 1):
					if left[row - temp][column] >= column - k:
						max_perimeter = max(max_perimeter, 2 * (temp + column - k))
	print(max_perimeter if max_perimeter > 0 else 'impossible')
main()


import sys
import heapq

class LandMap:

	def __init__(self, width, height, lines):
		self.width = width
		self.height = height
		self.lines = lines

	def get(self, x, y):
		return self.lines[y][x]

	def set(self, x, y, val):
		self.lines[y][x] = val

	def print(self):
		for line in self.lines:
			print('\t'.join(map(str, line)))

def getLargestPerimeter(landMap):
	(rightMap, downMap) = getRunMaps(landMap)
	queue = []
	maxPossiblePerimeter = (landMap.width + landMap.height) * 2
	for row in range(landMap.height):
		for col in range(landMap.width):
			width = rightMap.get(col, row)
			height = downMap.get(col, row)
			if width > 0 and height > 0:
				perimeter = (width + height) * 2
				heapq.heappush(queue, (maxPossiblePerimeter - perimeter, col, row, width, height))
	while len(queue) > 0:
		(key, col, row, width, height) = heapq.heappop(queue)
		if tryRectangle(col, row, width, height, downMap, rightMap):
			return 2 * (width + height)
		else:
			if width > 1:
				heapq.heappush(queue, (key + 2, col, row, width - 1, height))
			if height > 1:
				heapq.heappush(queue, (key + 2, col, row, width, height - 1))
	return 'impossible'

def findRectangle(col, row, width, height, downMap, rightMap, minPerimeter):
	perimeter = 2 * width + 2 * height
	if perimeter > minPerimeter:
		if tryRectangle(col, row, width, height, downMap, rightMap):
			return perimeter
		elif perimeter > minPerimeter + 2:
			if height > 1:
				oneShorter = findRectangle(col, row, width, height - 1, downMap, rightMap, minPerimeter)
				if oneShorter is not None:
					return oneShorter
			if width > 1:
				oneNarrower = findRectangle(col, row, width - 1, height, downMap, rightMap, minPerimeter)
				if oneNarrower is not None:
					return oneNarrower
	return None

def tryRectangle(col, row, width, height, downMap, rightMap):
	return downMap.get(col + width, row) >= height and rightMap.get(col, row + height) >= width

def getRunMaps(landMap):
	rightMap = getEmptyMap(landMap.width, landMap.height)
	downMap = getEmptyMap(landMap.width, landMap.height)
	for row in range(landMap.height):
		for col in range(landMap.width):
			calculateRun(landMap, col, row, 'r', rightMap)
			calculateRun(landMap, col, row, 'd', downMap)
	return (rightMap, downMap)

def calculateRun(landMap, x, y, direction, runMap):
	if x >= landMap.width or y >= landMap.height:
		return -1
	elif landMap.get(x, y) == 'x':
		run = -1
	elif runMap.get(x, y) is not None:
		return runMap.get(x, y)
	elif direction == 'r':
		run = 1 + calculateRun(landMap, x + 1, y, direction, runMap)
	elif direction == 'd':
		run = 1 + calculateRun(landMap, x, y + 1, direction, runMap)
	runMap.set(x, y, run)
	return run

def getEmptyMap(width, height):
	lines = [[None for i in range(width)] for i in range(height)]
	return LandMap(width, height, lines)
lines = []
width = None
height = None
for line in sys.stdin:
	if width is None and height is None:
		(height, width) = map(int, line.split(' '))
	else:
		lines[len(lines):] = [line.strip()]
landMap = LandMap(width, height, lines)
print(getLargestPerimeter(landMap))


(n, m) = list(map(int, input().split(' ')))
lines = [input() for i in range(n)]
state = [[[0, 0] for j in range(m)] for i in range(n)]
for i in range(n):
	for j in range(m):
		if lines[i][j] == '.':
			top = state[i - 1][j][0] if i >= 1 else 0
			state[i][j][0] = 1 + top
			left = state[i][j - 1][1] if j >= 1 else 0
			state[i][j][1] = 1 + left
MIN_INF = float('-inf')
max_peri = MIN_INF
for i in range(n):
	for j in range(m):
		s = state[i][j]
		if s[1] * s[0] > max_peri:
			for x in range(j - s[1] + 1, j):
				for y in range(i - s[0] + 1, i):
					if state[i][x][0] >= i - y + 1 and state[y][j][1] >= j - x + 1:
						peri = 2 * (j - x) + 2 * (i - y)
						if peri > max_peri:
							max_peri = peri
						continue
if max_peri is MIN_INF:
	print('impossible')
else:
	print(max_peri)


import re
from itertools import chain

def main():
	(rows, cols) = [int(fld) for fld in input().split()]
	field = [input() for _ in range(rows)]
	assert all((len(row) == cols for row in field))
	print(bestperim(field[:400]))

def bestperim(field):
	fmt = ('{:0' + str(len(field[0])) + 'b}').format
	fnum = [int(''.join(('1' if c == '.' else '0' for c in row)), 2) for row in field]
	gappat = re.compile('\\.[\\.\\-]*\\.')
	ans = 0
	for (ia, a) in enumerate(fnum):
		allclear = a
		for (ib, b) in enumerate(fnum[ia + 1:]):
			allclear &= b
			kith = ''.join(('.' if ac == '1' else '-' if ab == '1' else '#' for (ac, ab) in zip(fmt(allclear), fmt(a & b))))
			bestgap = max(chain((0,), (len(gap) for gap in gappat.findall(kith)))) - 1
			if bestgap > 0:
				ans = max(ans, bestgap + ib + 1)
	return 2 * ans if ans > 0 else 'impossible'
main()


(N, M) = map(int, input().split())
up = [[0 for i in range(M)] for n in range(N)]
left = []
land = [[x for x in input()] for i in range(N)]
for i in range(N):
	left.append([0 for x in range(M)])
	for j in range(M):
		if j == 0:
			left[i][j] = 0 if land[i][j] != 'x' else -1
		elif land[i][j] == 'x':
			left[i][j] = -1
		else:
			left[i][j] = left[i][j - 1] + 1
for i in range(M):
	for j in range(N):
		if j == 0:
			up[j][i] = 0 if land[j][i] != 'x' else -1
		elif land[j][i] == 'x':
			up[j][i] = -1
		else:
			up[j][i] = up[j - 1][i] + 1
max_perimeter = -1
for row in range(N - 1, 0, -1):
	for column in range(M - 1, 0, -1):
		for k in range(column - left[row][column], column):
			for temp in range(1, min(up[row][column], up[row][k]) + 1):
				if left[row - temp][column] >= column - k:
					max_perimeter = max(max_perimeter, 2 * (temp + column - k))
print(max_perimeter if max_perimeter > 0 else 'impossible')


import sys
perimeter = 0
(n_row, n_col) = tuple([int(x) for x in input().strip().split()])
grid = []
for i in range(n_row):
	grid.append(input().strip())
pos_to_n_of_consec_down_dot = [[0] * (n_col + 1) for i in range(n_row + 1)]
pos_to_n_of_consec_right_dot = [[0] * (n_col + 1) for i in range(n_row + 1)]
for i in range(len(grid) - 1, -1, -1):
	for j in range(len(grid[i]) - 1, -1, -1):
		if grid[i][j] == '.':
			pos_to_n_of_consec_down_dot[i][j] = pos_to_n_of_consec_down_dot[i + 1][j] + 1
			pos_to_n_of_consec_right_dot[i][j] = pos_to_n_of_consec_right_dot[i][j + 1] + 1
		elif grid[i][j] == 'x':
			pos_to_n_of_consec_down_dot[i][j] = 0
			pos_to_n_of_consec_right_dot[i][j] = 0
for i in range(len(grid)):
	for j in range(len(grid[i])):
		if pos_to_n_of_consec_down_dot[i][j] < 2 or pos_to_n_of_consec_right_dot[i][j] < 2:
			continue
		i_inclim = i + pos_to_n_of_consec_down_dot[i][j]
		j_inclim = j + pos_to_n_of_consec_right_dot[i][j]
		for i2 in range(i, i_inclim + 1, 1):
			for j2 in range(j, j_inclim + 1, 1):
				if i + pos_to_n_of_consec_down_dot[i][j2] >= i2 + 1 and j + pos_to_n_of_consec_right_dot[i2][j] >= j2 + 1:
					if i2 != i and j2 != j and ((i2 - i) * 2 + (j2 - j) * 2 > perimeter):
						perimeter = (i2 - i) * 2 + (j2 - j) * 2
if perimeter > 0:
	print('{}'.format(perimeter))
else:
	print('impossible')


(m, n) = map(int, input().strip().split())
L = []
for _ in range(m):
	L.append(input())
perimeter = 0
up = [[-1 if L[0][j] == 'x' else 0 for j in range(n)]]
for i in range(1, m):
	up.append([-1 if L[i][j] == 'x' else up[i - 1][j] + 1 for j in range(n)])
left = []
for i in range(m):
	row = [-1] if L[i][0] == 'x' else [0]
	for j in range(1, n):
		row.append(-1 if L[i][j] == 'x' else row[j - 1] + 1)
	left.append(row)
for r2 in range(m - 1, 0, -1):
	for c2 in range(n - 1, 0, -1):
		if L[r2][c2] == 'x':
			continue
		r1 = r2 - 1
		c1 = c2 - 1
		limr1 = r2 - up[r2][c2]
		limc1 = c2 - left[r2][c2]
		while r1 >= limr1 and c1 >= limc1:
			if L[r1][c1] == 'x':
				r1 -= 1
				c1 = c2 - 1
				continue
			if up[r2][c1] >= r2 - r1 and left[r1][c2] >= c2 - c1:
				perimeter = max(perimeter, r2 + c2 - r1 - c1)
			if c1 == limc1:
				c1 = c2 - 1
				r1 -= 1
			else:
				c1 -= 1
if perimeter:
	print(2 * perimeter)
else:
	print('impossible')


def perimeter(r1, c1, r2, c2):
	return 2 * abs(r1 - r2) + 2 * abs(c1 - c2)

def bestPerimCorner(r, c, table):
	(up, left) = table[r][c]
	if 1 in (up, left):
		return 0
	ans = 0
	above_r = r - up + 1
	left_c = c - left + 1
	for row in range(above_r, r):
		leftExtent = c - table[row][c][1] + 1
		for col in range(left_c, c):
			upperExtent = r - table[r][col][0] + 1
			goodLeftEdge = leftExtent <= col
			goodTopEdge = upperExtent <= row
			if goodLeftEdge and goodTopEdge:
				ans = max(ans, perimeter(row, col, r, c))
				break
			pass
		pass
	return ans

def largestPerimeter(rows, cols, grid):
	ans = 0
	table = []
	for r in range(rows):
		table.append([])
		for c in range(cols):
			if grid[r][c] == 'x':
				table[r].append((0, 0))
			else:
				(up, left) = (1, 1)
				if r > 0:
					up = table[r - 1][c][0] + 1
				if c > 0:
					left = table[r][c - 1][1] + 1
				table[r].append((up, left))
				p = bestPerimCorner(r, c, table)
				ans = max(ans, p)
				pass
			pass
		pass
	return 'impossible' if ans == 0 else str(ans)
(rows, cols) = map(int, input().strip().split())
grid = []
for r in range(rows):
	grid.append(input().strip())
	pass
print(largestPerimeter(rows, cols, grid))
pass


(Y, X) = map(int, input().split())
mx = [[ch for ch in input()] for _ in range(Y)]
rrun = [[-1] * (X + 1) for _ in range(Y + 1)]
drun = [[-1] * (X + 1) for _ in range(Y + 1)]
for y in range(Y - 1, -1, -1):
	for x in range(X):
		if mx[y][x] == '.':
			drun[y][x] = drun[y + 1][x] + 1
		else:
			drun[y][x] = -1
for x in range(X - 1, -1, -1):
	for y in range(Y):
		if mx[y][x] == '.':
			rrun[y][x] = rrun[y][x + 1] + 1
		else:
			rrun[y][x] = -1
pmax = 0
for y in range(Y - 1):
	for x in range(X - 1):
		if mx[y][x] == '.':
			for w in range(2, rrun[y][x] + 2):
				for h in range(2, drun[y][x] + 2):
					if drun[y][x + w - 1] >= h - 1 and rrun[y + h - 1][x] >= w - 1:
						p = 2 * (w - 1 + h - 1)
						pmax = max(p, pmax)
print(pmax if pmax != 0 else 'impossible')


(m, n) = [int(x) for x in input().split()]
a = []
for i in range(m):
	a.append(input())
mp = 0
for i in range(m - 1):
	for j in range(n - 1):
		if a[i][j] == '.':
			mj = n
			for ii in range(i + 1, m):
				if mp >= 2 * (m - 1 - i + mj - 1 - j):
					break
				elif a[ii][j] == 'x':
					break
				else:
					for jj in range(j + 1, mj):
						if a[i][jj] == 'x':
							mj = jj
							break
						if a[ii][jj] == 'x':
							break
						else:
							valid = True
							for iii in range(i + 1, ii):
								if a[iii][jj] == 'x':
									valid = False
									break
							if valid:
								p = 2 * (ii - i + jj - j)
								if p > mp:
									mp = p
if mp == 0:
	print('impossible')
else:
	print(mp)


author = 'siddharth'
from itertools import combinations as com
(m, n) = map(int, input().split())
field = []
for _ in range(m):
	field.append(input())
max_perimeter = 0
for y in range(m):
	x = 0
	while x < n:
		while x < n and field[y][x] != '.':
			x += 1
		x1 = x
		while x < n and field[y][x] == '.':
			x += 1
		x2 = x - 1
		if not x2 > x1:
			continue
		for (ax, bx) in com(range(x1, x2 + 1), 2):
			for h in range(y + 1, m):
				if not 'x' in field[h][ax:bx + 1]:
					perimeter = 2 * (bx - ax) + 2 * (h - y)
					max_perimeter = max(perimeter, max_perimeter)
				if field[h][ax] == 'x' or field[h][bx] == 'x':
					break
for x in range(n):
	y = 0
	while y < m:
		while y < m and field[y][x] != '.':
			y += 1
		y1 = y
		while y < m and field[y][x] == '.':
			y += 1
		y2 = y - 1
		if not y2 > y1:
			continue
		for w in range(x + 1, n):
			if field[y1][w] == 'x' or field[y2][w] == 'x':
				break
			if not 'x' in [field[i][w] for i in range(y1, y2 + 1)]:
				perimeter = 2 * (y2 - y1) + 2 * (w - x)
				max_perimeter = max(perimeter, max_perimeter)
print(max_perimeter if max_perimeter > 0 else 'impossible')


from itertools import *
(M, N) = map(int, input().split())
grid = [[c == '.' for c in input()] for m in range(M)]
gridT = map(list, zip(*grid))
acc = lambda x, y: x + 1 if y else -1
left = [list(accumulate([0 if row[0] else -1] + row[1:], acc)) for row in grid]
up = [list(accumulate([0 if row[0] else -1] + row[1:], acc)) for row in gridT]
up = list(map(list, zip(*up)))
max_p = 0
for n in range(N - 1, -1, -1):
	for m in range(M - 1, -1, -1):
		if grid[m][n]:
			if left[m][n] > 0 and up[m][n] > 0:
				for l in range(n - left[m][n], n):
					for u in range(m - min(up[m][n], up[m][l]), m):
						if l >= n - left[u][n]:
							p = 2 * (n - l) + 2 * (m - u)
							if p > max_p:
								max_p = p
print(max_p if max_p != 0 else 'impossible')


def calPer(ug, lg, uc, bc):
	rec = True
	if bc[0] - ug[bc[0]][bc[1]] > uc[0]:
		rec = False
	if bc[1] - lg[uc[0]][bc[1]] > uc[1]:
		rec = False
	if bc[0] - ug[bc[0]][uc[1]] > uc[0]:
		rec = False
	if bc[1] - lg[bc[0]][bc[1]] > uc[1]:
		rec = False
	if rec:
		return 2 * (bc[0] - uc[0]) + 2 * (bc[1] - uc[1])
	else:
		return 0
(length, width) = [int(x) for x in input().split()]
dic = {}
fix = (0, 0)
move = (length - 1, width - 1)
grid = []
upGrid = [[0 for _ in range(width)] for _ in range(length)]
leftGrid = [[0 for _ in range(width)] for _ in range(length)]
for i in range(length):
	grid.append(list(input()))
for i in range(1, length):
	for j in range(width):
		if grid[i][j] == 'x':
			upGrid[i][j] = -1
		elif grid[i - 1][j] == 'x':
			upGrid[i][j] = 0
		else:
			upGrid[i][j] = upGrid[i - 1][j] + 1
for i in range(length):
	for j in range(1, width):
		if grid[i][j] == 'x':
			leftGrid[i][j] = -1
		elif grid[i][j - 1] == 'x':
			leftGrid[i][j] = 0
		else:
			leftGrid[i][j] = leftGrid[i][j - 1] + 1
answer = 0
for i in range(length - 1, -1, -1):
	for j in range(width - 1, -1, -1):
		if grid[i][j] == 'x':
			continue
		if 2 * (i + 1) + 2 * (j + 1) <= answer:
			continue
		for x in range(i - upGrid[i][j], i):
			for y in range(j - leftGrid[i][j], j):
				if grid[x][y] == 'x':
					continue
				answer = max(calPer(upGrid, leftGrid, (x, y), (i, j)), answer)
if answer > 0:
	print(answer)
else:
	print('impossible')


def create_marsh(n, m, obstacles):
	marsh_vert = [[0 for x in range(m)] for x in range(n)]
	marsh_hori = [[0 for x in range(m)] for x in range(n)]
	for i in range(n):
		for j in range(m):
			if obstacles[i][j] is False:
				if j > 0:
					marsh_hori[i][j] = marsh_hori[i][j - 1] + 1
				if i > 0:
					marsh_vert[i][j] = marsh_vert[i - 1][j] + 1
			else:
				marsh_vert[i][j] = -1
				marsh_hori[i][j] = -1
	return (marsh_hori, marsh_vert)

def calculate_perimeter(n, m, marsh_vert, marsh_hori, obstacles):
	max_perimeter = 0
	for start_i in range(n - 1, 0, -1):
		for start_j in range(m - 1, 0, -1):
			if obstacles[start_i][start_j] is True:
				continue
			up_stride = marsh_vert[start_i][start_j]
			left_stride = marsh_hori[start_i][start_j]
			if up_stride == 0 or left_stride == 0:
				continue
			top_left_i = start_i - up_stride
			top_left_j = start_j - left_stride
			local_max_found = False
			for i in range(top_left_i, start_i):
				for j in range(top_left_j, start_j):
					if obstacles[i][j] is True:
						continue
					down_sweep = marsh_vert[start_i][j]
					if down_sweep >= start_i - i:
						left_sweep = marsh_hori[i][start_j] - marsh_hori[i][j]
						if left_sweep >= start_j - j:
							l = start_j - j
							b = start_i - i
							perimeter = 2 * (l + b)
							max_perimeter = max(max_perimeter, perimeter)
							local_max_found = True
							break
	return max_perimeter
[n, m] = [int(x) for x in input().split()]
obstacles = [[] for x in range(n)]
for i in range(n):
	line = str(input())
	obstacles[i].extend([True if x == 'x' else False for x in line])
(hori, vert) = create_marsh(n, m, obstacles)
max_perimeter = calculate_perimeter(n, m, vert, hori, obstacles)
if max_perimeter == 0:
	print('impossible')
else:
	print(max_perimeter)


def first_row_before(lines, max_row, max_col):
	for i in range(max_row, 0, -1):
		if lines[i][max_col] == 'x':
			return i + 1
	return 0

def first_col_before(lines, max_row, max_col):
	for i in range(max_col, 0, -1):
		if lines[max_row][i] == 'x':
			return i + 1
	return 0

def perimeter_ok(lines, r, s, max_row, max_col):
	for i in range(r, max_row + 1):
		if lines[i][s] == 'x':
			return False
	for j in range(s, max_col + 1):
		if lines[r][j] == 'x':
			return False
	return True

def calc_perimeter(r, s, u, v):
	return 2 * (u - r + v - s)

def max_perimeter(lines, max_row, max_col):
	if max_row < 1 or max_col < 1:
		return 0
	if lines[max_row][max_col] == 'x' or lines[max_row - 1][max_col] == 'x' or lines[max_row][max_col - 1] == 'x':
		return 0
	min_row = first_row_before(lines, max_row, max_col)
	min_col = first_col_before(lines, max_row, max_col)
	best_perimeter = 0
	for r in range(min_row, max_row):
		for s in range(min_col, max_col):
			if best_perimeter < calc_perimeter(r, s, max_row, max_col):
				if perimeter_ok(lines, r, s, max_row, max_col):
					best_perimeter = calc_perimeter(r, s, max_row, max_col)
	return best_perimeter

def get_perimeter(lines):
	best_perimeter = 0
	for r in range(a - 1, 0, -1):
		for s in range(b - 1, 0, -1):
			if calc_perimeter(0, 0, r, s) <= best_perimeter:
				break
			best_perimeter = max(best_perimeter, max_perimeter(lines, r, s))
	return best_perimeter
(a, b) = map(int, input().split(' '))
lines = []
for i in range(int(a)):
	lines.append(list(input()))
perimeter = get_perimeter(lines)
if not perimeter:
	print('impossible')
else:
	print(perimeter)


(R, C) = tuple(map(int, input().split()))
iMap = [tuple(input()) for _ in range(R)]
Right = [[-1] * C for _ in range(R)]
Left = [[-1] * C for _ in range(R)]
Up = [[-1] * C for _ in range(R)]
Down = [[-1] * C for _ in range(R)]
for r in range(R):
	for c in range(C):
		if iMap[r][c] != 'x':
			if c > 0 and Right[r][c - 1] > 0:
				Right[r][c] = Right[r][c - 1] - 1
			else:
				count = 0
				for cr in range(c + 1, C):
					if iMap[r][cr] == 'x':
						break
					else:
						count += 1
				Right[r][c] = count
for r in range(R):
	for c in range(C):
		if iMap[r][c] == 'x':
			continue
		if r > 0 and Down[r - 1][c] > 0:
			Down[r][c] = Down[r - 1][c] - 1
		else:
			count = 0
			for rd in range(r + 1, R):
				if iMap[rd][c] == 'x':
					break
				else:
					count += 1
			Down[r][c] = count
for r in range(R):
	for c in range(C - 1, -1, -1):
		if iMap[r][c] == 'x':
			continue
		if c < C - 1 and Left[r][c + 1] > 0:
			Left[r][c] = Left[r][c + 1] - 1
		else:
			count = 0
			for cl in range(c - 1, -1, -1):
				if iMap[r][cl] == 'x':
					break
				else:
					count += 1
			Left[r][c] = count
for r in range(R - 1, -1, -1):
	for c in range(C):
		if iMap[r][c] == 'x':
			continue
		if r < R - 1 and Up[r + 1][c] > 0:
			Up[r][c] = Up[r + 1][c] - 1
		else:
			count = 0
			for ru in range(r - 1, -1, -1):
				if iMap[ru][c] == 'x':
					break
				else:
					count += 1
			Up[r][c] = count
maxLen = 0
for r in range(R):
	for c in range(C):
		if all([Right[r][c] > 0, Down[r][c] > 0, Right[r][c] * 2 + Down[r][c] * 2 > maxLen]):
			for cl in range(c + Right[r][c], c, -1):
				curDown = min(Down[r][cl], Down[r][c])
				if (cl - c) * 2 + curDown * 2 > maxLen:
					for ru in range(r + curDown, r, -1):
						if Left[ru][cl] >= cl - c:
							curLen = (ru - r) * 2 + (cl - c) * 2
							if curLen > maxLen:
								maxLen = curLen
								break
print(maxLen if maxLen > 0 else 'impossible')


(m, n) = map(int, input().strip().split())
L = []
for _ in range(m):
	L.append(input())
perimeter = 0
up = [[-1 if L[0][j] == 'x' else 0 for j in range(n)]]
for i in range(1, m):
	up.append([-1 if L[i][j] == 'x' else up[i - 1][j] + 1 for j in range(n)])
left = []
for i in range(m):
	row = [-1] if L[i][0] == 'x' else [0]
	for j in range(1, n):
		row.append(-1 if L[i][j] == 'x' else row[j - 1] + 1)
	left.append(row)
for r2 in range(m - 1, 0, -1):
	for c2 in range(n - 1, 0, -1):
		if L[r2][c2] == 'x':
			continue
		r1 = r2 - 1
		c1 = c2 - 1
		limr1 = r2 - up[r2][c2]
		limc1 = c2 - left[r2][c2]
		while r1 >= limr1 and c1 >= limc1:
			if L[r1][c1] == 'x':
				r1 -= 1
				c1 = c2 - 1
				continue
			if up[r2][c1] >= r2 - r1 and left[r1][c2] >= c2 - c1:
				perimeter = max(perimeter, r2 + c2 - r1 - c1)
			if c1 == limc1:
				c1 = c2 - 1
				r1 -= 1
			else:
				c1 -= 1
if perimeter:
	print(2 * perimeter)
else:
	print('impossible')


def change(x):
	return int(x == '.')

def per(x, y):
	return 2 * (x + y - 2)

def solution():
	(n, m) = map(int, input().split(' '))
	res = -1
	mx = -1
	mn = -1
	h = list()
	v = list()
	for i in range(n + 1):
		h.append([0 for i in range(m + 1)])
	for i in range(m + 1):
		v.append([0 for i in range(n + 1)])
	for i in range(1, n + 1):
		line = input()
		for j in range(1, m + 1):
			if line[j - 1] == '.':
				h[i][j] = h[i][j - 1] + 1
				v[j][i] = v[j][i - 1] + 1
				if h[i][j] > 1 and v[j][i] > 1:
					p = per(h[i][j], v[j][i])
					mx = max(p, mx)
					if mn == -1:
						mn = p
					else:
						mn = min(p, mn)
			else:
				h[i][j] = 0
				v[j][i] = 0
	N = range(1, n)
	M = range(1, m)
	l = int(mx / 2)
	if mx != -1:
		for a in N:
			p = per(n - a + 1, m)
			if res == mx or res >= p or mn > p:
				break
			for b in M:
				p = per(n - a + 1, m - b + 1)
				if res == mx or res >= p or mn > p:
					break
				if h[a][b]:
					x = n
					while x > a:
						p = per(x - a + 1, m - b + 1)
						while x > a and x - a + 1 > v[b][x]:
							x -= 1
						if x == a or res == mx or res >= p or (mn > p):
							break
						y = m
						d = l + a + b - x
						if d:
							y = min(m, d)
						while y > b:
							dx = x - a + 1
							dy = y - b + 1
							p = per(dx, dy)
							if res == mx or res >= p or mn > p:
								break
							if dy <= h[a][y] and dy <= h[x][y] and (dx <= v[y][x]):
								res = p
							y -= 1
						x -= 1
	if res != -1:
		print(res)
	else:
		print('impossible')
solution()


import sys
(M, N) = [int(x) for x in input().split()]
X = []
for m in range(M):
	line = input().strip()
	X.append([])
	for i in range(N):
		X[m].append([0, 0] if line[i] == '.' else [-1, -1])
for m in range(1, M):
	if X[m][0][0] == 0:
		X[m][0][0] = X[m - 1][0][0] + 1
for n in range(1, N):
	if X[0][n][1] == 0:
		X[0][n][1] = X[0][n - 1][1] + 1
for m in range(1, M):
	for n in range(1, N):
		if X[m][n][0] == -1:
			continue
		X[m][n][0] = X[m - 1][n][0] + 1
		X[m][n][1] = X[m][n - 1][1] + 1
p = 0
for m in range(1, M):
	for n in range(1, N):
		(r, c) = X[m][n]
		while r > 0 and c > 0 and (r + c > p):
			rr = min(r, X[m][n - c][0])
			cc = min(c, X[m - r][n][1])
			if rr == r and cc == c:
				pp = rr + cc
				if pp > p:
					p = pp
				break
			if rr * c >= r * cc:
				r -= 1
			else:
				c -= 1
if p > 1:
	print(p + p)
else:
	print('impossible')


(m, n) = [int(x) for x in input().strip().split()]
pic = list()
lr = list()
td = list()
for row in range(m):
	line = [1 if x == '.' else -1 for x in list(input().strip())]
	pic.append(line)
	sl = list()
	for j in range(n):
		if j == 0:
			sl.append(0 if line[j] > 0 else -1)
		elif line[j] > 0:
			sl.append(sl[j - 1] + 1)
		else:
			sl.append(-1)
	lr.append(sl)
	sl = list()
	if row == 0:
		sl = [0 if x > 0 else -1 for x in line]
	else:
		last = td[row - 1]
		for j in range(n):
			if line[j] > 0:
				sl.append(last[j] + 1)
			else:
				sl.append(-1)
	td.append(sl)
rlimit = list()
blimit = list()
for i in range(m - 1, -1, -1):
	rline = list()
	bline = list()
	for j in range(n - 1, -1, -1):
		if i == m - 1:
			bline.append(0 if pic[i][j] > 0 else -1)
		else:
			bline.insert(0, blimit[0][j] + 1 if pic[i][j] > 0 else -1)
		if j == n - 1:
			rline.append(0 if pic[i][j] > 0 else -1)
		else:
			rline.insert(0, rline[0] + 1 if pic[i][j] > 0 else -1)
	rlimit.insert(0, rline)
	blimit.insert(0, bline)
p = 0
for t in range(m - 1):
	l = -1
	while l <= n - 1 - p // 2 + (m - 1 - t) and l < n - 1:
		l += 1
		if pic[t][l] < 0:
			continue
		b = t + blimit[t][l] + 1
		while b > t + 1:
			b -= 1
			r = l + min(rlimit[t][l], rlimit[b][l]) + 1
			minr = max(l + 1, l + p // 2 - (b - t) + 1)
			while r > minr:
				r -= 1
				if r - lr[t][r] > l or r - lr[b][r] > l:
					break
				if b - td[b][r] > t:
					continue
				p = 2 * (b - t + r - l)
				minr = max(l + 1, l + p // 2 - (b - t) + 1)
print(p if p > 0 else 'impossible')


(m, n) = input().strip().split(' ')
(m, n) = [int(m), int(n)]
field = [[]] * m
for i in range(m):
	field[i] = list(input().strip())
left = [[0 for _ in range(n)] for _ in range(m)]
up = [[0 for _ in range(n)] for _ in range(m)]
for i in range(m):
	for j in range(n):
		if j > 0:
			left[i][j] = left[i][j - 1] + 1 if field[i][j - 1] == '.' else 0
		if i > 0:
			up[i][j] = up[i - 1][j] + 1 if field[i - 1][j] == '.' else 0
max_perimeter = 0
for i in range(1, m):
	for j in range(1, n):
		if field[i][j] == '.':
			a = i - up[i][j]
			b = 0
			while a < i and 2 * (i - a) + 2 * (j - b) > max_perimeter:
				b = max(j - left[a][j], j - left[i][j])
				while up[i][b] < i - a and b < j and (2 * (i - a) + 2 * (j - b) > max_perimeter):
					b += 1
				if b < j and left[i][j] >= j - b and (field[a][b] == '.'):
					max_perimeter = max(max_perimeter, 2 * (i - a) + 2 * (j - b))
				a += 1
				b = 0
print('impossible' if max_perimeter == 0 else max_perimeter)


class Solution:

	def __init__(self):
		self.data = []
		(self.rows, self.cols) = get_int_list(input())
		for i in range(self.rows):
			self.data.append([1 if val == '.' else 0 for val in input().strip()])
		self.up_left = [[[0, 0] for j in range(self.cols)] for i in range(self.rows)]
		self.max = None

	def calculate(self):
		for i in range(self.rows):
			if i % 5 == 0:
				a = 1
			for j in range(self.cols):
				if self.data[i][j]:
					if j > 0 and self.data[i][j - 1]:
						self.up_left[i][j][1] = self.up_left[i][j - 1][1] + 1
					if i > 0 and self.data[i - 1][j]:
						self.up_left[i][j][0] = self.up_left[i - 1][j][0] + 1
					self.spider(i, j)
		if self.max is None:
			return 'impossible'
		else:
			return self.max

	def spider(self, row, col):
		(up, left) = self.up_left[row][col]
		if up == 0 or left == 0:
			return
		if self.max is not None and get_perimeter(up, left) <= self.max:
			return
		a_row = row - up
		count = 0
		while a_row != row:
			a_left = self.up_left[a_row][col][1]
			if a_left != 0:
				first = self.get_a_up(row, col, row - a_row, min(left, a_left))
				if count == 0 and first:
					return
			a_row += 1
			count += 1

	def get_a_up(self, row, col, up, left):
		count = 0
		a_col = col - left
		if self.max is not None and get_perimeter(up, left) <= self.max:
			return
		while a_col != col:
			a_up = self.up_left[row][a_col][0]
			if a_up >= up:
				self.add_max(min(a_up, up), col - a_col)
				return count == 0
			count += 1
			a_col += 1

	def add_max(self, up, left):
		if up == 0 or left == 0:
			return
		perimeter = get_perimeter(up, left)
		if self.max is None or perimeter > self.max:
			self.max = perimeter

def get_perimeter(up, left):
	return 2 * up + 2 * left

def main():
	my_object = Solution()
	print(my_object.calculate())

def get_int_list(in_str):
	return [int(i) for i in in_str.strip().split()]
main()


import sys
import os
(m, n) = [int(q_temp) for q_temp in input().strip().split(' ')]
a = list()
hash = dict()
for i in range(m):
	l = input().strip()
	a.append(l)
max_perim = 0
max_points = [0, 0, 0, 0]
for i in range(m):
	if 2 * (m - i - 1) + 2 * (n - 1) < max_perim:
		continue
	for j in range(n):
		i1 = j
		if a[i][j] == 'x' or a[i][min(j + 1, n - 1)] == 'x' or a[i][min(j + 2, n - 1)] == 'x' or (j >= n - 1):
			continue
		if 2 * (m - i - 1) + 2 * (n - j - 1) < max_perim:
			continue
		i2 = n - 1
		str_top = a[i][i1:i2 + 1]
		while i2 > i1:
			str_top = a[i][i1:i2 + 1]
			if str_top.count('x') == 0 and 2 * (i2 - i1) + 2 * (m - i - 1) > max_perim:
				search = True
				depth = 1
				while search and i + depth < m:
					str = a[i + depth][i1:i2 + 1]
					if str.count('x') == 0:
						perim = 2 * (i2 - i1) + 2 * depth
						if perim > max_perim:
							max_perim = perim
							max_points[0] = i
							max_points[1] = i1
							max_points[2] = i2 - i1
							max_points[3] = depth + 1
					if a[i + depth][i1] == 'x' or a[i + depth][i2] == 'x':
						search = False
					depth += 1
			i2 -= 1
if max_perim > 0:
	print(max_perim)
else:
	print('impossible')


(Y, X) = map(int, input().strip().split())
FX = []
FY = []
FXMAX = []
FYMAX = [-1] * X
for y in range(Y):
	fx = []
	fy = []
	line = input().strip()
	cx = -1
	fxmax = -1
	for x in range(X):
		cy = 0 if y < 1 else FY[y - 1][x] + 1
		cx += 1
		if line[x] == 'x':
			(cx, cy) = (-1, -1)
		fxmax = max(cx, fxmax)
		FYMAX[x] = max(cy, FYMAX[x])
		fx.append(cx)
		fy.append(cy)
	FX.append(fx)
	FY.append(fy)
	FXMAX.append(fxmax)

def C(x, y):
	if x < 1 or y < 1:
		return 0
	for y0 in range(0, Y - y):
		x0 = 0
		y1 = y0 + y
		if FXMAX[y0] < x:
			continue
		if FXMAX[y1] < x:
			continue
		while x0 + x < X:
			x1 = x0 + x
			m = min(FX[y0][x1], FX[y1][x1])
			if m < x:
				x0 += x - m
				continue
			m = min(FY[y1][x0], FY[y1][x1])
			if m < y:
				x0 += 1
				continue
			return x + y
	return 0

def main():
	S = max(FXMAX) + max(FYMAX)
	for s in range(S, 0, -1):
		for x in range(min(s, X - 1), 0, -1):
			y = s - x
			if y > Y - 1:
				break
			res = C(x, y)
			if res:
				print(res * 2)
				return
	print('impossible')
main()


import itertools as it
(m, n) = [int(m) for m in input().strip().split()]
Arr = []
for i1 in range(m):
	Arr.append([True if m == '.' else False for m in input().strip()])
RightTravel = []
MaxWidth = 1
for i1 in Arr:
	RightTravel.append([])
	StartInd = 0
	Count = 0
	for (I2, i2) in enumerate(i1):
		if i2:
			Count += 1
		else:
			if Count > 0:
				if Count > MaxWidth:
					MaxWidth = Count
				for i3 in range(Count - 1, -1, -1):
					RightTravel[-1].append(i3)
			RightTravel[-1].append(None)
			StartInd = I2 + 1
			Count = 0
	if Count > 0 and i2:
		for i3 in range(Count - 1, -1, -1):
			RightTravel[-1].append(i3)
		if Count > MaxWidth:
			MaxWidth = Count
R = {}
PMax = None
for Width in range(MaxWidth - 1, 0, -1):
	PointSet = [(q, q + Width) for q in range(n - Width)]
	for i1 in PointSet:
		R[i1] = None
	for m1 in range(m):
		for AB in PointSet:
			if Arr[m1][AB[0]] and Arr[m1][AB[1]]:
				if R[AB] == None:
					if RightTravel[m1][AB[0]] != None and RightTravel[m1][AB[0]] >= AB[1] - AB[0]:
						R[AB] = 0
				else:
					R[AB] += 1
				if RightTravel[m1][AB[0]] != None and RightTravel[m1][AB[0]] >= AB[1] - AB[0]:
					if R[AB] != None and R[AB] > 0:
						PNew = R[AB] * 2 + 2 * (AB[1] - AB[0])
						if PMax == None or PNew > PMax:
							PMax = PNew
			else:
				R[AB] = None
	if PMax != None and 2 * (Width + m - 1) <= PMax:
		break
if PMax == None:
	print('impossible')
else:
	print(PMax)


class Point:

	def __init__(self, is_wall):
		self.is_wall = is_wall
		self.p_left = 0
		self.p_right = 0
		self.p_up = 0
		self.p_down = 0
		self.is_left = None
		self.is_right = None
		self.is_up = None
		self.is_down = None
		self.max_perimeter = 0

class Main:

	def __init__(self, inp):
		self.mat_raw = []
		self.mat = []
		self.max_fence_perimeter = 0
		inp = inp.split('\n')
		(self.m, self.n) = list(map(int, inp[0].strip().split(' ')))
		for i in range(self.m):
			line = inp[1:][i]
			nth = [True if x == 'x' else False for x in line]
			self.mat_raw.append(nth)

	def create_mat(self):
		self.mat = []
		for row_raw in self.mat_raw:
			row = []
			for column_element in row_raw:
				if column_element:
					row.append(Point(True))
				else:
					row.append(Point(False))
			self.mat.append(row)

	def update_is_wall(self):
		for i in range(self.m):
			for j in range(self.n):
				current_point = self.mat[i][j]
				if i == 0:
					current_point.is_up = True
				elif self.mat[i - 1][j].is_wall:
					current_point.is_up = True
				else:
					current_point.is_up = False
				if i == self.m - 1:
					current_point.is_down = True
				elif self.mat[i + 1][j].is_wall:
					current_point.is_down = True
				else:
					current_point.is_down = False
				if j == 0:
					current_point.is_left = True
				elif self.mat[i][j - 1].is_wall:
					current_point.is_left = True
				else:
					current_point.is_left = False
				if j == self.n - 1:
					current_point.is_right = True
				elif self.mat[i][j + 1].is_wall:
					current_point.is_right = True
				else:
					current_point.is_right = False
				if current_point.is_wall:
					current_point.is_left = True
					current_point.is_right = True
					current_point.is_up = True
					current_point.is_down = True

	def count_max_distance(self):
		for i in range(self.m):
			for j in range(self.n):
				current_point = self.mat[i][j]
				if not current_point.is_left:
					previous_point = self.mat[i][j - 1]
					prev_p_right = previous_point.p_right
					if current_point.is_wall:
						current_point.p_right = 0
					else:
						current_point.p_right = prev_p_right + 1
		for i in range(self.m):
			for j in range(self.n - 1, -1, -1):
				current_point = self.mat[i][j]
				if not current_point.is_right:
					previous_point = self.mat[i][j + 1]
					prev_p_left = previous_point.p_left
					if current_point.is_wall:
						current_point.p_left = 0
					else:
						current_point.p_left = prev_p_left + 1
		for j in range(self.n):
			for i in range(self.m):
				current_point = self.mat[i][j]
				if not current_point.is_up:
					previous_point = self.mat[i - 1][j]
					prev_p_down = previous_point.p_down
					if current_point.is_wall:
						current_point.p_down = 0
					else:
						current_point.p_down = prev_p_down + 1
		for j in range(self.n):
			for i in range(self.m - 1, -1, -1):
				current_point = self.mat[i][j]
				if not current_point.is_down:
					previous_point = self.mat[i + 1][j]
					prev_p_up = previous_point.p_up
					if current_point.is_wall:
						current_point.p_up = 0
					else:
						current_point.p_up = prev_p_up + 1

	def biggest_for_point(self):
		for i in range(self.m):
			for j in range(self.n):
				current_point = self.mat[i][j]
				if current_point.p_left > 0 and current_point.p_up > 0:
					max_per = 0
					best_possible_per = 2 * (current_point.p_up + 1 + (current_point.p_left + 1))
					if best_possible_per > self.max_fence_perimeter:
						for k in range(1, current_point.p_up + 1):
							for l in range(1, current_point.p_left + 1):
								f_point = self.mat[i + k][j + l]
								if f_point.p_right >= l and f_point.p_down >= k:
									per = 2 * (k + l)
									if per > max_per:
										max_per = per
										if per > self.max_fence_perimeter:
											self.max_fence_perimeter = per
						current_point.max_perimeter = max_per

	def print_mat_raw(self):
		string = '\n'.join([''.join([str(int(c)) for c in row]) for row in self.mat_raw])
		print('Raw matrix')
		print(string + '\n')

	@staticmethod
	def _print_surroundings(arr):
		string = '\n'.join([''.join([str(int(c)) for c in row]) for row in arr])
		print(string + '\n')

	def print_surroundings(self):
		print('----PRINTING SURROUNDINGS----\n')
		print('Left')
		arr = [[x.is_left for x in row] for row in self.mat]
		self._print_surroundings(arr)
		print('Right')
		arr = [[x.is_right for x in row] for row in self.mat]
		self._print_surroundings(arr)
		print('Up')
		arr = [[x.is_up for x in row] for row in self.mat]
		self._print_surroundings(arr)
		print('Down')
		arr = [[x.is_down for x in row] for row in self.mat]
		self._print_surroundings(arr)

	def print_cumulative_path(self):
		print('---- PRINTING CUMULATIVE PATH ----\n')
		print('Left')
		arr = [[x.p_left for x in row] for row in self.mat]
		self._print_surroundings(arr)
		print('Right')
		arr = [[x.p_right for x in row] for row in self.mat]
		self._print_surroundings(arr)
		print('Up')
		arr = [[x.p_up for x in row] for row in self.mat]
		self._print_surroundings(arr)
		print('Down')
		arr = [[x.p_down for x in row] for row in self.mat]
		self._print_surroundings(arr)

	def print_max_perimeter(self):
		print('---- PRINTING MAX PERIMETER ----\n---- ASSUME POINT IS TOP LEFT----\n')
		arr = [[x.max_perimeter for x in row] for row in self.mat]
		self._print_surroundings(arr)

	def show_result(self):
		if self.max_fence_perimeter:
			print(self.max_fence_perimeter)
		else:
			print('impossible')

	def run(self):
		self.create_mat()
		self.update_is_wall()
		self.count_max_distance()
		self.biggest_for_point()
		self.show_result()
lines = []
line = input()
(m, n) = line.strip().split(' ')
lines.append(line)
for i in range(int(m)):
	line = input()
	lines.append(line)
main = Main('\n'.join(lines))
main.run()


import sys
(m, n) = [int(x) for x in next(sys.stdin).strip().split(' ')]
grid = [line.strip() for line in sys.stdin]
max_dists_vert = {k: {} for k in range(m)}
max_dists_horiz = {k: {} for k in range(m)}
for i in range(m):
	max_dists_horiz[i][0] = 1 * (grid[i][0] == '.')
for j in range(n):
	max_dists_vert[0][j] = 1 * (grid[0][j] == '.')
for i in range(m):
	for j in range(n):
		not_marsh = grid[i][j] == '.'
		if i > 0:
			max_dists_vert[i][j] = max_dists_vert[i - 1][j] + 1 if not_marsh else 0
		if j > 0:
			max_dists_horiz[i][j] = max_dists_horiz[i][j - 1] + 1 if not_marsh else 0
(best_pair, best_pair_score) = (None, 0)
for i in range(m - 1, 0, -1):
	for j in range(n - 1, 0, -1):
		max_i = max_dists_vert[i][j]
		max_j = max_dists_horiz[i][j]
		if 2 * (max_i + max_j - 2) <= best_pair_score:
			continue
		for delta_i in range(max_i, 1, -1):
			for delta_j in range(max_j, 1, -1):
				if 2 * (delta_i + delta_j - 2) <= best_pair_score:
					continue
				(i2, j2) = (i - delta_i + 1, j - delta_j + 1)
				(p2_vert, p2_horiz) = (max_dists_vert[i][j2], max_dists_horiz[i2][j])
				if max_dists_vert[i][j2] >= delta_i and max_dists_horiz[i2][j] >= delta_j:
					pair = [(i, j), (i2, j2)]
					pair_score = 2 * (delta_i + delta_j - 2)
					if pair_score > best_pair_score:
						(best_pair, best_pair_score) = (pair, pair_score)
if best_pair_score == 0:
	print('impossible')
else:
	print(best_pair_score)


(m, n) = [int(w) for w in input().split()]
a = []
for _ in range(m):
	line = input().strip()
	row = [c == 'x' for c in line]
	a.append(row)
cd = [[0] * n for _ in range(m)]
for j in range(n):
	cd[-1][j] = -1 if a[-1][j] else 0
for i in range(m - 2, -1, -1):
	for j in range(n):
		if a[i][j]:
			cd[i][j] = -1
		elif cd[i + 1][j] != -1:
			cd[i][j] = cd[i + 1][j] + 1
cr = [[0] * n for _ in range(m)]
for i in range(m):
	cr[i][n - 1] = -1 if a[i][n - 1] else 0
for j in range(n - 2, -1, -1):
	for i in range(m):
		if a[i][j]:
			cr[i][j] = -1
		elif cr[i][j + 1] != -1:
			cr[i][j] = cr[i][j + 1] + 1
maxp = -1
for i in range(m):
	for j in range(n):
		if a[i][j]:
			continue
		maxh = cd[i][j] + 1
		if maxh > m - i:
			maxh = m - i
		maxw = cr[i][j] + 1
		if maxw > n - j:
			maxw = n - j
		if maxh + maxh + maxw + maxw - 4 <= maxp:
			continue
		minw = 2
		for h in range(maxh, 1, -1):
			for w in range(maxw, minw - 1, -1):
				p = w + w + h + h - 4
				if p > maxp:
					if cr[i + h - 1][j] + 1 >= w and cd[i][j + w - 1] + 1 >= h:
						maxp = p
print(maxp if maxp >= 0 else 'impossible')


import sys
fstd = 't0'

class Marshes(object):

	def __init__(self, r, c):
		self.X = []
		self.Rows = r
		self.Cols = c
		self.FL = []
		self.FT = []
		self.res = 0

	def addRow(self, x):
		X = self.X
		R = self.Rows
		C = self.Cols
		FL = self.FL
		FT = self.FT
		idx = len(X)
		X.append(list(map(lambda v: (0, 1)[v == 'x'], x)))
		FL.append([0] * C)
		FL[idx][0] = (0, -1)[X[idx][0] == 1]
		for i in range(1, C):
			FL[idx][i] = (FL[idx][i - 1] + 1, -1)[X[idx][i] == 1]
		FT.append([0] * C)
		if idx == 0:
			for i in range(C):
				FT[idx][i] = (0, -1)[X[idx][i] == 1]
		else:
			for i in range(C):
				FT[idx][i] = (FT[idx - 1][i] + 1, -1)[X[idx][i] == 1]
		res = self.res
		if idx > 0:
			r = idx
			for c in range(C - 1, 0, -1):
				if c + r <= res:
					break
				t = FL[r][c] + FT[r][c]
				if t < 2 or t <= res:
					continue
				for dc in range(FL[r][c], 0, -1):
					if dc + FT[r][c] <= res:
						break
					dr = min(FT[r][c], FT[r][c - dc])
					if dr + dc <= res:
						continue
					for ddr in range(dr, 0, -1):
						if FL[r - ddr][c] >= dc and ddr + dc > res:
							res = ddr + dc
							break
		self.res = res
		return res
(rows, cols) = map(int, input().strip().split(' '))
M = Marshes(rows, cols)
res = 0
for _ in range(rows):
	res = M.addRow(input().strip())
print(('impossible', res * 2)[res > 0])


(m, n) = map(int, input().split())
f = []
for i in range(m):
	f.append(list(map(lambda x: 1 if x == 'x' else 0, input())))
f_paths = [[[-1, -1, -1, -1] for i in range(n)] for j in range(m)]
for i in range(m):
	for j in range(n):
		if f[i][j]:
			path_len = 0
			for k in range(i + 1, m):
				if f[k][j]:
					break
				f_paths[k][j][0] = path_len
				path_len += 1
			path_len = 0
			for k in range(j + 1, n):
				if f[i][k]:
					break
				f_paths[i][k][1] = path_len
				path_len += 1
			path_len = 0
			for k in range(i - 1, -1, -1):
				if f[k][j]:
					break
				f_paths[k][j][2] = path_len
				path_len += 1
			path_len = 0
			for k in range(j - 1, -1, -1):
				if f[i][k]:
					break
				f_paths[i][k][3] = path_len
				path_len += 1
max_perimeter = 0
for i in range(0, m - 1):
	for j in range(0, n - 1):
		down_distance = f_paths[i][j][2] if f_paths[i][j][2] != -1 else m - i - 1
		right_distance = f_paths[i][j][3] if f_paths[i][j][3] != -1 else n - j - 1
		if f[i][j] or f[i][j + 1] or f[i + 1][j] or (down_distance * 2 + right_distance * 2 < max_perimeter):
			continue
		(k, l) = (i + 1, j + 1)
		while k < m and l < n:
			if f[k][j] or (f_paths[k][j][0] != -1 and f_paths[k][j][0] < k - i or (f_paths[i][l][1] != -1 and f_paths[i][l][1] < l - j)):
				break
			if f[k][l]:
				k += 1
				l += 1
				continue
			if f_paths[k][l][1] == -1 or f_paths[k][l][1] >= l - j:
				for y in range(l, n):
					if f[k][y] or f[i][y] or (f_paths[i][y][1] != -1 and f_paths[i][y][1] < y - j):
						break
					if f_paths[k][y][0] == -1 or f_paths[k][y][0] >= k - i:
						max_perimeter = max(max_perimeter, (k - i) * 2 + (y - j) * 2)
			k += 1
print(max_perimeter if max_perimeter else 'impossible')


(m, n) = list(map(int, input().strip().split(' ')))
location = []
for i in range(m):
	locationt = list(map(str, input().strip()))
	location.append(locationt)
prediction = [[[0, 0] for i in range(n + 1)] for j in range(m + 1)]
for i in range(n):
	for j in range(m):
		if location[m - 1 - j][n - 1 - i] == '.':
			prediction[m - 1 - j][n - 1 - i] = [prediction[m - j][n - i - 1][0] + 1, prediction[m - j - 1][n - i][1] + 1]
total = 0
for i1 in range(m - 1):
	for j1 in range(n - 1):
		i2max = i1 + prediction[i1][j1][0] - 1
		if location[i1][j1] == '.' and total < i2max - i1 + n - 1 - j1:
			for i2 in range(i1 + 1, i2max + 1):
				cond1 = prediction[i1][j1][1]
				cond2 = prediction[i2][j1][1]
				jmax = j1 + min(cond1, cond2) - 1
				j2max = i2 - i1 + jmax - j1 - total
				for j2 in range(min(min(cond1, cond2) - 1, j2max)):
					if location[i2][jmax - j2] == '.' and prediction[i1][jmax - j2][0] + i1 - 1 >= i2:
						total = i2 - i1 + jmax - j2 - j1
						break
if total == 0:
	print('impossible')
else:
	print(total * 2)


import os
import sys

def kMarsh(grid):
	n = len(grid)
	m = len(grid[0])
	res = 0
	for i1 in range(n - 1):
		is_corner = [land == '.' for land in grid[i1]]
		row1 = grid[i1]
		for i2 in range(i1 + 1, n):
			row2 = grid[i2]
			for j in range(m):
				if row2[j] != '.':
					is_corner[j] = False
			if True not in is_corner:
				break
			is_cell_land = False
			largest_land = 0
			land_start = -1
			last_land = -1
			for j in range(m):
				if is_corner[j]:
					last_land = j
					if not is_cell_land:
						is_cell_land = True
						land_start = j
				elif row2[j] == 'x' or row1[j] == 'x':
					if is_cell_land:
						is_cell_land = False
						if last_land - land_start > largest_land:
							largest_land = last_land - land_start
						land_start = -1
			if largest_land:
				next_res = largest_land + (i2 - i1)
				if next_res > res:
					res = next_res
	if not res:
		print('impossible')
	else:
		print(res * 2)
mn = input().split()
m = int(mn[0])
n = int(mn[1])
grid = []
for _ in range(m):
	grid_item = input()
	grid.append('x' + grid_item + 'x')
kMarsh(grid)


import os
import sys

def kMarsh(grid):
	ar1 = []
	a = []
	for j in range(len(grid[0])):
		t = []
		if j == 0:
			if grid[0][j] == '.':
				t.append(1)
			else:
				t.append(0)
		elif grid[0][j] == '.':
			t.append(a[j - 1][0] + 1)
		else:
			t.append(0)
		if grid[0][j] == '.':
			t.append(1)
		else:
			t.append(0)
		a.append(t)
	ar1.append(a)
	for i in range(1, len(grid)):
		a = []
		for j in range(len(grid[i])):
			t = []
			t2 = []
			if j == 0:
				if grid[i][j] == '.':
					t.append(1)
				else:
					t.append(0)
			elif grid[i][j] == '.':
				t.append(a[j - 1][0] + 1)
			else:
				t.append(0)
			if grid[i][j] == '.':
				t.append(ar1[i - 1][j][1] + 1)
			else:
				t.append(0)
			a.append(t)
		ar1.append(a)
	ma = 0
	for i in range(len(grid)):
		for j in range(len(grid[i])):
			if ar1[i][j][0] > 1 and ar1[i][j][1] > 1:
				x = ar1[i][j][0]
				y = ar1[i][j][1]
				siz = 2 * x + 2 * (y - 2)
				if ma < siz:
					for k in range(x - 1):
						sta = max((ma - 2 * (k + 2)) // 2 - 1, 0)
						for l in range(sta, y - 1):
							val = 1
							siz2 = 2 * (k + 2) + 2 * l
							if siz2 > ma:
								for m in range(k + 1):
									if grid[i - l - 1][j - m - 1] != '.':
										val = 0
								for m in range(l):
									if grid[i - m - 1][j - k - 1] != '.':
										val = 0
								if val == 1:
									ma = siz2
	if ma > 0:
		print(ma)
	else:
		print('impossible')
mn = input().split()
m = int(mn[0])
n = int(mn[1])
grid = []
for _ in range(m):
	grid_item = input()
	grid.append(grid_item)
kMarsh(grid)


import os
import sys

def kMarsh(grid):
	(n, m) = (len(grid), len(grid[0]))
	up = [[0 for _ in range(m)] for _ in range(n)]
	down = [[0 for _ in range(m)] for _ in range(n)]
	left = [[0 for _ in range(m)] for _ in range(n)]
	right = [[0 for _ in range(m)] for _ in range(n)]
	for i in range(n):
		s = 0
		for j in range(m):
			if grid[i][j] == '.':
				s += 1
			else:
				s = 0
			left[i][j] = s
	for i in range(n):
		s = 0
		for j in range(m - 1, -1, -1):
			if grid[i][j] == '.':
				s += 1
			else:
				s = 0
			right[i][j] = s
	for j in range(m):
		s = 0
		for i in range(n):
			if grid[i][j] == '.':
				s += 1
			else:
				s = 0
			up[i][j] = s
	for j in range(m):
		s = 0
		for i in range(n - 1, -1, -1):
			if grid[i][j] == '.':
				s += 1
			else:
				s = 0
			down[i][j] = s
	ma = 0
	for i in range(n):
		for j in range(m):
			if grid[i][j] == 'x':
				continue
			for p in range(i + down[i][j] - 1, i, -1):
				if 2 * (p - i + right[i][j] - 1) <= ma:
					break
				for q in range(j + right[i][j] - 1, j, -1):
					if grid[p][q] == 'x':
						continue
					if 2 * (p - i + q - j) <= ma:
						break
					if p - up[p][q] + 1 <= i and q - left[p][q] + 1 <= j:
						ma = max(ma, 2 * (p - i + q - j))
						break
	print(ma if ma else 'impossible')
mn = input().split()
m = int(mn[0])
n = int(mn[1])
grid = []
for _ in range(m):
	grid_item = input()
	grid.append(grid_item)
kMarsh(grid)


(m, n) = map(int, input().split(' '))

class Cell:

	def __init__(self, v):
		(self.u, self.l, self.v) = (-1 if v == 'x' else 0, -1 if v == 'x' else 0, v)
(D, rs) = ([[Cell(x) for x in input()] for i in range(m)], 1)
for j in range(1, n):
	if D[0][j].v != 'x' and D[0][j - 1].l != -1:
		D[0][j].l = D[0][j - 1].l + 1
for i in range(1, m):
	if D[i][0].v != 'x' and D[i - 1][0].u != -1:
		D[i][0].u = D[i - 1][0].u + 1
for i in range(1, m):
	for j in range(1, n):
		c = D[i][j]
		if c.v != 'x':
			if D[i - 1][j].v != 'x':
				c.u = D[i - 1][j].u + 1
			if D[i][j - 1].v != 'x':
				c.l = D[i][j - 1].l + 1
			ok = False
			for pq in range(c.u + c.l, rs, -1):
				for p in range(min(c.u, pq - 1), max(pq - c.l - 1, 0), -1):
					q = pq - p
					if q > c.l or q < 1:
						continue
					if D[i - p][j].l >= q and D[i][j - q].u >= p:
						rs = p + q
						ok = True
						break
				if ok:
					break
print(rs + rs if rs > 1 else 'impossible')


import os
import sys

def kMarsh(grid):
	m = len(grid)
	n = len(grid[0])
	ans = 0
	bush_row = []
	bush_col = []
	for i in range(m):
		(last_bush, row) = (-1, [])
		for j in range(n):
			if grid[i][j] == 'x':
				last_bush = j
			row.append(last_bush)
		bush_row.append(row)
	for i in range(n):
		(last_bush, col) = (-1, [])
		for j in range(m):
			if grid[j][i] == 'x':
				last_bush = j
			col.append(last_bush)
		bush_col.append(col)
	for x1 in range(m):
		if 2 * (m - 1 - x1 + n - 1) <= ans:
			break
		for y1 in range(n):
			if grid[x1][y1] == 'x':
				continue
			if 2 * (m - 1 - x1 + n - 1 - y1) <= ans:
				break
			for x2 in range(max(ans // 2 + x1 - n + 2 + y1, x1 + 1), m):
				if bush_col[y1][x2] >= x1:
					break
				for y2 in range(max(ans // 2 - x2 + x1 + y1 + 1, y1 + 1), n):
					if bush_row[x1][y2] < y1 and bush_row[x2][y2] < y1:
						if bush_col[y2][x2] < x1:
							ans = 2 * (x2 - x1 + y2 - y1)
					else:
						break
	if ans == 0:
		print('impossible')
	else:
		print(ans)
mn = input().split()
m = int(mn[0])
n = int(mn[1])
grid = []
for _ in range(m):
	grid_item = input()
	grid.append(grid_item)
kMarsh(grid)


from copy import copy
(rows, cols) = map(int, input().split())
field = [input() for _ in range(rows)]
bck = []
newrow = [[-1, -1]] * cols
for row in field:
	x = -1
	for (j, ch) in enumerate(row):
		if ch == '.':
			x += 1
			y = newrow[j][1] + 1
		else:
			(x, y) = (-1, -1)
		newrow[j] = (x, y)
	bck.append(copy(newrow))
fwd = []
newrow = [[-1, -1]] * cols
for row in reversed(field):
	x = -1
	for j in range(cols - 1, -1, -1):
		if row[j] == '.':
			x += 1
			y = newrow[j][1] + 1
		else:
			(x, y) = (-1, -1)
		newrow[j] = (x, y)
	fwd.append(copy(newrow))
fwd.reverse()
maxp = 1
for x1 in range(cols):
	for y1 in range(rows):
		(dx1, dy1) = fwd[y1][x1]
		if dx1 * dy1 > 0 and dx1 + dy1 > maxp:
			for x2 in range(x1 + 1, x1 + dx1 + 1):
				for y2 in range(y1 + 1 + max(0, maxp - x2 + x1), y1 + dy1 + 1):
					(dx2, dy2) = bck[y2][x2]
					if dx2 >= x2 - x1 and dy2 >= y2 - y1:
						maxp = x2 + y2 - x1 - y1
result = 'impossible' if maxp < 2 else 2 * maxp
print(result)


import os
import sys

def kMarsh(grid):
	rows = len(grid)
	columns = len(grid[0])
	(emptyInRow, emptyInColumn) = emptyCellDict(grid, rows, columns)
	maximalPerimeter = 0
	for row in range(rows):
		for column in range(columns):
			newPerimeter = checkSquare(emptyInRow, emptyInColumn, row, column, maximalPerimeter)
			if newPerimeter >= maximalPerimeter:
				maximalPerimeter = newPerimeter
	if maximalPerimeter == 0:
		print('impossible')
	else:
		print(maximalPerimeter)

def checkSquare(emptyInRow, emptyInColumn, startRow, startColumn, currentMax):
	if emptyInColumn[startRow][startColumn] * 2 + emptyInRow[startRow][startColumn] * 2 < currentMax:
		return currentMax
	maximalPerimeter = 0
	for checkRow in range(1, emptyInColumn[startRow][startColumn]):
		maximalColumn = min(emptyInRow[startRow][startColumn], emptyInRow[startRow + checkRow][startColumn])
		for checkColumn in range(1, maximalColumn):
			if emptyInColumn[startRow][startColumn + checkColumn] >= checkRow:
				newPerimeter = 2 * (startRow + checkRow + 1 - startRow) + 2 * (startColumn + 1 + checkColumn - startColumn) - 4
				if newPerimeter > maximalPerimeter:
					maximalPerimeter = newPerimeter
	return maximalPerimeter

def emptyCellDict(grid, rows, columns):
	emptyInRow = [[0 for i in range(columns)] for j in range(rows)]
	emptyInColumn = [[0 for i in range(columns)] for j in range(rows)]
	for row in range(rows):
		for column in range(columns):
			if grid[row][column] == '.':
				if column == 0:
					emptyInRow[row][column] = previousColumnBlocked(grid, columns, row, column)
				elif grid[row][column - 1] == '.':
					emptyInRow = previousColumnEmpty(grid, emptyInRow, row, column)
				else:
					emptyInRow[row][column] = previousColumnBlocked(grid, columns, row, column)
				if row == 0:
					emptyInColumn[row][column] = previousRowBlocked(grid, row, column, rows)
				elif grid[row - 1][column] == '.':
					emptyInColumn = previousRowEmpty(grid, emptyInColumn, row, column)
				else:
					emptyInColumn[row][column] = previousRowBlocked(grid, row, column, rows)
	return (emptyInRow, emptyInColumn)

def previousRowEmpty(grid, emptyInColumn, row, column):
	emptyInColumn[row][column] = emptyInColumn[row - 1][column] - 1
	return emptyInColumn

def previousRowBlocked(grid, row, column, rows):
	numberFollowingEmpty = 0
	for followingRows in range(row, rows):
		if grid[followingRows][column] == '.':
			numberFollowingEmpty += 1
		else:
			return numberFollowingEmpty
	return numberFollowingEmpty

def previousColumnEmpty(grid, emptyInRow, row, column):
	emptyInRow[row][column] = emptyInRow[row][column - 1] - 1
	return emptyInRow

def previousColumnBlocked(grid, columns, row, column):
	if column != columns:
		numberFollowingEmpty = 0
	else:
		return 1
	for followingColumns in range(column, columns):
		if grid[row][followingColumns] == '.':
			numberFollowingEmpty += 1
		else:
			return numberFollowingEmpty
	return numberFollowingEmpty
mn = input().split()
m = int(mn[0])
n = int(mn[1])
grid = []
for _ in range(m):
	grid_item = input()
	grid.append(grid_item)
kMarsh(grid)


import os
import sys
(m, n) = [int(x) for x in next(sys.stdin).strip().split(' ')]
grid = [line.strip() for line in sys.stdin]
max_dists_vert = {k: {} for k in range(m)}
max_dists_horiz = {k: {} for k in range(m)}
for i in range(m):
	max_dists_horiz[i][0] = 1 * (grid[i][0] == '.')
for j in range(n):
	max_dists_vert[0][j] = 1 * (grid[0][j] == '.')
for i in range(m):
	for j in range(n):
		not_marsh = grid[i][j] == '.'
		if i > 0:
			max_dists_vert[i][j] = max_dists_vert[i - 1][j] + 1 if not_marsh else 0
		if j > 0:
			max_dists_horiz[i][j] = max_dists_horiz[i][j - 1] + 1 if not_marsh else 0
(best_pair, best_pair_score) = (None, 0)
for i in range(m - 1, 0, -1):
	for j in range(n - 1, 0, -1):
		max_i = max_dists_vert[i][j]
		max_j = max_dists_horiz[i][j]
		if 2 * (max_i + max_j - 2) <= best_pair_score:
			continue
		for delta_i in range(max_i, 1, -1):
			for delta_j in range(max_j, 1, -1):
				if 2 * (delta_i + delta_j - 2) <= best_pair_score:
					continue
				(i2, j2) = (i - delta_i + 1, j - delta_j + 1)
				(p2_vert, p2_horiz) = (max_dists_vert[i][j2], max_dists_horiz[i2][j])
				if max_dists_vert[i][j2] >= delta_i and max_dists_horiz[i2][j] >= delta_j:
					pair = [(i, j), (i2, j2)]
					pair_score = 2 * (delta_i + delta_j - 2)
					if pair_score > best_pair_score:
						(best_pair, best_pair_score) = (pair, pair_score)
if best_pair_score == 0:
	print('impossible')
else:
	print(best_pair_score)


import os
import sys
(m, n) = [int(x) for x in next(sys.stdin).strip().split(' ')]
grid = [line.strip() for line in sys.stdin]
max_dists_vert = {k: {} for k in range(m)}
max_dists_horiz = {k: {} for k in range(m)}
for i in range(m):
	max_dists_horiz[i][0] = 1 * (grid[i][0] == '.')
for j in range(n):
	max_dists_vert[0][j] = 1 * (grid[0][j] == '.')
for i in range(m):
	for j in range(n):
		not_marsh = grid[i][j] == '.'
		if i > 0:
			max_dists_vert[i][j] = max_dists_vert[i - 1][j] + 1 if not_marsh else 0
		if j > 0:
			max_dists_horiz[i][j] = max_dists_horiz[i][j - 1] + 1 if not_marsh else 0
(best_pair, best_pair_score) = (None, 0)
for i in range(m - 1, 0, -1):
	for j in range(n - 1, 0, -1):
		max_i = max_dists_vert[i][j]
		max_j = max_dists_horiz[i][j]
		if 2 * (max_i + max_j - 2) <= best_pair_score:
			continue
		for delta_i in range(max_i, 1, -1):
			for delta_j in range(max_j, 1, -1):
				if 2 * (delta_i + delta_j - 2) <= best_pair_score:
					continue
				(i2, j2) = (i - delta_i + 1, j - delta_j + 1)
				(p2_vert, p2_horiz) = (max_dists_vert[i][j2], max_dists_horiz[i2][j])
				if max_dists_vert[i][j2] >= delta_i and max_dists_horiz[i2][j] >= delta_j:
					pair = [(i, j), (i2, j2)]
					pair_score = 2 * (delta_i + delta_j - 2)
					if pair_score > best_pair_score:
						(best_pair, best_pair_score) = (pair, pair_score)
if best_pair_score == 0:
	print('impossible')
else:
	print(best_pair_score)


import os
import sys

def matrix_helper(m, n, grid):
	down_mat = [[-1 for j in range(n)] for i in range(m)]
	right_mat = [[-1 for j in range(n)] for i in range(m)]
	grid_z = list(zip(*grid))
	grid_t = []
	for row in grid_z:
		grid_t.append(''.join(row))
	if grid[0][0] == 'x':
		pass
	else:
		ind = grid_t[0][1:m].find('x')
		if ind != -1:
			count = ind
		else:
			count = m - 1
		down_mat[0][0] = count
		ind = grid[0][1:n].find('x')
		if ind != -1:
			count = ind
		else:
			count = n - 1
		right_mat[0][0] = count
	for i in range(1, m):
		prev_count = down_mat[i - 1][0]
		if prev_count > 0:
			down_mat[i][0] = prev_count - 1
		elif prev_count == 0:
			pass
		else:
			ind = grid_t[0][i + 1:m].find('x')
			if ind != -1:
				count = ind
			else:
				count = m - i - 1
			down_mat[i][0] = count
		ind = grid[i][1:n].find('x')
		if ind != -1:
			count = ind
		else:
			count = n - 1
		right_mat[i][0] = count
	for j in range(1, n):
		prev_count = right_mat[0][j - 1]
		if prev_count > 0:
			right_mat[0][j] = prev_count - 1
		elif prev_count == 0:
			pass
		else:
			ind = grid[0][j + 1:n].find('x')
			if ind != -1:
				count = ind
			else:
				count = n - j - 1
			right_mat[0][j] = count
		ind = grid_t[j][1:m].find('x')
		if ind != -1:
			count = ind
		else:
			count = m - 1
		down_mat[0][j] = count
	for i in range(1, m):
		for j in range(1, n):
			if grid[i][j] == 'x':
				continue
			prev_count = down_mat[i - 1][j]
			if prev_count > 0:
				down_mat[i][j] = prev_count - 1
			else:
				ind = grid_t[j][i + 1:m].find('x')
				if ind != -1:
					count = ind
				else:
					count = m - i - 1
				down_mat[i][j] = count
			prev_count = right_mat[i][j - 1]
			if prev_count > 0:
				right_mat[i][j] = prev_count - 1
			else:
				ind = grid[i][j + 1:n].find('x')
				if ind != -1:
					count = ind
				else:
					count = n - j - 1
				right_mat[i][j] = count
	return (down_mat, right_mat)

def kMarsh(m, n, down_mat, right_mat):
	max_rect = 0
	for i in range(m - 1):
		for j in range(n - 1):
			for r in range(max(1, int(max_rect / 2 - n + 1)), right_mat[i][j] + 1):
				if down_mat[i][j + r] <= 0:
					continue
				for d in range(max(1, int(max_rect / 2 - r)), down_mat[i][j] + 1):
					if right_mat[i + d][j] <= 0:
						continue
					if right_mat[i + d][j] >= r and down_mat[i][j + r] >= d:
						new_rect = 2 * (r + d)
						if new_rect > max_rect:
							max_rect = new_rect
					else:
						continue
	if max_rect != 0:
		print(max_rect)
	else:
		print('impossible')
mn = input().split()
m = int(mn[0])
n = int(mn[1])
grid = []
for _ in range(m):
	grid_item = input()
	grid.append(grid_item)
has_marsh = False
for row in grid:
	if row.find('x') != -1:
		has_marsh = True
		break
if not has_marsh:
	print(2 * (n + m - 2))
else:
	(down_mat, right_mat) = matrix_helper(m, n, grid)
	kMarsh(m, n, down_mat, right_mat)


import os
import sys

def kMarsh(grid):
	n = len(grid)
	m = len(grid[0])
	left = [[0] * m for _ in range(n)]
	up = [[0] * m for _ in range(n)]
	right = [[0] * m for _ in range(n)]
	down = [[0] * m for _ in range(n)]
	for i in range(n):
		if grid[i][0] == '.':
			left[i][0] = 1
		for j in range(1, m):
			if grid[i][j] == '.':
				left[i][j] = left[i][j - 1] + 1
	for j in range(m):
		if grid[0][j] == '.':
			up[0][j] = 1
		for i in range(1, n):
			if grid[i][j] == '.':
				up[i][j] = up[i - 1][j] + 1
	for i in range(n):
		if grid[i][m - 1] == '.':
			right[i][m - 1] = 1
		for j in range(m - 2, -1, -1):
			if grid[i][j] == '.':
				right[i][j] = right[i][j + 1] + 1
	for j in range(m):
		if grid[n - 1][j] == '.':
			down[n - 1][j] = 1
		for i in range(n - 2, -1, -1):
			if grid[i][j] == '.':
				down[i][j] = down[i + 1][j] + 1
	ans = 0
	for i in range(n):
		for j in range(m):
			if grid[i][j] == 'x':
				continue
			if (right[i][j] + down[i][j] - 2) * 2 <= ans:
				continue
			for p in range(i + down[i][j] - 1, i, -1):
				if (p - i + right[i][j] - 1) * 2 <= ans:
					break
				for q in range(j + right[i][j] - 1, j, -1):
					if grid[p][q] == 'x':
						continue
					if (p - i + q - j) * 2 <= ans:
						break
					if p - i <= up[p][q] - 1 and q - j <= left[p][q] - 1:
						ans = max(ans, (p - i + q - j) * 2)
						break
	print(ans if ans else 'impossible')
mn = input().split()
m = int(mn[0])
n = int(mn[1])
grid = []
for _ in range(m):
	grid_item = input()
	grid.append(grid_item)
kMarsh(grid)


import os
import sys

def kMarsh(Nrows, Ncols, grid):
	ups = [[-1] * (Ncols + 1) for _ in range(Nrows + 1)]
	left = [[-1] * (Ncols + 1) for _ in range(Nrows + 1)]
	for r in range(Nrows):
		for c in range(Ncols):
			if grid[r][c] == '.':
				ups[r + 1][c + 1] = ups[r][c + 1] + 1
				left[r + 1][c + 1] = left[r + 1][c] + 1
	rv = 1
	for r in range(Nrows, 0, -1):
		for c in range(Ncols, 0, -1):
			if r * c <= rv:
				break
			vu = ups[r][c]
			vl = left[r][c]
			if vu + vl > rv:
				for i in range(vu, 0, -1):
					vl2 = min(vl, left[r - i][c])
					if i + vl2 > rv:
						for j in range(vl2, 0, -1):
							if ups[r][c - j] >= i:
								if i + j > rv:
									rv = i + j
	if rv == 1:
		print('impossible')
	else:
		print(str(2 * rv))
mn = input().split()
Nrows = int(mn[0])
Ncols = int(mn[1])
grid = []
for _ in range(Nrows):
	grid_item = input()
	grid.append(grid_item)
kMarsh(Nrows, Ncols, grid)


import os
import sys

def compPer(x, y):
	if x == y == 0:
		return 0
	if x == 1:
		return y
	elif y == 1:
		return x
	return 2 * x + 2 * y - 4

def kMarsh(grid, m, n):
	perMax = 0
	upM = [[-1] * n for i in range(m)]
	lfM = [[-1] * n for i in range(m)]
	for i in range(m):
		for j in range(n):
			if grid[i][j] == 'x':
				upM[i][j] = lfM[i][j] = -1
			else:
				if i == 0:
					upM[i][j] = 0
				else:
					upM[i][j] = upM[i - 1][j] + 1
				if j == 0:
					lfM[i][j] = 0
				else:
					lfM[i][j] = lfM[i][j - 1] + 1
	for i in range(m):
		for j in range(n):
			if grid[i][j] != 'x':
				if compPer(upM[i][j] + 1, lfM[i][j] + 1) <= perMax:
					continue
				for ii in range(upM[i][j], -1, -1):
					for jj in range(lfM[i][j], -1, -1):
						if compPer(ii + 1, jj + 1) <= perMax:
							break
						leftUpa = lfM[i - ii][j]
						upLefta = upM[i][j - jj]
						if leftUpa >= jj and upLefta >= ii and (ii > 0 and jj > 0):
							perMax = max(perMax, compPer(ii + 1, jj + 1))
	if perMax > 1:
		print(perMax)
		return
	print('impossible ')
mn = input().split()
m = int(mn[0])
n = int(mn[1])
grid = []
for _ in range(m):
	grid_item = input()
	grid.append(grid_item)
kMarsh(grid, m, n)


import os
import sys

def generer_matrices(grid):
	n = len(grid)
	m = len(grid[0])
	left = []
	for i in range(n):
		left.append([])
		left[i].append(-1 if grid[i][0] == 'x' else 0)
		for j in range(1, m):
			left[i].append(-1 if grid[i][j] == 'x' else left[i][-1] + 1)
	up = [[0] * m for _ in range(n)]
	for j in range(m):
		up[0][j] = -1 if grid[0][j] == 'x' else 0
		for i in range(1, n):
			up[i][j] = -1 if grid[i][j] == 'x' else up[i - 1][j] + 1
	return (left, up)

def kMarsh(grid):
	(left, up) = generer_matrices(grid)
	maxi = -1
	for i in range(len(grid) - 1, -1, -1):
		for j in range(len(grid[0]) - 1, -1, -1):
			hauteur = up[i][j]
			while hauteur > 0:
				if 2 * (hauteur + m) < maxi:
					break
				if grid[i - hauteur][j] != 'x':
					largeur = min(left[i][j], left[i - hauteur][j])
					while largeur > 0:
						if grid[i][j - largeur] != 'x' and grid[i - hauteur][j - largeur] != 'x':
							if up[i][j - largeur] >= hauteur:
								maxi = max(maxi, 2 * (hauteur + largeur))
						largeur -= 1
				hauteur -= 1
	if maxi >= 0:
		print(maxi)
	else:
		print('impossible')
mn = input().split()
m = int(mn[0])
n = int(mn[1])
grid = []
for _ in range(m):
	grid_item = input()
	grid.append(grid_item)
kMarsh(grid)


import os
import sys

def kMarsh(grid):
	left = []
	upp = []
	up = []
	for i in range(len(grid)):
		t = []
		p = -1
		for j in range(len(grid[0])):
			if grid[i][j] == '.':
				p += 1
			else:
				p = -1
			t.append(p)
		left.append(t)
	for j in range(len(grid[0])):
		t = []
		p = -1
		for i in range(len(grid)):
			if grid[i][j] == '.':
				p += 1
			else:
				p = -1
			t.append(p)
		upp.append(t)
	for i in range(len(grid)):
		t = []
		for j in range(len(grid[0])):
			t.append(upp[j][i])
		up.append(t)
	x = 3
	for ii in range(len(grid)):
		for jj in range(len(grid[0])):
			i = len(grid) - 1 - ii
			j = len(grid[0]) - 1 - jj
			if left[i][j] > 0 and up[i][j] > 0:
				for k in range(max(1, x // 2 - left[i][j] + 1), up[i][j] + 1):
					for l in range(max(1, x // 2 - k + 1), left[i][j] + 1):
						if left[i - k][j] >= l and up[i][j - l] >= k:
							x = 2 * (k + l)
	if x == 3:
		print('impossible')
	else:
		print(str(x))
mn = input().split()
m = int(mn[0])
n = int(mn[1])
grid = []
for _ in range(m):
	grid_item = input()
	grid.append(grid_item)
kMarsh(grid)


def solve(grid, n, m):
	upper = [[-1 for i in range(n)] for k in range(m)]
	left = [[-1 for i in range(n)] for k in range(m)]
	for j in range(n):
		current = 0
		for k in range(m):
			if ord(grid[k][j]) == 46:
				upper[k][j] = current
				current += 1
			else:
				current = 0
	for j in range(m):
		current = 0
		for i in range(n):
			if ord(grid[j][i]) == 46:
				left[j][i] = current
				current += 1
			else:
				current = 0
	best = -1
	for i in range(m - 1, -1, -1):
		for j in range(n - 1, -1, -1):
			max_left = left[i][j]
			max_up = upper[i][j]
			for w in range(i - max_up, i):
				x = 0
				k = False
				while x < max_left and w - x >= i - max_up:
					c = 2 * (i - w + max_left)
					if c < best:
						k = True
						break
					if upper[i][j - max_left + x] >= i - w + x and left[w - x][j] >= max_left - x:
						if c > best:
							best = c
							k = True
							break
					x += 1
				if k:
					break
			if not k:
				for l in range(j - max_left + 1, j):
					x = 0
					r = False
					while l + x < j and 1 + x <= max_up:
						c = 2 * (j - l + 1)
						if c < best:
							r = True
							break
						if upper[i][l + x] >= x + 1 and left[i - 1 - x][j] >= j - l - x:
							if c > best:
								best = c
								r = True
								break
						x += 1
					if r:
						break
	return best

def main():
	(m, n) = [int(x) for x in input().split()]
	grid = []
	for _ in range(m):
		grid_item = input()
		grid.append(grid_item)
	res = solve(grid, n, m)
	if res == -1:
		print('impossible')
	else:
		print(res)
main()


import os
import sys

def kMarsh(grid):
	m = len(grid)
	n = len(grid[0])
	a = [[0 for x in range(n + 1)] for y in range(m + 1)]
	down = [[0 for x in range(n + 1)] for y in range(m + 1)]
	right = [[0 for x in range(n + 1)] for y in range(m + 1)]
	for i in range(0, m):
		for j in range(0, n):
			if grid[i][j] == '.':
				a[i][j] = 1
			else:
				a[i][j] = 0
				down[i][j] = -1
				right[i][j] = -1
	for i in range(0, m):
		for j in range(0, n):
			if (i != 0) & (a[m - i - 1][j] == 1):
				if a[m - i - 1][j] == 1:
					down[m - i - 1][j] = down[m - i][j] + 1
			if (j != 0) & (a[i][n - j - 1] == 1):
				if a[i][n - j - 1] == 1:
					right[i][n - j - 1] = right[i][n - j] + 1
	res = -1
	for i in range(0, m - 1):
		for j in range(0, n - 1):
			if a[i][j] == 1:
				half_perimeter = down[i][j] + right[i][j]
				for s in reversed(range(2, half_perimeter + 1)):
					if res < half_perimeter * 2:
						for d in range(1, min(down[i][j] + 1, s)):
							r = s - d
							if r > right[i][j]:
								continue
							x = i + d
							y = j + r
							if (down[i][y] >= d) & (right[x][j] >= r):
								if d + d + r + r > res:
									res = d + d + r + r
									break
	if res == -1:
		print('impossible')
	else:
		print(res)
mn = input().split()
m = int(mn[0])
n = int(mn[1])
grid = []
for _ in range(m):
	grid_item = input()
	grid.append(grid_item)
kMarsh(grid)


import sys
(m, n) = [int(q_temp) for q_temp in input().strip().split(' ')]
a = list()
for i in range(m):
	l = input().strip()
	a.append(l)
max_perim = 0
for i in range(m):
	if 2 * (m - i - 1) + 2 * (n - 1) < max_perim:
		continue
	for j in range(n):
		i1 = j
		if a[i][j] == 'x' or a[i][min(j + 1, n - 1)] == 'x' or a[i][min(j + 2, n - 1)] == 'x' or (j >= n - 1):
			continue
		if 2 * (m - i - 1) + 2 * (n - j - 1) < max_perim:
			continue
		i2 = n - 1
		str_top = a[i][i1:i2 + 1]
		while i2 > i1:
			str_top = a[i][i1:i2 + 1]
			if str_top.count('x') == 0 and 2 * (i2 - i1) + 2 * (m - i - 1) > max_perim:
				search = True
				depth = 1
				while search and i + depth < m:
					str = a[i + depth][i1:i2 + 1]
					if str.count('x') == 0:
						perim = 2 * (i2 - i1) + 2 * depth
						if perim > max_perim:
							max_perim = perim
					if a[i + depth][i1] == 'x' or a[i + depth][i2] == 'x':
						search = False
					depth += 1
			i2 -= 1
if max_perim > 0:
	print(max_perim)
else:
	print('impossible')


import os
import sys

def kMarsh(grid):
	rows = len(grid)
	columns = len(grid[0])
	found = 0
	for row in range(rows - 1):
		for column in range(columns - 1):
			if grid[row][column] == 'x':
				continue
			if grid[row + 1][column] == 'x' or grid[row][column + 1] == 'x':
				continue
			maximum = (rows - 1 - row) * 2 + (columns - 1 - column) * 2
			if maximum <= found:
				break
			for cr in range(row + 1, rows):
				if grid[cr][column] == 'x':
					break
				if (cr - row) * 2 + (columns - 1 - column) * 2 <= found:
					continue
				cc = columns - 1
				while cc > column:
					if (cr - row) * 2 + (cc - column) * 2 <= found:
						break
					if 'x' in grid[row][column:cc + 1]:
						cc = column + grid[row][column:cc + 1].index('x') - 1
						continue
					elif 'x' in grid[cr][column:cc + 1]:
						cc = column + grid[cr][column:cc + 1].index('x') - 1
						continue
					rect = True
					for trow in range(cr, row - 1, -1):
						if grid[trow][cc] == 'x':
							rect = False
							break
					if rect:
						found = (cr - row) * 2 + (cc - column) * 2
						break
					cc -= 1
	if found == 0:
		print('impossible')
	else:
		print(found)
mn = input().split()
m = int(mn[0])
n = int(mn[1])
grid = []
for _ in range(m):
	grid_item = input()
	grid.append(grid_item)
kMarsh(grid)


import os
import sys

def kMarsh(grid):
	rows = len(grid)
	cols = len(grid[0])
	up = [[0] * cols for _ in range(rows)]
	left = [[0] * cols for _ in range(rows)]
	for i in range(rows):
		for j in range(cols):
			if j > 0:
				left[i][j] = left[i][j - 1] + 1 if grid[i][j - 1] != 'x' else 0
			if i > 0:
				up[i][j] = up[i - 1][j] + 1 if grid[i - 1][j] != 'x' else 0
	max_perimeter = 0
	for i in range(1, rows):
		for j in range(1, cols):
			if grid[i][j] != 'x':
				a = i - up[i][j]
				b = 0
				while a < i and 2 * (i - a) + 2 * (j - b) > max_perimeter:
					b = max(j - left[a][j], j - left[i][j])
					while up[i][b] < i - a and b < j and (2 * (i - a) + 2 * (j - b) > max_perimeter):
						b += 1
					if b < j and left[i][j] >= j - b and (grid[a][b] != 'x'):
						max_perimeter = max(max_perimeter, 2 * (i - a) + 2 * (j - b))
					a += 1
					b = 0
	print(max_perimeter if max_perimeter > 0 else 'impossible')
mn = input().split()
m = int(mn[0])
n = int(mn[1])
grid = []
for _ in range(m):
	grid_item = input()
	grid.append(grid_item)
kMarsh(grid)


def print_2D(arr):
	for subarr in arr:
		print(subarr)
(n_rows, n_cloumns) = map(int, input().split())
world = ['0'] * n_rows
for row in range(n_rows):
	world[row] = input()
possible_down = [[-1 for row in range(n_cloumns)] for column in range(n_rows)]
possible_right = [[-1 for row in range(n_cloumns)] for column in range(n_rows)]
for row in reversed(range(n_rows)):
	for column in reversed(range(n_cloumns)):
		if world[row][column] == 'x':
			possible_down[row][column] = -1
			continue
		if row == n_rows - 1:
			possible_down[row][column] = 0
			continue
		possible_down[row][column] = possible_down[row + 1][column] + 1
for row in reversed(range(n_rows)):
	for column in reversed(range(n_cloumns)):
		if world[row][column] == 'x':
			possible_right[row][column] = -1
			continue
		if column == n_cloumns - 1:
			possible_right[row][column] = 0
			continue
		possible_right[row][column] = possible_right[row][column + 1] + 1
rectange_size = 0
for row in range(n_rows):
	area = 0
	for column in range(n_cloumns):
		if rectange_size >= (n_rows - row - 1) * 2 + (n_cloumns - column - 1) * 2:
			break
		down1 = possible_down[row][column]
		right1 = possible_right[row][column]
		if down1 in [-1, 0] or right1 in [-1, 0]:
			continue
		for right in reversed(range(1, right1 + 1)):
			down2 = possible_down[row][column + right]
			if down2 in [-1, 0]:
				continue
			common_down = min(down1, down2)
			down = 0
			for down in reversed(range(1, common_down + 1)):
				if possible_right[row + down][column] >= right:
					area = right + right + down + down
					if area > rectange_size:
						rectange_size = area
					break
			if down == down1:
				break
			if area == (n_rows - row - 1) * 2 + (n_cloumns - column - 1) * 2:
				break
		if area == (n_rows - row - 1) * 2 + (n_cloumns - column - 1) * 2:
			break
	if area == (n_rows - row - 1) * 2 + (n_cloumns - column - 1) * 2:
		break
if rectange_size != 0:
	print(rectange_size)
else:
	print('impossible')


import os
import sys

def kMarsh(grid):
	(n, m) = (len(grid), len(grid[0]))
	(down_table, right_table) = ([[0 for i in range(m)] for j in range(n)], [[0 for i in range(m)] for j in range(n)])
	cur_max = 0
	for y in range(n - 1, -1, -1):
		for x in range(m - 1, -1, -1):
			if grid[y][x] == '.':
				down_table[y][x] += 1
				right_table[y][x] += 1
				if y != 0 and grid[y - 1][x] == '.':
					down_table[y - 1][x] += down_table[y][x]
				if x != 0 and grid[y][x - 1] == '.':
					right_table[y][x - 1] += right_table[y][x]
	for a in range(n):
		for b in range(m):
			if grid[a][b] == '.':
				(max_hor, max_vert) = (right_table[a][b], down_table[a][b])
				if max_hor <= 1 or max_vert <= 1 or 2 * (max_hor + max_vert) < cur_max:
					continue
				cur_max = test_rect(max_hor, max_vert, (a, b), cur_max, down_table, right_table)
	if cur_max == 0:
		print('impossible')
	else:
		print(cur_max)

def test_rect(max_width, max_height, corner, cur_max, down_table, right_table):
	(y, x) = corner
	new_max = cur_max
	for width in range(1, max_width):
		for height in range(1, max_height):
			perimeter = 2 * (width + height)
			if perimeter < new_max:
				continue
			if right_table[y + height][x] > width and down_table[y][x + width] > height:
				new_max = perimeter
	return new_max
mn = input().split()
m = int(mn[0])
n = int(mn[1])
grid = []
for _ in range(m):
	grid_item = input()
	grid.append(grid_item)
kMarsh(grid)


import math
import os
import random
import re
import sys

def printMatrix(matrix):
	msg = ''
	for row in matrix:
		msg = msg + ' '.join(map(str, row)) + '\n'
	print(msg)

def kMarsh(m, n):
	grid = []
	up_matrix = [[0 for _ in range(n)] for _ in range(m)]
	left_matrix = [[0 for _ in range(n)] for _ in range(m)]
	for i in range(m):
		grid_item = input()
		grid.append(grid_item)
		for j in range(n):
			if grid[i][j] == '.':
				left_matrix[i][j] = 0 if j == 0 else left_matrix[i][j - 1] + 1
				up_matrix[i][j] = 0 if i == 0 else up_matrix[i - 1][j] + 1
			else:
				left_matrix[i][j] = up_matrix[i][j] = -1
	max_perimeter = 0
	for i in range(m - 1, 0, -1):
		for j in range(n - 1, 0, -1):
			if grid[i][j] == 'x':
				continue
			for x in range(i - up_matrix[i][j], i):
				if grid[x][j] == 'x':
					break
				for y in range(j - left_matrix[i][j], j):
					if grid[i][y] == 'x':
						break
					up_side = i - x
					left_side = j - y
					if up_side + left_side <= max_perimeter:
						break
					if grid[x][y] == '.' and up_side <= up_matrix[i][y] and (left_side <= left_matrix[x][j]) and (up_side + left_side > max_perimeter):
						max_perimeter = up_side + left_side
			if i + j <= int(math.floor(max_perimeter / 2)):
				break
		if i + j <= int(math.floor(max_perimeter / 2)):
			break
	return 'impossible' if max_perimeter == 0 else max_perimeter * 2
first_multiple_input = input().rstrip().split()
m = int(first_multiple_input[0])
n = int(first_multiple_input[1])
if 2 <= m <= 500 and 2 <= n <= 500:
	print(kMarsh(m, n))
else:
	print('dimensions m and n should be both between 2 and 500')


import math
import os
import random
import re
import sys

def kMarsh(grid):

	def is_possible(i, j, k, l):
		return grid[k].find('x', l, j + 1) < 0 and grid[i].find('x', l, j + 1) < 0 and (columns[l].find('x', k, i + 1) < 0) and (columns[j].find('x', k, i + 1) < 0)
	m = len(grid)
	n = len(grid[0])
	columns = []
	for i in range(n):
		columns.append(''.join((row[i] for row in grid)))
	perimeter = 0
	for k in range(m - 1):
		if m - k - 1 + n - 1 <= perimeter:
			break
		for l in range(n - 1):
			if grid[k][l] == 'x':
				continue
			row = columns[l].find('x', k + 1)
			col = grid[k].find('x', l + 1)
			if row < 0:
				row = m
			if col < 0:
				col = n
			for i in range(row - 1, k, -1):
				if i - k + n - 1 <= perimeter:
					break
				for j in range(col - 1, l, -1):
					if is_possible(i, j, k, l):
						perimeter = max(perimeter, j - l + i - k)
						break
	if perimeter > 0:
		print(perimeter * 2)
	else:
		print('impossible')
first_multiple_input = input().rstrip().split()
m = int(first_multiple_input[0])
n = int(first_multiple_input[1])
grid = []
for _ in range(m):
	grid_item = input()
	grid.append(grid_item)
kMarsh(grid)


import math
import os
import random
import re
import sys
from collections import deque

def is_rect(rec, tx, ty, bx, by):
	hor_ok = rec[by][tx][0] + tx >= bx
	ver_ok = rec[ty][bx][1] + ty >= by
	return ver_ok and hor_ok

def find_rect_big_to_small(rec, tx, ty, bx, by):
	q = deque()
	q.append((bx, by))
	while q:
		cor = q.popleft()
		if is_rect(rec, tx, ty, cor[0], cor[1]):
			return -tx - ty + cor[0] + cor[1]
		if cor[0] > tx + 1 and (cor[0] - 1, cor[1]) not in q:
			q.append((cor[0] - 1, cor[1]))
		if cor[1] > ty + 1 and (cor[0], cor[1] - 1) not in q:
			q.append((cor[0], cor[1] - 1))
	return 0

def find_largest(rec, tx, ty, lrg):
	if rec[ty][tx][0] == 0 or rec[ty][tx][1] == 0:
		return lrg
	bx = tx + rec[ty][tx][0]
	by = ty + rec[ty][tx][1]
	if bx - tx + by - ty <= lrg:
		return lrg
	tmp = find_rect_big_to_small(rec, tx, ty, bx, by)
	return max(tmp, lrg)

def kMarsh(grid):
	num_r = len(grid)
	num_c = len(grid[0])
	rec = [[(0, 0)] * num_c for _ in range(num_r)]
	col = num_c - 1
	row = num_r - 1
	if grid[row][col] == '.':
		rec[row][col] = (0, 0)
	else:
		rec[row][col] = (-1, -1)
	col = num_c - 2
	while col >= 0:
		if grid[row][col] == '.':
			rec[row][col] = (rec[row][col + 1][0] + 1, 0)
		else:
			rec[row][col] = (-1, -1)
		col -= 1
	row = num_r - 2
	while row >= 0:
		if grid[row][col] == '.':
			rec[row][col] = (0, rec[row + 1][col][1] + 1)
		else:
			rec[row][col] = (-1, -1)
		row -= 1
	row = num_r - 2
	while row >= 0:
		col = num_c - 2
		while col >= 0:
			if grid[row][col] == '.':
				rec[row][col] = (rec[row][col + 1][0] + 1, rec[row + 1][col][1] + 1)
			else:
				rec[row][col] = (-1, -1)
			col -= 1
		row -= 1
	lrg = 0
	for i in range(num_r):
		for j in range(num_c):
			lrg = find_largest(rec, j, i, lrg)
	if lrg == 0:
		print('impossible')
	else:
		print(2 * lrg)
first_multiple_input = input().rstrip().split()
m = int(first_multiple_input[0])
n = int(first_multiple_input[1])
grid = []
for _ in range(m):
	grid_item = input()
	grid.append(grid_item)
kMarsh(grid)


import os
import sys

def kMarsh(grid):
	rows = len(grid)
	cols = len(grid[0])
	up = [[0] * cols for _ in range(rows)]
	left = [[0] * cols for _ in range(rows)]
	for i in range(rows):
		for j in range(cols):
			if j > 0:
				left[i][j] = left[i][j - 1] + 1 if grid[i][j - 1] != 'x' else 0
			if i > 0:
				up[i][j] = up[i - 1][j] + 1 if grid[i - 1][j] != 'x' else 0
	max_perimeter = 0
	for i in range(1, rows):
		for j in range(1, cols):
			if grid[i][j] != 'x':
				a = i - up[i][j]
				b = 0
				while a < i and 2 * (i - a) + 2 * (j - b) > max_perimeter:
					b = max(j - left[a][j], j - left[i][j])
					while up[i][b] < i - a and b < j and (2 * (i - a) + 2 * (j - b) > max_perimeter):
						b += 1
					if b < j and left[i][j] >= j - b and (grid[a][b] != 'x'):
						max_perimeter = max(max_perimeter, 2 * (i - a) + 2 * (j - b))
					a += 1
					b = 0
	print(max_perimeter if max_perimeter > 0 else 'impossible')
mn = input().split()
m = int(mn[0])
n = int(mn[1])
grid = []
for _ in range(m):
	grid_item = input()
	grid.append(grid_item)
kMarsh(grid)


import math
import os
import random
import re
import sys

def kMarsh(grid):
	rows = len(grid)
	cols = len(grid[0])
	up = [[0] * cols for _ in range(rows)]
	left = [[0] * cols for _ in range(rows)]
	for i in range(rows):
		for j in range(cols):
			if j > 0:
				left[i][j] = left[i][j - 1] + 1 if grid[i][j - 1] != 'x' else 0
			if i > 0:
				up[i][j] = up[i - 1][j] + 1 if grid[i - 1][j] != 'x' else 0
	max_preimeter = 0
	for i in range(1, rows):
		for j in range(1, cols):
			if grid[i][j] != 'x':
				a = i - up[i][j]
				b = 0
				while a < i and 2 * (i - a) + 2 * (j - b) > max_preimeter:
					b = max(j - left[a][j], j - left[i][j])
					while up[i][b] < i - a and b < j and (2 * (i - a) + 2 * (j - b) > max_preimeter):
						b += 1
					if b < j and left[i][j] >= j - b and (grid[a][b] != 'x'):
						max_preimeter = max(max_preimeter, 2 * (i - a) + 2 * (j - b))
					a += 1
					b = 0
	print(max_preimeter if max_preimeter > 0 else 'impossible')
first_multiple_input = input().rstrip().split()
m = int(first_multiple_input[0])
n = int(first_multiple_input[1])
grid = []
for _ in range(m):
	grid_item = input()
	grid.append(grid_item)
kMarsh(grid)


import os
import sys

def kMarsh(grid):
	rows = len(grid)
	cols = len(grid[0])
	up = [[0] * cols for _ in range(rows)]
	left = [[0] * cols for _ in range(rows)]
	for i in range(rows):
		for j in range(cols):
			if j > 0:
				left[i][j] = left[i][j - 1] + 1 if grid[i][j - 1] != 'x' else 0
			if i > 0:
				up[i][j] = up[i - 1][j] + 1 if grid[i - 1][j] != 'x' else 0
	max_perimeter = 0
	for i in range(1, rows):
		for j in range(1, cols):
			if grid[i][j] != 'x':
				a = i - up[i][j]
				b = 0
				while a < i and 2 * (i - a) + 2 * (j - b) > max_perimeter:
					b = max(j - left[a][j], j - left[i][j])
					while up[i][b] < i - a and b < j and (2 * (i - a) + 2 * (j - b) > max_perimeter):
						b += 1
					if b < j and left[i][j] >= j - b and (grid[a][b] != 'x'):
						max_perimeter = max(max_perimeter, 2 * (i - a) + 2 * (j - b))
					a += 1
					b = 0
	print(max_perimeter if max_perimeter > 0 else 'impossible')
mn = input().split()
m = int(mn[0])
n = int(mn[1])
grid = []
for _ in range(m):
	grid_item = input()
	grid.append(grid_item)
kMarsh(grid)


import os
import sys

def kMarsh(grid):
	rows = len(grid)
	cols = len(grid[0])
	up = [[0] * cols for _ in range(rows)]
	left = [[0] * cols for _ in range(rows)]
	for i in range(rows):
		for j in range(cols):
			if j > 0:
				left[i][j] = left[i][j - 1] + 1 if grid[i][j - 1] != 'x' else 0
			if i > 0:
				up[i][j] = up[i - 1][j] + 1 if grid[i - 1][j] != 'x' else 0
	max_perimeter = 0
	for i in range(1, rows):
		for j in range(1, cols):
			if grid[i][j] != 'x':
				a = i - up[i][j]
				b = 0
				while a < i and 2 * (i - a) + 2 * (j - b) > max_perimeter:
					b = max(j - left[a][j], j - left[i][j])
					while up[i][b] < i - a and b < j and (2 * (i - a) + 2 * (j - b) > max_perimeter):
						b += 1
					if b < j and left[i][j] >= j - b and (grid[a][b] != 'x'):
						max_perimeter = max(max_perimeter, 2 * (i - a) + 2 * (j - b))
					a += 1
					b = 0
	print(max_perimeter if max_perimeter > 0 else 'impossible')
mn = input().split()
m = int(mn[0])
n = int(mn[1])
grid = []
for _ in range(m):
	grid_item = input()
	grid.append(grid_item)
kMarsh(grid)


import math
import os
import random
import re
import sys

def kMarsh(grid):
	rows = len(grid)
	cols = len(grid[0])
	up = [[0] * cols for _ in range(rows)]
	left = [[0] * cols for _ in range(rows)]
	for i in range(rows):
		for j in range(cols):
			if j > 0:
				left[i][j] = left[i][j - 1] + 1 if grid[i][j - 1] != 'x' else 0
			if i > 0:
				up[i][j] = up[i - 1][j] + 1 if grid[i - 1][j] != 'x' else 0
	max_perimeter = 0
	for i in range(1, rows):
		for j in range(1, cols):
			if grid[i][j] != 'x':
				a = i - up[i][j]
				b = 0
				while a < i and 2 * (i - a) + 2 * (j - b) > max_perimeter:
					b = max(j - left[a][j], j - left[i][j])
					while up[i][b] < i - a and b < j and (2 * (i - a) + 2 * (j - b) > max_perimeter):
						b += 1
					if b < j and left[i][j] >= j - b and (grid[a][b] != 'x'):
						max_perimeter = max(max_perimeter, 2 * (i - a) + 2 * (j - b))
					a += 1
					b = 0
	print(max_perimeter if max_perimeter > 0 else 'impossible')
first_multiple_input = input().rstrip().split()
m = int(first_multiple_input[0])
n = int(first_multiple_input[1])
grid = []
for _ in range(m):
	grid_item = input()
	grid.append(grid_item)
kMarsh(grid)


import os
import sys

def kMarsh(grid):
	rows = len(grid)
	cols = len(grid[0])
	up = [[0] * cols for _ in range(rows)]
	left = [[0] * cols for _ in range(rows)]
	for i in range(rows):
		for j in range(cols):
			if j > 0:
				left[i][j] = left[i][j - 1] + 1 if grid[i][j - 1] != 'x' else 0
			if i > 0:
				up[i][j] = up[i - 1][j] + 1 if grid[i - 1][j] != 'x' else 0
	max_perimeter = 0
	for i in range(1, rows):
		for j in range(1, cols):
			if grid[i][j] != 'x':
				a = i - up[i][j]
				b = 0
				while a < i and 2 * (i - a) + 2 * (j - b) > max_perimeter:
					b = max(j - left[a][j], j - left[i][j])
					while up[i][b] < i - a and b < j and (2 * (i - a) + 2 * (j - b) > max_perimeter):
						b += 1
					if b < j and left[i][j] >= j - b and (grid[a][b] != 'x'):
						max_perimeter = max(max_perimeter, 2 * (i - a) + 2 * (j - b))
					a += 1
					b = 0
	print(max_perimeter if max_perimeter > 0 else 'impossible')
mn = input().split()
m = int(mn[0])
n = int(mn[1])
grid = []
for _ in range(m):
	grid_item = input()
	grid.append(grid_item)
kMarsh(grid)


import os
import sys

def kMarsh(grid):
	rows = len(grid)
	cols = len(grid[0])
	up = [[0] * cols for _ in range(rows)]
	left = [[0] * cols for _ in range(rows)]
	for i in range(rows):
		for j in range(cols):
			if j > 0:
				left[i][j] = left[i][j - 1] + 1 if grid[i][j - 1] != 'x' else 0
			if i > 0:
				up[i][j] = up[i - 1][j] + 1 if grid[i - 1][j] != 'x' else 0
	max_perimeter = 0
	for i in range(1, rows):
		for j in range(1, cols):
			if grid[i][j] != 'x':
				a = i - up[i][j]
				b = 0
				while a < i and 2 * (i - a) + 2 * (j - b) > max_perimeter:
					b = max(j - left[a][j], j - left[i][j])
					while up[i][b] < i - a and b < j and (2 * (i - a) + 2 * (j - b) > max_perimeter):
						b += 1
					if b < j and left[i][j] >= j - b and (grid[a][b] != 'x'):
						max_perimeter = max(max_perimeter, 2 * (i - a) + 2 * (j - b))
					a += 1
					b = 0
	print(max_perimeter if max_perimeter > 0 else 'impossible')
mn = input().split()
m = int(mn[0])
n = int(mn[1])
grid = []
for _ in range(m):
	grid_item = input()
	grid.append(grid_item)
kMarsh(grid)


import os
import sys

def kMarsh(grid):
	rows = len(grid)
	cols = len(grid[0])
	up = [[0] * cols for _ in range(rows)]
	left = [[0] * cols for _ in range(rows)]
	for i in range(rows):
		for j in range(cols):
			if j > 0:
				left[i][j] = left[i][j - 1] + 1 if grid[i][j - 1] != 'x' else 0
			if i > 0:
				up[i][j] = up[i - 1][j] + 1 if grid[i - 1][j] != 'x' else 0
	max_perimeter = 0
	for i in range(1, rows):
		for j in range(1, cols):
			if grid[i][j] != 'x':
				a = i - up[i][j]
				b = 0
				while a < i and 2 * (i - a) + 2 * (j - b) > max_perimeter:
					b = max(j - left[a][j], j - left[i][j])
					while up[i][b] < i - a and b < j and (2 * (i - a) + 2 * (j - b) > max_perimeter):
						b += 1
					if b < j and left[i][j] >= j - b and (grid[a][b] != 'x'):
						max_perimeter = max(max_perimeter, 2 * (i - a) + 2 * (j - b))
					a += 1
					b = 0
	print(max_perimeter if max_perimeter > 0 else 'impossible')
mn = input().split()
m = int(mn[0])
n = int(mn[1])
grid = []
for _ in range(m):
	grid_item = input()
	grid.append(grid_item)
kMarsh(grid)


import math
import os
import random
import re
import sys

def kMarsh(grid):
	rows = len(grid)
	cols = len(grid[0])
	up = [[0] * cols for _ in range(rows)]
	left = [[0] * cols for _ in range(rows)]
	for i in range(rows):
		for j in range(cols):
			if j > 0:
				left[i][j] = left[i][j - 1] + 1 if grid[i][j - 1] != 'x' else 0
			if i > 0:
				up[i][j] = up[i - 1][j] + 1 if grid[i - 1][j] != 'x' else 0
	max_perimeter = 0
	for i in range(1, rows):
		for j in range(1, cols):
			if grid[i][j] != 'x':
				a = i - up[i][j]
				b = 0
				while a < i and 2 * (i - a) + 2 * (j - b) > max_perimeter:
					b = max(j - left[a][j], j - left[i][j])
					while up[i][b] < i - a and b < j and (2 * (i - a) + 2 * (j - b) > max_perimeter):
						b += 1
					if b < j and left[i][j] >= j - b and (grid[a][b] != 'x'):
						max_perimeter = max(max_perimeter, 2 * (i - a) + 2 * (j - b))
					a += 1
					b = 0
	print(max_perimeter if max_perimeter > 0 else 'impossible')
first_multiple_input = input().rstrip().split()
m = int(first_multiple_input[0])
n = int(first_multiple_input[1])
grid = []
for _ in range(m):
	grid_item = input()
	grid.append(grid_item)
kMarsh(grid)


import os
import sys

def kMarsh(grid):
	rows = len(grid)
	cols = len(grid[0])
	up = [[0] * cols for _ in range(rows)]
	left = [[0] * cols for _ in range(rows)]
	for i in range(rows):
		for j in range(cols):
			if j > 0:
				left[i][j] = left[i][j - 1] + 1 if grid[i][j - 1] != 'x' else 0
			if i > 0:
				up[i][j] = up[i - 1][j] + 1 if grid[i - 1][j] != 'x' else 0
	max_perimeter = 0
	for i in range(1, rows):
		for j in range(1, cols):
			if grid[i][j] != 'x':
				a = i - up[i][j]
				b = 0
				while a < i and 2 * (i - a) + 2 * (j - b) > max_perimeter:
					b = max(j - left[a][j], j - left[i][j])
					while up[i][b] < i - a and b < j and (2 * (i - a) + 2 * (j - b) > max_perimeter):
						b += 1
					if b < j and left[i][j] >= j - b and (grid[a][b] != 'x'):
						max_perimeter = max(max_perimeter, 2 * (i - a) + 2 * (j - b))
					a += 1
					b = 0
	print(max_perimeter if max_perimeter > 0 else 'impossible')
mn = input().split()
m = int(mn[0])
n = int(mn[1])
grid = []
for _ in range(m):
	grid_item = input()
	grid.append(grid_item)
kMarsh(grid)


import os
import sys

def kMarsh(grid):
	rows = len(grid)
	cols = len(grid[0])
	up = [[0] * cols for _ in range(rows)]
	left = [[0] * cols for _ in range(rows)]
	for i in range(rows):
		for j in range(cols):
			if j > 0:
				left[i][j] = left[i][j - 1] + 1 if grid[i][j - 1] != 'x' else 0
			if i > 0:
				up[i][j] = up[i - 1][j] + 1 if grid[i - 1][j] != 'x' else 0
	max_perimeter = 0
	for i in range(1, rows):
		for j in range(1, cols):
			if grid[i][j] != 'x':
				a = i - up[i][j]
				b = 0
				while a < i and 2 * (i - a) + 2 * (j - b) > max_perimeter:
					b = max(j - left[a][j], j - left[i][j])
					while up[i][b] < i - a and b < j and (2 * (i - a) + 2 * (j - b) > max_perimeter):
						b += 1
					if b < j and left[i][j] >= j - b and (grid[a][b] != 'x'):
						max_perimeter = max(max_perimeter, 2 * (i - a) + 2 * (j - b))
					a += 1
					b = 0
	print(max_perimeter if max_perimeter > 0 else 'impossible')
mn = input().split()
m = int(mn[0])
n = int(mn[1])
grid = []
for _ in range(m):
	grid_item = input()
	grid.append(grid_item)
kMarsh(grid)


import os
import sys

def kMarsh(grid):
	rows = len(grid)
	cols = len(grid[0])
	up = [[0] * cols for _ in range(rows)]
	left = [[0] * cols for _ in range(rows)]
	for i in range(rows):
		for j in range(cols):
			if j > 0:
				left[i][j] = left[i][j - 1] + 1 if grid[i][j - 1] != 'x' else 0
			if i > 0:
				up[i][j] = up[i - 1][j] + 1 if grid[i - 1][j] != 'x' else 0
	max_perimeter = 0
	for i in range(1, rows):
		for j in range(1, cols):
			if grid[i][j] != 'x':
				a = i - up[i][j]
				b = 0
				while a < i and 2 * (i - a) + 2 * (j - b) > max_perimeter:
					b = max(j - left[a][j], j - left[i][j])
					while up[i][b] < i - a and b < j and (2 * (i - a) + 2 * (j - b) > max_perimeter):
						b += 1
					if b < j and left[i][j] >= j - b and (grid[a][b] != 'x'):
						max_perimeter = max(max_perimeter, 2 * (i - a) + 2 * (j - b))
					a += 1
					b = 0
	print(max_perimeter if max_perimeter > 0 else 'impossible')
mn = input().split()
m = int(mn[0])
n = int(mn[1])
grid = []
for _ in range(m):
	grid_item = input()
	grid.append(grid_item)
kMarsh(grid)


import os
import sys

def kMarsh(grid):
	rows = len(grid)
	cols = len(grid[0])
	up = [[0] * cols for _ in range(rows)]
	left = [[0] * cols for _ in range(rows)]
	for i in range(rows):
		for j in range(cols):
			if j > 0:
				left[i][j] = left[i][j - 1] + 1 if grid[i][j - 1] != 'x' else 0
			if i > 0:
				up[i][j] = up[i - 1][j] + 1 if grid[i - 1][j] != 'x' else 0
	max_perimeter = 0
	for i in range(1, rows):
		for j in range(1, cols):
			if grid[i][j] != 'x':
				a = i - up[i][j]
				b = 0
				while a < i and 2 * (i - a) + 2 * (j - b) > max_perimeter:
					b = max(j - left[a][j], j - left[i][j])
					while up[i][b] < i - a and b < j and (2 * (i - a) + 2 * (j - b) > max_perimeter):
						b += 1
					if b < j and left[i][j] >= j - b and (grid[a][b] != 'x'):
						max_perimeter = max(max_perimeter, 2 * (i - a) + 2 * (j - b))
					a += 1
					b = 0
	print(max_perimeter if max_perimeter > 0 else 'impossible')
mn = input().split()
m = int(mn[0])
n = int(mn[1])
grid = []
for _ in range(m):
	grid_item = input()
	grid.append(grid_item)
kMarsh(grid)


import math
import os
import random
import re
import sys

def kMarsh(grid):
	rows = len(grid)
	cols = len(grid[0])
	up = [[0] * cols for _ in range(rows)]
	left = [[0] * cols for _ in range(rows)]
	for i in range(rows):
		for j in range(cols):
			if j > 0:
				left[i][j] = left[i][j - 1] + 1 if grid[i][j - 1] != 'x' else 0
			if i > 0:
				up[i][j] = up[i - 1][j] + 1 if grid[i - 1][j] != 'x' else 0
	max_perimeter = 0
	for i in range(1, rows):
		for j in range(1, cols):
			if grid[i][j] != 'x':
				a = i - up[i][j]
				b = 0
				while a < i and 2 * (i - a) + 2 * (j - b) > max_perimeter:
					b = max(j - left[a][j], j - left[i][j])
					while up[i][b] < i - a and b < j and (2 * (i - a) + 2 * (j - b) > max_perimeter):
						b += 1
					if b < j and left[i][j] >= j - b and (grid[a][b] != 'x'):
						max_perimeter = max(max_perimeter, 2 * (i - a) + 2 * (j - b))
					a += 1
					b = 0
	print(max_perimeter if max_perimeter > 0 else 'impossible')
mn = input().split()
m = int(mn[0])
n = int(mn[1])
grid = []
for _ in range(m):
	grid_item = input()
	grid.append(grid_item)
kMarsh(grid)


import os
import sys

def kMarsh(grid):
	rows = len(grid)
	cols = len(grid[0])
	up = [[0] * cols for _ in range(rows)]
	left = [[0] * cols for _ in range(rows)]
	for i in range(rows):
		for j in range(cols):
			if j > 0:
				left[i][j] = left[i][j - 1] + 1 if grid[i][j - 1] != 'x' else 0
			if i > 0:
				up[i][j] = up[i - 1][j] + 1 if grid[i - 1][j] != 'x' else 0
	max_perimeter = 0
	for i in range(1, rows):
		for j in range(1, cols):
			if grid[i][j] != 'x':
				a = i - up[i][j]
				b = 0
				while a < i and 2 * (i - a) + 2 * (j - b) > max_perimeter:
					b = max(j - left[a][j], j - left[i][j])
					while up[i][b] < i - a and b < j and (2 * (i - a) + 2 * (j - b) > max_perimeter):
						b += 1
					if b < j and left[i][j] >= j - b and (grid[a][b] != 'x'):
						max_perimeter = max(max_perimeter, 2 * (i - a) + 2 * (j - b))
					a += 1
					b = 0
	print(max_perimeter if max_perimeter > 0 else 'impossible')
mn = input().split()
m = int(mn[0])
n = int(mn[1])
grid = []
for _ in range(m):
	grid_item = input()
	grid.append(grid_item)
kMarsh(grid)


import math
import os
import random
import re
import sys

def kMarsh(grid):
	rows = len(grid)
	cols = len(grid[0])
	up = [[0] * cols for _ in range(rows)]
	left = [[0] * cols for _ in range(rows)]
	for i in range(rows):
		for j in range(cols):
			if j > 0:
				left[i][j] = left[i][j - 1] + 1 if grid[i][j - 1] != 'x' else 0
			if i > 0:
				up[i][j] = up[i - 1][j] + 1 if grid[i - 1][j] != 'x' else 0
	max_perimeter = 0
	for i in range(1, rows):
		for j in range(1, cols):
			if grid[i][j] != 'x':
				a = i - up[i][j]
				b = 0
				while a < i and 2 * (i - a) + 2 * (j - b) > max_perimeter:
					b = max(j - left[a][j], j - left[i][j])
					while up[i][b] < i - a and b < j and (2 * (i - a) + 2 * (j - b) > max_perimeter):
						b += 1
					if b < j and left[i][j] >= j - b and (grid[a][b] != 'x'):
						max_perimeter = max(max_perimeter, 2 * (i - a) + 2 * (j - b))
					a += 1
					b = 0
	print(max_perimeter if max_perimeter > 0 else 'impossible')
first_multiple_input = input().rstrip().split()
m = int(first_multiple_input[0])
n = int(first_multiple_input[1])
grid = []
for _ in range(m):
	grid_item = input()
	grid.append(grid_item)
kMarsh(grid)


import os
import sys

def kMarsh(grid):
	rows = len(grid)
	cols = len(grid[0])
	up = [[0] * cols for _ in range(rows)]
	left = [[0] * cols for _ in range(rows)]
	for i in range(rows):
		for j in range(cols):
			if j > 0:
				left[i][j] = left[i][j - 1] + 1 if grid[i][j - 1] != 'x' else 0
			if i > 0:
				up[i][j] = up[i - 1][j] + 1 if grid[i - 1][j] != 'x' else 0
	max_perimeter = 0
	for i in range(1, rows):
		for j in range(1, cols):
			if grid[i][j] != 'x':
				a = i - up[i][j]
				b = 0
				while a < i and 2 * (i - a) + 2 * (j - b) > max_perimeter:
					b = max(j - left[a][j], j - left[i][j])
					while up[i][b] < i - a and b < j and (2 * (i - a) + 2 * (j - b) > max_perimeter):
						b += 1
					if b < j and left[i][j] >= j - b and (grid[a][b] != 'x'):
						max_perimeter = max(max_perimeter, 2 * (i - a) + 2 * (j - b))
					a += 1
					b = 0
	print(max_perimeter if max_perimeter > 0 else 'impossible')
mn = input().split()
m = int(mn[0])
n = int(mn[1])
grid = []
for _ in range(m):
	grid_item = input()
	grid.append(grid_item)
kMarsh(grid)


import os
import sys

def kMarsh(grid):
	rows = len(grid)
	cols = len(grid[0])
	up = [[0] * cols for _ in range(rows)]
	left = [[0] * cols for _ in range(rows)]
	for i in range(rows):
		for j in range(cols):
			if j > 0:
				left[i][j] = left[i][j - 1] + 1 if grid[i][j - 1] != 'x' else 0
			if i > 0:
				up[i][j] = up[i - 1][j] + 1 if grid[i - 1][j] != 'x' else 0
	max_perimeter = 0
	for i in range(1, rows):
		for j in range(1, cols):
			if grid[i][j] != 'x':
				a = i - up[i][j]
				b = 0
				while a < i and 2 * (i - a) + 2 * (j - b) > max_perimeter:
					b = max(j - left[a][j], j - left[i][j])
					while up[i][b] < i - a and b < j and (2 * (i - a) + 2 * (j - b) > max_perimeter):
						b += 1
					if b < j and left[i][j] >= j - b and (grid[a][b] != 'x'):
						max_perimeter = max(max_perimeter, 2 * (i - a) + 2 * (j - b))
					a += 1
					b = 0
	print(max_perimeter if max_perimeter > 0 else 'impossible')
mn = input().split()
m = int(mn[0])
n = int(mn[1])
grid = []
for _ in range(m):
	grid_item = input()
	grid.append(grid_item)
kMarsh(grid)


import math
import os
import random
import re
import sys

def kMarsh(grid):
	rows = len(grid)
	cols = len(grid[0])
	up = [[0] * cols for _ in range(rows)]
	left = [[0] * cols for _ in range(rows)]
	for i in range(rows):
		for j in range(cols):
			if j > 0:
				left[i][j] = left[i][j - 1] + 1 if grid[i][j - 1] != 'x' else 0
			if i > 0:
				up[i][j] = up[i - 1][j] + 1 if grid[i - 1][j] != 'x' else 0
	max_perimeter = 0
	for i in range(1, rows):
		for j in range(1, cols):
			if grid[i][j] != 'x':
				a = i - up[i][j]
				b = 0
				while a < i and 2 * (i - a) + 2 * (j - b) > max_perimeter:
					b = max(j - left[a][j], j - left[i][j])
					while up[i][b] < i - a and b < j and (2 * (i - a) + 2 * (j - b) > max_perimeter):
						b += 1
					if b < j and left[i][j] >= j - b and (grid[a][b] != 'x'):
						max_perimeter = max(max_perimeter, 2 * (i - a) + 2 * (j - b))
					a += 1
					b = 0
	print(max_perimeter if max_perimeter > 0 else 'impossible')
first_multiple_input = input().rstrip().split()
m = int(first_multiple_input[0])
n = int(first_multiple_input[1])
grid = []
for _ in range(m):
	grid_item = input()
	grid.append(grid_item)
kMarsh(grid)


import os
import sys

def kMarsh(grid):
	rows = len(grid)
	cols = len(grid[0])
	up = [[0] * cols for _ in range(rows)]
	left = [[0] * cols for _ in range(rows)]
	for i in range(rows):
		for j in range(cols):
			if j > 0:
				left[i][j] = left[i][j - 1] + 1 if grid[i][j - 1] != 'x' else 0
			if i > 0:
				up[i][j] = up[i - 1][j] + 1 if grid[i - 1][j] != 'x' else 0
	max_perimeter = 0
	for i in range(1, rows):
		for j in range(1, cols):
			if grid[i][j] != 'x':
				a = i - up[i][j]
				b = 0
				while a < i and 2 * (i - a) + 2 * (j - b) > max_perimeter:
					b = max(j - left[a][j], j - left[i][j])
					while up[i][b] < i - a and b < j and (2 * (i - a) + 2 * (j - b) > max_perimeter):
						b += 1
					if b < j and left[i][j] >= j - b and (grid[a][b] != 'x'):
						max_perimeter = max(max_perimeter, 2 * (i - a) + 2 * (j - b))
					a += 1
					b = 0
	print(max_perimeter if max_perimeter > 0 else 'impossible')
mn = input().split()
m = int(mn[0])
n = int(mn[1])
grid = []
for _ in range(m):
	grid_item = input()
	grid.append(grid_item)
kMarsh(grid)


import os
import sys

def kMarsh(grid):
	rows = len(grid)
	cols = len(grid[0])
	up = [[0] * cols for _ in range(rows)]
	left = [[0] * cols for _ in range(rows)]
	for i in range(rows):
		for j in range(cols):
			if j > 0:
				left[i][j] = left[i][j - 1] + 1 if grid[i][j - 1] != 'x' else 0
			if i > 0:
				up[i][j] = up[i - 1][j] + 1 if grid[i - 1][j] != 'x' else 0
	max_perimeter = 0
	for i in range(1, rows):
		for j in range(1, cols):
			if grid[i][j] != 'x':
				a = i - up[i][j]
				b = 0
				while a < i and 2 * (i - a) + 2 * (j - b) > max_perimeter:
					b = max(j - left[a][j], j - left[i][j])
					while up[i][b] < i - a and b < j and (2 * (i - a) + 2 * (j - b) > max_perimeter):
						b += 1
					if b < j and left[i][j] >= j - b and (grid[a][b] != 'x'):
						max_perimeter = max(max_perimeter, 2 * (i - a) + 2 * (j - b))
					a += 1
					b = 0
	print(max_perimeter if max_perimeter > 0 else 'impossible')
mn = input().split()
m = int(mn[0])
n = int(mn[1])
grid = []
for _ in range(m):
	grid_item = input()
	grid.append(grid_item)
kMarsh(grid)


import os
import sys

def kMarsh(grid):
	rows = len(grid)
	cols = len(grid[0])
	up = [[0] * cols for _ in range(rows)]
	left = [[0] * cols for _ in range(rows)]
	for i in range(rows):
		for j in range(cols):
			if j > 0:
				left[i][j] = left[i][j - 1] + 1 if grid[i][j - 1] != 'x' else 0
			if i > 0:
				up[i][j] = up[i - 1][j] + 1 if grid[i - 1][j] != 'x' else 0
	max_perimeter = 0
	for i in range(1, rows):
		for j in range(1, cols):
			if grid[i][j] != 'x':
				a = i - up[i][j]
				b = 0
				while a < i and 2 * (i - a) + 2 * (j - b) > max_perimeter:
					b = max(j - left[a][j], j - left[i][j])
					while up[i][b] < i - a and b < j and (2 * (i - a) + 2 * (j - b) > max_perimeter):
						b += 1
					if b < j and left[i][j] >= j - b and (grid[a][b] != 'x'):
						max_perimeter = max(max_perimeter, 2 * (i - a) + 2 * (j - b))
					a += 1
					b = 0
	print(max_perimeter if max_perimeter > 0 else 'impossible')
mn = input().split()
m = int(mn[0])
n = int(mn[1])
grid = []
for _ in range(m):
	grid_item = input()
	grid.append(grid_item)
kMarsh(grid)


import os
import sys

def kMarsh(grid):
	rows = len(grid)
	cols = len(grid[0])
	up = [[0] * cols for _ in range(rows)]
	left = [[0] * cols for _ in range(rows)]
	for i in range(rows):
		for j in range(cols):
			if j > 0:
				left[i][j] = left[i][j - 1] + 1 if grid[i][j - 1] != 'x' else 0
			if i > 0:
				up[i][j] = up[i - 1][j] + 1 if grid[i - 1][j] != 'x' else 0
	max_perimeter = 0
	for i in range(1, rows):
		for j in range(1, cols):
			if grid[i][j] != 'x':
				a = i - up[i][j]
				b = 0
				while a < i and 2 * (i - a) + 2 * (j - b) > max_perimeter:
					b = max(j - left[a][j], j - left[i][j])
					while up[i][b] < i - a and b < j and (2 * (i - a) + 2 * (j - b) > max_perimeter):
						b += 1
					if b < j and left[i][j] >= j - b and (grid[a][b] != 'x'):
						max_perimeter = max(max_perimeter, 2 * (i - a) + 2 * (j - b))
					a += 1
					b = 0
	print(max_perimeter if max_perimeter > 0 else 'impossible')
mn = input().split()
m = int(mn[0])
n = int(mn[1])
grid = []
for _ in range(m):
	grid_item = input()
	grid.append(grid_item)
kMarsh(grid)


import os
import sys

def kMarsh(grid):
	rows = len(grid)
	cols = len(grid[0])
	up = [[0] * cols for _ in range(rows)]
	left = [[0] * cols for _ in range(rows)]
	for i in range(rows):
		for j in range(cols):
			if j > 0:
				left[i][j] = left[i][j - 1] + 1 if grid[i][j - 1] != 'x' else 0
			if i > 0:
				up[i][j] = up[i - 1][j] + 1 if grid[i - 1][j] != 'x' else 0
	max_perimeter = 0
	for i in range(1, rows):
		for j in range(1, cols):
			if grid[i][j] != 'x':
				a = i - up[i][j]
				b = 0
				while a < i and 2 * (i - a) + 2 * (j - b) > max_perimeter:
					b = max(j - left[a][j], j - left[i][j])
					while up[i][b] < i - a and b < j and (2 * (i - a) + 2 * (j - b) > max_perimeter):
						b += 1
					if b < j and left[i][j] >= j - b and (grid[a][b] != 'x'):
						max_perimeter = max(max_perimeter, 2 * (i - a) + 2 * (j - b))
					a += 1
					b = 0
	print(max_perimeter if max_perimeter > 0 else 'impossible')
mn = input().split()
m = int(mn[0])
n = int(mn[1])
grid = []
for _ in range(m):
	grid_item = input()
	grid.append(grid_item)
kMarsh(grid)


import os
import sys

def kMarsh(grid):
	rows = len(grid)
	cols = len(grid[0])
	up = [[0] * cols for _ in range(rows)]
	left = [[0] * cols for _ in range(rows)]
	for i in range(rows):
		for j in range(cols):
			if j > 0:
				left[i][j] = left[i][j - 1] + 1 if grid[i][j - 1] != 'x' else 0
			if i > 0:
				up[i][j] = up[i - 1][j] + 1 if grid[i - 1][j] != 'x' else 0
	max_perimeter = 0
	for i in range(1, rows):
		for j in range(1, cols):
			if grid[i][j] != 'x':
				a = i - up[i][j]
				b = 0
				while a < i and 2 * (i - a) + 2 * (j - b) > max_perimeter:
					b = max(j - left[a][j], j - left[i][j])
					while up[i][b] < i - a and b < j and (2 * (i - a) + 2 * (j - b) > max_perimeter):
						b += 1
					if b < j and left[i][j] >= j - b and (grid[a][b] != 'x'):
						max_perimeter = max(max_perimeter, 2 * (i - a) + 2 * (j - b))
					a += 1
					b = 0
	print(max_perimeter if max_perimeter > 0 else 'impossible')
mn = input().split()
m = int(mn[0])
n = int(mn[1])
grid = []
for _ in range(m):
	grid_item = input()
	grid.append(grid_item)
kMarsh(grid)


import os
import sys

def kMarsh(grid):
	rows = len(grid)
	cols = len(grid[0])
	up = [[0] * cols for _ in range(rows)]
	left = [[0] * cols for _ in range(rows)]
	for i in range(rows):
		for j in range(cols):
			if j > 0:
				left[i][j] = left[i][j - 1] + 1 if grid[i][j - 1] != 'x' else 0
			if i > 0:
				up[i][j] = up[i - 1][j] + 1 if grid[i - 1][j] != 'x' else 0
	max_perimeter = 0
	for i in range(1, rows):
		for j in range(1, cols):
			if grid[i][j] != 'x':
				a = i - up[i][j]
				b = 0
				while a < i and 2 * (i - a) + 2 * (j - b) > max_perimeter:
					b = max(j - left[a][j], j - left[i][j])
					while up[i][b] < i - a and b < j and (2 * (i - a) + 2 * (j - b) > max_perimeter):
						b += 1
					if b < j and left[i][j] >= j - b and (grid[a][b] != 'x'):
						max_perimeter = max(max_perimeter, 2 * (i - a) + 2 * (j - b))
					a += 1
					b = 0
	print(max_perimeter if max_perimeter > 0 else 'impossible')
mn = input().split()
m = int(mn[0])
n = int(mn[1])
grid = []
for _ in range(m):
	grid_item = input()
	grid.append(grid_item)
kMarsh(grid)


import os
import sys

def kMarsh(grid):
	rows = len(grid)
	cols = len(grid[0])
	up = [[0] * cols for _ in range(rows)]
	left = [[0] * cols for _ in range(rows)]
	for i in range(rows):
		for j in range(cols):
			if j > 0:
				left[i][j] = left[i][j - 1] + 1 if grid[i][j - 1] != 'x' else 0
			if i > 0:
				up[i][j] = up[i - 1][j] + 1 if grid[i - 1][j] != 'x' else 0
	max_perimeter = 0
	for i in range(1, rows):
		for j in range(1, cols):
			if grid[i][j] != 'x':
				a = i - up[i][j]
				b = 0
				while a < i and 2 * (i - a) + 2 * (j - b) > max_perimeter:
					b = max(j - left[a][j], j - left[i][j])
					while up[i][b] < i - a and b < j and (2 * (i - a) + 2 * (j - b) > max_perimeter):
						b += 1
					if b < j and left[i][j] >= j - b and (grid[a][b] != 'x'):
						max_perimeter = max(max_perimeter, 2 * (i - a) + 2 * (j - b))
					a += 1
					b = 0
	print(max_perimeter if max_perimeter > 0 else 'impossible')
mn = input().split()
m = int(mn[0])
n = int(mn[1])
grid = []
for _ in range(m):
	grid_item = input()
	grid.append(grid_item)
kMarsh(grid)


import os
import sys

def kMarsh(grid):
	rows = len(grid)
	cols = len(grid[0])
	up = [[0] * cols for _ in range(rows)]
	left = [[0] * cols for _ in range(rows)]
	for i in range(rows):
		for j in range(cols):
			if j > 0:
				left[i][j] = left[i][j - 1] + 1 if grid[i][j - 1] != 'x' else 0
			if i > 0:
				up[i][j] = up[i - 1][j] + 1 if grid[i - 1][j] != 'x' else 0
	max_perimeter = 0
	for i in range(1, rows):
		for j in range(1, cols):
			if grid[i][j] != 'x':
				a = i - up[i][j]
				b = 0
				while a < i and 2 * (i - a) + 2 * (j - b) > max_perimeter:
					b = max(j - left[a][j], j - left[i][j])
					while up[i][b] < i - a and b < j and (2 * (i - a) + 2 * (j - b) > max_perimeter):
						b += 1
					if b < j and left[i][j] >= j - b and (grid[a][b] != 'x'):
						max_perimeter = max(max_perimeter, 2 * (i - a) + 2 * (j - b))
					a += 1
					b = 0
	print(max_perimeter if max_perimeter > 0 else 'impossible')
mn = input().split()
m = int(mn[0])
n = int(mn[1])
grid = []
for _ in range(m):
	grid_item = input()
	grid.append(grid_item)
kMarsh(grid)


import os
import sys

def kMarsh(grid):
	rows = len(grid)
	cols = len(grid[0])
	up = [[0] * cols for _ in range(rows)]
	left = [[0] * cols for _ in range(rows)]
	for i in range(rows):
		for j in range(cols):
			if j > 0:
				left[i][j] = left[i][j - 1] + 1 if grid[i][j - 1] != 'x' else 0
			if i > 0:
				up[i][j] = up[i - 1][j] + 1 if grid[i - 1][j] != 'x' else 0
	max_perimeter = 0
	for i in range(1, rows):
		for j in range(1, cols):
			if grid[i][j] != 'x':
				a = i - up[i][j]
				b = 0
				while a < i and 2 * (i - a) + 2 * (j - b) > max_perimeter:
					b = max(j - left[a][j], j - left[i][j])
					while up[i][b] < i - a and b < j and (2 * (i - a) + 2 * (j - b) > max_perimeter):
						b += 1
					if b < j and left[i][j] >= j - b and (grid[a][b] != 'x'):
						max_perimeter = max(max_perimeter, 2 * (i - a) + 2 * (j - b))
					a += 1
					b = 0
	print(max_perimeter if max_perimeter > 0 else 'impossible')
mn = input().split()
m = int(mn[0])
n = int(mn[1])
grid = []
for _ in range(m):
	grid_item = input()
	grid.append(grid_item)
kMarsh(grid)


import os
import sys

def kMarsh(grid):
	rows = len(grid)
	cols = len(grid[0])
	up = [[0] * cols for _ in range(rows)]
	left = [[0] * cols for _ in range(rows)]
	for i in range(rows):
		for j in range(cols):
			if j > 0:
				left[i][j] = left[i][j - 1] + 1 if grid[i][j - 1] != 'x' else 0
			if i > 0:
				up[i][j] = up[i - 1][j] + 1 if grid[i - 1][j] != 'x' else 0
	max_perimeter = 0
	for i in range(1, rows):
		for j in range(1, cols):
			if grid[i][j] != 'x':
				a = i - up[i][j]
				b = 0
				while a < i and 2 * (i - a) + 2 * (j - b) > max_perimeter:
					b = max(j - left[a][j], j - left[i][j])
					while up[i][b] < i - a and b < j and (2 * (i - a) + 2 * (j - b) > max_perimeter):
						b += 1
					if b < j and left[i][j] >= j - b and (grid[a][b] != 'x'):
						max_perimeter = max(max_perimeter, 2 * (i - a) + 2 * (j - b))
					a += 1
					b = 0
	print(max_perimeter if max_perimeter > 0 else 'impossible')
mn = input().split()
m = int(mn[0])
n = int(mn[1])
grid = []
for _ in range(m):
	grid_item = input()
	grid.append(grid_item)
kMarsh(grid)


import os
import sys

def kMarsh(grid):
	rows = len(grid)
	cols = len(grid[0])
	up = [[0] * cols for _ in range(rows)]
	left = [[0] * cols for _ in range(rows)]
	for i in range(rows):
		for j in range(cols):
			if j > 0:
				left[i][j] = left[i][j - 1] + 1 if grid[i][j - 1] != 'x' else 0
			if i > 0:
				up[i][j] = up[i - 1][j] + 1 if grid[i - 1][j] != 'x' else 0
	max_perimeter = 0
	for i in range(1, rows):
		for j in range(1, cols):
			if grid[i][j] != 'x':
				a = i - up[i][j]
				b = 0
				while a < i and 2 * (i - a) + 2 * (j - b) > max_perimeter:
					b = max(j - left[a][j], j - left[i][j])
					while up[i][b] < i - a and b < j and (2 * (i - a) + 2 * (j - b) > max_perimeter):
						b += 1
					if b < j and left[i][j] >= j - b and (grid[a][b] != 'x'):
						max_perimeter = max(max_perimeter, 2 * (i - a) + 2 * (j - b))
					a += 1
					b = 0
	print(max_perimeter if max_perimeter > 0 else 'impossible')
mn = input().split()
m = int(mn[0])
n = int(mn[1])
grid = []
for _ in range(m):
	grid_item = input()
	grid.append(grid_item)
kMarsh(grid)


import os
import sys

def kMarsh(grid):
	rows = len(grid)
	cols = len(grid[0])
	up = [[0] * cols for _ in range(rows)]
	left = [[0] * cols for _ in range(rows)]
	for i in range(rows):
		for j in range(cols):
			if j > 0:
				left[i][j] = left[i][j - 1] + 1 if grid[i][j - 1] != 'x' else 0
			if i > 0:
				up[i][j] = up[i - 1][j] + 1 if grid[i - 1][j] != 'x' else 0
	max_perimeter = 0
	for i in range(1, rows):
		for j in range(1, cols):
			if grid[i][j] != 'x':
				a = i - up[i][j]
				b = 0
				while a < i and 2 * (i - a) + 2 * (j - b) > max_perimeter:
					b = max(j - left[a][j], j - left[i][j])
					while up[i][b] < i - a and b < j and (2 * (i - a) + 2 * (j - b) > max_perimeter):
						b += 1
					if b < j and left[i][j] >= j - b and (grid[a][b] != 'x'):
						max_perimeter = max(max_perimeter, 2 * (i - a) + 2 * (j - b))
					a += 1
					b = 0
	print(max_perimeter if max_perimeter > 0 else 'impossible')
mn = input().split()
m = int(mn[0])
n = int(mn[1])
grid = []
for _ in range(m):
	grid_item = input()
	grid.append(grid_item)
kMarsh(grid)


import os
import sys

def kMarsh(grid):
	rows = len(grid)
	cols = len(grid[0])
	up = [[0] * cols for _ in range(rows)]
	left = [[0] * cols for _ in range(rows)]
	for i in range(rows):
		for j in range(cols):
			if j > 0:
				left[i][j] = left[i][j - 1] + 1 if grid[i][j - 1] != 'x' else 0
			if i > 0:
				up[i][j] = up[i - 1][j] + 1 if grid[i - 1][j] != 'x' else 0
	max_perimeter = 0
	for i in range(1, rows):
		for j in range(1, cols):
			if grid[i][j] != 'x':
				a = i - up[i][j]
				b = 0
				while a < i and 2 * (i - a) + 2 * (j - b) > max_perimeter:
					b = max(j - left[a][j], j - left[i][j])
					while up[i][b] < i - a and b < j and (2 * (i - a) + 2 * (j - b) > max_perimeter):
						b += 1
					if b < j and left[i][j] >= j - b and (grid[a][b] != 'x'):
						max_perimeter = max(max_perimeter, 2 * (i - a) + 2 * (j - b))
					a += 1
					b = 0
	print(max_perimeter if max_perimeter > 0 else 'impossible')
mn = input().split()
m = int(mn[0])
n = int(mn[1])
grid = []
for _ in range(m):
	grid_item = input()
	grid.append(grid_item)
kMarsh(grid)