AtCoder Grand Contest 007 - Shik and Stone

We have a grid of H rows and W columns. Initially, there is a stone in the top left cell. Shik is trying to move the stone to the bottom right cell. In each step, he can move the stone one cell to its left, up, right, or down (if such cell exists). It is possible that the stone visits a cell multiple times (including the bottom right and the top left cell).

You are given a matrix of characters a_{ij} (1 \leq i \leq H, 1 \leq j \leq W). After Shik completes all moving actions, a_{ij} is `#` if the stone had ever located at the i-th row and the j-th column during the process of moving. Otherwise, a_{ij} is `.`. Please determine whether it is possible that Shik only uses right and down moves in all steps.

Constraints

* 2 \leq H, W \leq 8
* a_{i,j} is either `#` or `.`.
* There exists a valid sequence of moves for Shik to generate the map a.

Input

The input is given from Standard Input in the following format:


H W
a_{11}a_{12}...a_{1W}
:
a_{H1}a_{H2}...a_{HW}


Output

If it is possible that Shik only uses right and down moves, print `Possible`. Otherwise, print `Impossible`.

Examples

Input

4 5
##...
.##..
..##.
...##


Output

Possible


Input

4 5
...
.##..
..##.
...##


Output

Possible


Input

5 3

..#

..


Output

Impossible


Input

4 5
...
.###.
.###.
...##


Output

Impossible

Source: atcoder | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
(H, W) = map(int, input().split())
print(['Imp', 'P'][H + W - 1 == sum((input().count('#') for _ in range(H)))] + 'ossible')


(h, w) = map(int, input().split())
cnt = 0
for _ in range(h):
	cnt += input().count('#')
if cnt == h + w - 1:
	print('Possible')
else:
	print('Impossible')


(H, W, A) = open(0).read().split(maxsplit=2)
if A.count('#') == int(H) + int(W) - 1:
	print('Possible')
else:
	print('Impossible')


(N, M) = input().split()
c = 0
for i in range(int(N)):
	a = list(input())
	for j in a:
		if j == '#':
			c += 1
if c == int(N) + int(M) - 1:
	print('Possible')
else:
	print('Impossible')


(h, w) = map(int, input().split())
a = [list(input()) for i in range(h)]
sum = 0
for b in a:
	sum += b.count('#')
if sum == h + w - 1:
	print('Possible')
else:
	print('Impossible')


(h, *a) = open(0)
print(('Imp' * (sum((x.count('#') for x in a)) != eval(h.replace(' ', '+')) - 1) or 'P') + 'ossible')


(H, W) = map(int, input().split())
s = 0
for i in range(H):
	A = list(input())
	s += A.count('#')
if s == H + W - 1:
	print('Possible')
else:
	print('Impossible')


(H, W) = map(int, input().split(' '))
A = [input() for _ in range(H)]
print(['Impossible', 'Possible'][''.join(A).count('#') == H + W - 1])


(h, w) = map(int, input().split())
v = sum((sum((1 for i in input() if i == '#')) for _ in range(h)))
if v == h + w - 1:
	print('Possible')
else:
	print('Impossible')


(h, w) = map(int, input().split())
a = ''
for i in range(h):
	a = a + input()
if a.count('#') == h + w - 1:
	print('Possible')
else:
	print('Impossible')


(H, W) = map(int, input().split())
A = [input() for _ in range(H)]
if H + W - 1 == sum((a.count('#') for a in A)):
	print('Possible')
else:
	print('Impossible')


t = open(0).read()
print('I mPp'[t.count('#') < int(t[0]) + int(t[2])::2] + 'ossible')


(H, W) = map(int, input().split())
suma = 0
for i in range(H):
	a = input()
	suma += a.count('#')
if suma == H + W - 1:
	print('Possible')
else:
	print('Impossible')


(H, W) = map(int, input().split())
shortest = H - 1 + (W - 1)
tmp = -1
for i in range(H):
	tmp += input().count('#')
print('Possible' if tmp == shortest else 'Impossible')


(H, W) = map(int, input().split())
cnt = 0
for _ in range(H):
	l = input()
	cnt += l.count('#')
if cnt == H + W - 1:
	print('Possible')
else:
	print('Impossible')


import sys

def input():
	return sys.stdin.readline().rstrip()
(H, W) = map(int, input().split())
count = 0
for _ in range(H):
	count += input().count('#')
print('Possible' if count == H + W - 1 else 'Impossible')


(H, W) = map(int, input().split())
A = [list(input()) for _ in range(H)]
ans = 'Impossible'
cnt = 0
for a in A:
	cnt += a.count('#')
if cnt == H + W - 1:
	ans = 'Possible'
print(ans)


t = open(0).read()
print(('P' * (t.count('#') < sum(map(int, t.split()[:2]))) or 'Imp') + 'ossible')


(h, w) = [int(i) for i in input().split()]
a = [input().count('#') for i in range(h)]
print(['Impossible', 'Possible'][sum(a) == h + w - 1])


(h, w) = map(int, input().split())
a = [list(input()) for _ in range(h)]
cnt = sum([row.count('#') for row in a])
print('Possible' if cnt == h + w - 1 else 'Impossible')


(h, w) = map(int, input().split())
print(('Imp' if sum((input().count('#') for i in [0] * h)) != h + w - 1 else 'P') + 'ossible')


(h, w) = map(int, input().split())
a = [list(input()).count('#') for i in range(h)]
print(['Imp', 'P'][sum(a) == h + w - 1] + 'ossible')


(h, w) = list(map(int, input().split()))
temp = 0
for i in range(h):
	temp += input().count('#')
print('Possible' if temp == h + w - 1 else 'Impossible')


(h, w) = map(int, input().split())
fld = ''.join([input() for _ in range(h)])
if fld.count('#') == h + w - 1:
	print('Possible')
else:
	print('Impossible')


(H, W) = map(int, input().split())
count = 0
for i in range(H):
	Ai = input()
	for c in Ai:
		if c == '#':
			count += 1
ans = 'Possible' if count == H + W - 1 else 'Impossible'
print(ans)


(H, W) = map(int, input().split())
ans = 0
for _ in range(H):
	s = input()
	A = list((x for x in s))
	ans += A.count('#')
if ans == H + W - 1:
	print('Possible')
else:
	print('Impossible')


(h, w) = map(int, input().split())
a = [input() for _ in range(h)]
c = 0
for i in a:
	for j in i:
		if j == '#':
			c += 1
if c == h + w - 1:
	print('Possible')
else:
	print('Impossible')


(H, W) = map(int, input().split())
L = [list(input()) for i in range(H)]
cnt = 0
for i in L:
	c = i.count('#')
	cnt += c
if cnt == H + W - 1:
	print('Possible')
else:
	print('Impossible')


(a, b) = map(int, input().split())
cnt = 0
for i in range(a):
	s = input()
	cnt += s.count('#')
if cnt == a + b - 1:
	print('Possible')
else:
	print('Impossible')


(h, w) = map(int, input().split())
f = [input() for _ in range(h)]
res = 0
for i in range(h):
	res += f[i].count('#')
if res == h + w - 1:
	print('Possible')
else:
	print('Impossible')


(h, w) = map(int, input().split())
a = [input() for _ in range(h)]
result = ''.join(a).count('#') == h + w - 1
print(['Impossible', 'Possible'][result])


(h, w) = map(int, input().split())
A = [input() for _ in range(h)]
sp = 0
for line in A:
	if line.find('#') != sp:
		print('Impossible')
		exit()
	sp = line.rfind('#')
print('Possible')


(n, m) = map(int, input().split())
arr = [input() for _ in range(n)]
for i in range(n - 1):
	if m - 1 - arr[i][::-1].index('#') > arr[i + 1].index('#'):
		print('Impossible')
		break
else:
	print('Possible')


(a, b, *c) = open(0).read().split()
if int(a) + int(b) - 1 == sum((i.count('#') for i in c)):
	print('Possible')
else:
	print('Impossible')


(H, W) = map(int, input().split())
fields = [list(input()) for i in range(H)]
cnt = 0
for f in fields:
	cnt += f.count('#')
if cnt == H + W - 1:
	print('Possible')
else:
	print('Impossible')


(H, W) = map(int, input().split())
A = [input() for h in range(H)]
count = 0
for a in A:
	count += a.count('#')
print('Possible' if H + W - 1 == count else 'Impossible')


(h, w) = map(int, input().split())
sums = 0
for i in range(h):
	sums += str(input()).count('#')
if sums == h + w - 1:
	print('Possible')
else:
	print('Impossible')


(H, W) = map(int, input().split())
c = sum((input().count('#') for _ in [0] * H))
print('Possible' if c == H + W - 1 else 'Impossible')


(h, w) = map(int, input().split())
c = 0
for _ in range(h):
	a = list(input())
	c += a.count('#')
print('Possible' if c == h + w - 1 else 'Impossible')


(h, w) = map(int, input().split())
a = []
for i in range(h):
	x = input()
	a.append(x)
cnt = 0
for i in range(h):
	cnt += a[i].count('#')
if cnt == h + w - 1:
	print('Possible')
else:
	print('Impossible')


from itertools import chain
(h, w) = map(int, input().split())
As = list(chain.from_iterable([list(input()) for i in range(h)]))
print('Possible' if As.count('#') == h + w - 1 else 'Impossible')


(H, W) = map(int, input().split())
A = ''
for i in range(H):
	A += input()
n = A.count('#')
if n == H + W - 1:
	print('Possible')
else:
	print('Impossible')


import sys
(h, w) = map(int, input().split())
c = 0
for i in range(h):
	s = input()
	c += s.count('#')
if c == h + w - 1:
	print('Possible')
else:
	print('Impossible')


(h, w) = map(int, input().split())
a = []
for _ in range(h):
	a.append(input())
n = 0
for ai in a:
	n += ai.count('#')
print('Possible' if n == h + w - 1 else 'Impossible')


(h, w) = map(int, input().split())
cnt = 0
for i in range(h):
	s = input()
	for j in range(len(s)):
		if s[j] == '#':
			cnt += 1
print('Possible') if cnt == h + w - 1 else print('Impossible')


(A, B) = list(map(int, input().split()))
l = []
for i in range(A):
	l.append(list(input()))
c = 0
for i in range(A):
	c += l[i].count('#')
print('Possible' if A + B - 1 == c else 'Impossible')


(H, W) = map(int, input().split())
A = [input() for _ in range(H)]
c = 0
for i in range(H):
	c += A[i].count('#')
if c == H + W - 1:
	print('Possible')
else:
	print('Impossible')


import sys
import os
(H, W) = map(int, input().split())
cntS = 0
for i in range(H):
	cntS += list(input()).count('#')
if cntS == H + W - 1:
	print('Possible')
else:
	print('Impossible')


(h, w) = map(int, input().split())
A = [input().count('#') for _ in range(h)]
print('Impossible' if h + w - 1 != sum(A) else 'Possible')


(h, w) = map(int, input().split())
c = 0
for i in range(h):
	(a, b) = (input(), [])
	for j in range(w):
		b.append(a[j])
	c += b.count('#')
print('Possible' if h + w - 1 == c else 'Impossible')


(H, Y) = map(int, input().split())
K = 0
for i in range(H):
	K += input().count('#')
if K == H + Y - 1:
	print('Possible')
else:
	print('Impossible')


(h, w) = [int(v) for v in input().split()]
v = 0
for i in range(h):
	v += input().count('#')
if v == h + w - 1:
	print('Possible')
else:
	print('Impossible')


(h, w) = map(int, input().split())
n = 0
for y in range(h):
	s = input()
	for c in s:
		if c == '#':
			n += 1
if n == h + w - 1:
	print('Possible')
else:
	print('Impossible')


(H, W) = map(int, input().split())
t = 0
for k in range(H):
	t += input().count('#')
print('Possible' if t == H + W - 1 else 'Impossible')


(h, w) = map(int, input().split())
a = [str(input()) for _ in range(h)]
ans = 0
for i in range(h):
	ans += a[i].count('#')
if ans == h + w - 1:
	print('Possible')
else:
	print('Impossible')


from collections import Counter
(h, w) = list(map(int, input().split()))
num = sum((Counter(input())['#'] for _ in range(h)))
print('Possible' if w + h - 1 == num else 'Impossible')


(h, m) = list(map(int, input().split()))
count = h + m
for i in range(h):
	b = list(input())
	count -= b.count('#')
if count == 1:
	print('Possible')
else:
	print('Impossible')


(h, w) = map(int, input().split())
c = sum((input().count('#') for _ in '*' * h))
print('Impossible Possible'.split()[c == h + w - 1])


(A, B) = list(map(int, input().split()))
L = []
for i in range(A):
	L.append(list(input()))
k = 0
for j in range(A):
	k += L[j].count('#')
print('Possible' if A + B - 1 == k else 'Impossible')


(h, w) = map(int, input().split())
(a, b) = (0, 0)
ans = 'Possible'
for y in range(h):
	m = input()
	a = m.find('#')
	if a < b:
		ans = 'Impossible'
		break
	b = m.rfind('#')
print(ans)


(H, W) = map(int, input().split())
ans = 0
for _ in range(H):
	a = input()
	ans += a.count('#')
if ans == H + W - 1:
	print('Possible')
else:
	print('Impossible')


(h, w) = map(int, input().split())
print(['Impossible', 'Possible'][sum([list(input()).count('#') for _ in [0] * h]) == h + w - 1])


(H, W) = map(int, input().split())
table = [input() for _ in range(H)]
path_length = sum([t.count('#') for t in table])
if path_length == H + W - 1:
	print('Possible')
else:
	print('Impossible')


(H, W) = [int(hoge) for hoge in input().split()]
print('Possible') if sum([input().count('#') for h in range(H)]) == H + W - 1 else print('Impossible')


(h, w) = map(int, input().split())
array = [input().count('#') for x in range(h)]
print('Possible' if sum(array) == h + w - 1 else 'Impossible')


(h, w) = map(int, input().split())
a = [input() for _ in range(h)]
black = sum((s.count('#') for s in a))
if black == h + w - 1:
	print('Possible')
else:
	print('Impossible')


(H, W) = map(int, input().split())
ans = 0
for i in range(H):
	A = input()
	for j in range(W):
		if A[j] == '#':
			ans += 1
if ans + 1 == H + W:
	print('Possible')
else:
	print('Impossible')


(N, M) = map(int, input().split(' '))
maze = [list(input()) for i in range(N)]
tmp = 0
for i in range(N):
	tmp += maze[i].count('#')
if tmp == N + M - 1:
	print('Possible')
else:
	print('Impossible')


(h, w) = map(int, input().split())
g = [input() for _ in range(h)]
num = 0
for i in range(h):
	num += g[i].count('#')
if h + w == num + 1:
	print('Possible')
else:
	print('Impossible')


(H, W) = map(int, input().split())
moves = 0
for h in range(H):
	S = str(input())
	for s in S:
		if s == '#':
			moves += 1
if moves == H + W - 1:
	print('Possible')
else:
	print('Impossible')


(H, W) = map(int, input().split())
(gy, gx) = (H - 1, W - 1)
grid = ['' for i in range(H)]
touched = 0
for i in range(H):
	grid[i] = input()
	touched += grid[i].count('#')
print(('Imp', 'P')[touched == H + W - 1] + 'ossible')


(h, w) = map(int, input().split())
num = 0
s = [str(input()) for i in range(h)]
for i in range(h):
	num += s[i].count('#')
if num > h + w - 1:
	print('Impossible')
	exit()
print('Possible')


(x, y) = list(map(int, input().split()))
l = []
for i in range(x):
	l.append(list(input()))
val = 0
for j in range(x):
	val += l[j].count('#')
print('Possible' if x + y - 1 == val else 'Impossible')


(h, w) = map(int, input().split())
s = []
sh = 0
for i in range(h):
	t = input()
	sh += t.count('#')
	s.append(t)
if sh == h + w - 1:
	print('Possible')
else:
	print('Impossible')


(h, w) = map(int, input().split())
a = []
for i in range(h):
	a.append(list(input()))
ans = 0
for i in a:
	ans += i.count('#')
if ans == h + w - 1:
	print('Possible')
else:
	print('Impossible')


(*t,) = open(0)
print(['Imp', 'P'][int(t[0][0]) + int(t[0][2]) - 1 == sum((s.count('#') for s in t[1:]))] + 'ossible')


(H, W) = map(int, input().split())
tb = [list(input()) for _ in range(H)]
cnt = 0
for i in range(H):
	cnt += tb[i].count('#')
if cnt == H + W - 1:
	print('Possible')
else:
	print('Impossible')


(H, W) = map(int, input().split())
P = sum([list(input()).count('#') for i in range(H)])
if P == H + W - 1:
	print('Possible')
else:
	print('Impossible')


(h, w) = map(int, input().split())
l = [input() for i in range(h)]
p = [1, 1]
cnt = 0
for i in range(h):
	cnt += l[i].count('#')
if cnt == h + w - 1:
	print('Possible')
else:
	print('Impossible')