Problem:
 Score : 200 points    Problem Statement  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 .        Sample Input 1 4 5
##...
.##..
..##.
...##      Sample Output 1 Possible  The matrix can be generated by a 7 -move sequence: right, down, right, down, right, down, and right.       Sample Input 2 5 3
###
..#
###
#..
###      Sample Output 2 Impossible       Sample Input 3 4 5
##...
.###.
.###.
...##      Sample Output 3 Impossible

Solution (Python):
h,w = map(int, input().split())
cnt=0
for i in range(h):
    a = list(input())
    for tmp in a:
        if tmp=="
            cnt+=1
if cnt==h+w-1:
    print("Possible")
else:
    print("Impossible")

Solution (Python):
h,w=map(int,input().split());print("Possible" if sum([input().count("

Solution (Python):
h,w=map(int,input().split())
a=[input() for _ in range(h)]
if sum([i.count("
    print("Possible")
else:
    print("Impossible")

Solution (Python):
h,w = list(map(int, input().split()))

board = []
board.append(['.'] * (w+2))
for i in range(h):
    board.append(list('.' + input() + '.'))
board.append(['.'] * (w+2))

for i in range(1,h+1):
    for j in range(1,w+1):
        left = board[i][j-1]
        upper = board[i-1][j]
        if left == '
            print('Impossible')
            exit()
print('Possible')

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 

def ii(): return int(sys.stdin.readline().rstrip()) 
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) 
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]

def ss(): return sys.stdin.readline().rstrip() 
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) 
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]





h,w=mii()

mat=[list(ss()) for _ in range(h) ]
cnt=0
for i in range(h):
    for j in range(w):
        if mat[i][j]=="
            cnt+=1

if cnt==h+w-1:
    print("Possible")
else:
    print("Impossible")

Solution (Python):
H, W = map(int, input().split())
G = [input() for i in range(H)]
done = [[False]*W for i in range(H)]
def dfs(h, w):
    done[h][w] = True
    if h == H-1 and w == W-1:
        return
    if w+1 < W and G[h][w+1] == "
        dfs(h, w+1)
    elif h+1 < H and G[h+1][w] == "
        dfs(h+1, w)
dfs(0, 0)
ans = True
for i in range(H):
    for j in range(W):
        if G[i][j] == "
            if not done[i][j]:
                ans = False
if ans:
    print("Possible")
else:
    print("Impossible")

Solution (Python):
import math
import fractions



def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ZipArray(a):
    aa = [[a[i],i]for i in range(n)]

    aa.sort(key = lambda x : x[0])
    for i in range(n):
        aa[i][0]=i+1
    aa.sort(key = lambda x : x[1])
    b=[aa[i][0] for i in range(len(a))]
    return b

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

def Zeros(a,b):
    if(b<=-1):
        return [0 for i in range(a)]
    else:
        return [[0 for i in range(b)] for i in range(a)]

def AddV2(v,w):
    return [v[0]+w[0],v[1]+w[1]]

dir4 = [[1,0],[0,1],[-1,0],[0,-1]]


def clamp(x,y,z):
    return max(y,min(z,x))

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
            

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    
    def same_check(self, x, y):
        return self.find(x) == self.find(y)


'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 6 + 2
fact = [1, 1]  
factinv = [1, 1]  
inv = [0, 1]  

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

'''














h,w = list(map(int, input().split()))
data=[]

for i in range(h):
    data.append(input())

now = [0,0]
goal = [h-1,w-1]

count = 0
for i in range(h):
    for j in range(w):
        if(data[i][j]=='

if(count!=h+w-1):
    print("Impossible")
    exit()
            
            
while(True):
    if(now==goal):
        print("Possible")
        exit()
    a1='?'
    a2='?'
    if(now[1]!= w-1): a1 = data[now[0]][now[1]+1]
    if(now[0]!= h-1): a2 = data[now[0]+1][now[1]]
    if(a1=='
        now = AddV2(now,[0,1])
        continue
    if(a2=='
        now = AddV2(now,[1,0])
        continue
    if(a1!='
        print("Impossible")
        exit()
    if(a1=='
        print("Impossible")
        exit()

Solution (Python):
H,W=map(int,input().split())
print("Possible" if H+W-1==sum(input().count("

Solution (Python):
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")

Solution (Python):
H, W = map(int,input().split())

s = [list(input()) for _ in range(H)]

sharp_count = 0

for h in range(H):
  sharp_count += s[h].count("

if sharp_count == H+W-1:
  print("Possible")
else:
  print("Impossible")

Solution (Python):


H, W = map(int, input().split())
cnt = 0
for i in range(H):
    cnt += input().count('

if cnt == H+W-1: print('Possible')
else: print('Impossible')

Solution (Python):
h,w=map(int,input().split())
a=str()
for i in range(h):
    a+=input()
print('Possible' if a.count('

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

Solution (Python):
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]

cnt = sum([row.count("
print("Possible" if cnt == h + w - 1 else "Impossible")

Solution (Python):
from collections import deque
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]

queue = deque()
queue.append([0, 0])
visited = [[False] * w for _ in range(h)]
visited[0][0] = True

def judge():
    for i in range(h):
        for j in range(w):
            if a[i][j] == "
                return False
    return True
def bfs(queue):
    while len(queue) > 0:
        n_y, n_x = queue.popleft()
        if 0 <= n_x < w - 1 and 0 <= n_y < h - 1:
            if a[n_y][n_x + 1] == "
                print("Impossible")
                exit()
        for i, j in [[0, 1], [1, 0]]:
            y, x = n_y + i, n_x + j
            if 0 <= x < w and 0 <= y < h:
                if a[y][x] == "
                    queue.append([y, x])
                    visited[y][x] = True
    print("Possible" if judge() else "Impossible")
bfs(queue)

Solution (Python):
h, w = map(int, input().split())
L = [input() for _ in range(h)]
r = 0
for i in range(h):
    for j in range(w):
        if L[i][j] == '
            if j < r:
                print('Impossible')
                exit()
            else:
                r = j
else:
    print('Possible')

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

Solution (Python):
import sys
h, w = map(int, input().split())
f = [list(map(str, input().rstrip())) for _ in range(h)]

for i in range(h - 1):
    for j in range(w - 1):
        if (f[i][j] == "
            print("Impossible")
            sys.exit()

print("Possible")

Solution (Python):
h,w = map(int,input().split())
a = [input() for _ in range(h)]

cnt = 0
for x in range(h):
    for y in range(w):
        cnt += (a[x][y]=='
if(cnt > h+w-1):
    print('Impossible')
    exit()


x,y = 0,0
while(x+y<h+w-2):
    dx,dy=0,0

    if(x!=h-1):
        if(a[x+1][y]=='
            dx = 1
    if(y!=w-1):
        if(a[x][y+1]=='
            dy = 1
    if(dx+dy!=1):
        print('Impossible')
        exit()

    x += dx
    y += dy

print('Possible')

Solution (Python):
def answer(matrix):
    h = len(matrix)
    w = len(matrix[0])
    P, IM = ("Possible", "Impossible")
    cp = [0, 0] 
    rightBottom = [len(matrix)-1, len(matrix[0])-1]
    while(True):
        matrix[cp[0]][cp[1]] = '.'
        
        if cp[0] > 0 and matrix[cp[0]-1][cp[1]] == '
        
        if cp[1] > 0 and matrix[cp[0]][cp[1]-1] == '
        
        if cp[0]+1 < h and matrix[cp[0]+1][cp[1]] == '
            if cp[1]+1 < w and matrix[cp[0]][cp[1]+1] == '
                return IM
            cp[0] = cp[0]+1
            continue
        
        if cp[1]+1 < w and matrix[cp[0]][cp[1]+1] == '
            cp[1] = cp[1]+1
            continue
        if cp[0] == rightBottom[0] and cp[1] == rightBottom[1]:
            return P
    return P

h, w = map(int, input().split())
matrix = []
for _ in range(h):
    row = [c for c in input()]
    matrix.append(row)
print(answer(matrix))

Solution (Python):
H, W = map(int, input().split())
A = [input() for i in range(H)]

visited = [[False]*W for i in range(H)]
visited[0][0] = True
d = [[0, 0, -1, -1]]
while d:
  x, y, px, py = d.pop()
  num = 0
  flag = False
  for dx, dy in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
    if 0<=x+dx<H and 0<=y+dy<W and [x+dx, y+dy]!=[px, py] and A[x+dx][y+dy]=='
      visited[x+dx][y+dy] = True
      num += 1
      d.append([x+dx, y+dy, x, y])
      if dx < 0 or dy < 0:
        flag = True
  if (num >= 2) or flag:
    print('Impossible')
    quit()

print('Possible')

Solution (Python):











import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log 
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    H,W=MI()
    grid=[ST() for _ in range(H)]
    
    ans = True
    stack = [(0,0)]
    visited = set()
    while(stack):
        v = stack.pop()
        visited.add(v)
        for dh,dw in [(-1,0), (1,0), (0,-1), (0,1)]:
            to_h,to_w = v[0]+dh, v[1]+dw
            if(not(0<=to_h<H) or not(0<=to_w<W)):
                continue
            if(to_h,to_w) in visited:
                continue
            if(grid[to_h][to_w] == "
                ans = False
            if(grid[to_h][to_w] == "
                stack.append((to_h,to_w))
        if(len(stack) >= 2): 
            ans = False   
    if(ans):
        print("Possible")
    else:
        print("Impossible")
if __name__ == '__main__':
    main()

Solution (Python):


def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    

    
    

    h,w = map(int, input().split())
    s = 0
    for _ in range(h):
        a = input().rstrip()
        s += a.count('

    if s == h+w-1:
        print('Possible')
    else:
        print('Impossible')

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    

    
    

    h,w = map(int, input().split())
    a = [list(input().rstrip()) for _ in range(h)]
    
    s = 0
    for i in range(h):
        for j in range(w):
            if a[i][j] == '
                if s != j:
                    print('Impossible')
                    exit()
                s +=  1
        s -= 1

    if s == w-1:
        print('Possible')
    else:
        print('Impossible')

if __name__ == '__main__':
    main()

Solution (Python):
M = []
ans = []

def main():
    H,W = map(int, input().split())  
    for i in range(H):
        M.append(input())
        ans.append('.' * W)

    bfs(0,0)

    for i in range(H):
        if(M[i] != ans[i]):
            print('Impossible')
            return
    print('Possible')


def bfs(x,y):
    if(x>=len(M) or y>=len(M[0])):
        return False
    if(M[x][y]=='
        str_list = list(ans[x])
        str_list[y] = '
        ans[x] = "".join(str_list) 
        if(bfs(x,y+1) & bfs(x+1,y)):
            
            str_list = list(ans[0])
            str_list[0] = '.'
            ans[0] = "".join(str_list) 
        return True
    return False


if __name__ == '__main__':
    main()

Solution (Python):
h, w = map(int, input().split())
li = [['x']*(w+2)]
li += [list('x' + input() + 'x') for _ in range(h)]
li += [['x']*(w+2)]

x = 1
y = 1

flag = 1
while flag:
    li[y][x] = 'o'

    if li[y][x+1] == '
        x += 1
    elif li[y+1][x] == '
        y += 1
    else:
        break

for i in range(h+2):
    for j in range(w+2):
        if li[i][j] == '
            print('Impossible')
            break
    else:
        continue
    break
else:
    print('Possible')

Solution (Python):
h,w = map(int,input().split())
field = [list(input()) for i in range(h)]
 
tmp=0
for i in range(h):
    for j in range(w):
        if field[i][j]=='
            tmp+=1
if (h+w-1)==tmp:
    print('Possible')
else:
    print('Impossible')

Solution (Python):
H, W = map(int, input().split())
A = []
for _ in range(H):
    A.append(input())

r = 0

for a in A:
    flag = False
    if '
        print('Impossible')
        exit()
    for i in range(r, W):
        if a[i] == '
            if flag:
                print('Impossible')
                exit()
            r = i
        else:
            flag = True
            
print('Possible')

Solution (Python):
h,w = map(int,input().split())
field = [list(input()) for i in range(h)]

tmp=0
for i in range(h):
    for j in range(w):
        if field[i][j]=='
            tmp+=1
if (h+w-1)==tmp:
    print('Possible')
else:
    print('Impossible')

Solution (Python):
h,w = map(int,input().split())
l = [list(input()) for _ in range(h)]
n = [0,1,0,-1]
m = [1,0,-1,0]


def dfs(a,b):
  if 0<=a+n[0] and a+n[0]<=w-1 and 0<=b+m[0] and b+m[0]<=h-1 and 0<=a+n[1] and a+n[1]<=w-1 and 0<=b+m[1] and b+m[1]<=h-1:
    if l[b+m[0]][a+n[0]]=="
      return print("Impossible")
  for i in range(4):
    if 0<=a+n[i] and a+n[i]<=w-1 and 0<=b+m[i] and b+m[i]<=h-1:
      if l[b+m[i]][a+n[i]]=="
        if i==2 or i==3:
          return print("Impossible")

        elif a+n[i]==w-1 and b+m[i]==h-1:
          cou = 0
          for i in l:
            for j in i:
              if j=="
                cou += 1
          if cou==2:
            return print("Possible")
          else:
            return print("Impossible")
        else:
          l[b+m[i]][a+n[i]] = "."
          
          return dfs(a+n[i],b+m[i])
  else:
    return print("Impossible")
      
    
        
dfs(0,0)

Solution (Python):

from collections import Counter

h,w = map(int, input().split())

_list = []
for i in range(h):
    _list += list(input())

if _list.count("
    print("Possible")
else:
    print("Impossible")

Solution (Python):
h,w=map(int,input().split());print(("Imp"if sum(input().count("

Solution (Python):
h,w=map(int,input().split());print(("Imp"if sum(input().count("

Solution (Python):
import sys
h, w = map(int, input().split())
a = [input() for i in range(h)]
t = 0
for i in range(h):
    for j in range(w):
        if a[i][j] == "
            if j < t:
                print("Impossible")
                sys.exit()
            t = j
print("Possible")

Solution (Python):
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')

Solution (Python):
import sys
h,w = map(int,input().split())
A = []
for i in range(h):
    A.append(list(input()))
dx = [1,0,]
dy = [0,1,]
B = [[0,0]]
while B:
    S = B.pop()
    cnt = 0
    if S == [w-1,h-1]:
        A[h-1][w-1] = "."
        for L in A:
            if L.count("
                print("Impossible")
                sys.exit()
        else:
            print("Possible")
            break
    for i in range(2):
        x = S[0] + dx[i]
        y = S[1] + dy[i]
        if 0 <= x <= w-1 and 0 <= y <= h-1 and A[y][x] == "
            B.append([x,y])
            cnt += 1
    else:
        if cnt != 1:
            print("Impossible")
            break
        else:
            A[S[1]][S[0]] = "."

Solution (Python):
H, W = [int(hoge) for hoge in input().split()]
print("Possible") if sum([input().count("

Solution (Python):
def solve():
    H, W = map(int, input().split())
    A = [[i for i in input()] for _ in range(H)]
    
    x, y = 0, 0
    A[y][x] = '.'
    while True:
        if 0 <= x+1 < W and 0 <= y < H and A[y][x+1] == '
            x=x+1
            A[y][x] = '.'
        elif 0 <= x < W and 0 <= y+1 < H and A[y+1][x] == '
            y=y+1
            A[y][x] = '.'
        else:
            break
    
    for row in A:
        if '
            return 'Impossible'

    return 'Possible' if x == W-1 and y == H-1 else 'Impossible'

print(solve())

Solution (Python):
import sys

H, W = map(int, sys.stdin.readline().strip().split())

grid = []
for _ in range(H):
    grid.append(list(sys.stdin.readline().strip()))

count = 0
for i in range(H):
    for j in range(W):
        if grid[i][j] == "
            count += 1

if count == H + W - 1:
    print("Possible")
else:
    print("Impossible")

Solution (Python):
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')

Solution (Python):
from itertools import chain

H, W = map(int, input().split())
count = 0
for _ in range(H):
    l = list(input())
    count += l.count("

if count == H+W - 1:
    print("Possible")
else:
    print("Impossible")

Solution (Python):
a,b=map(int,input().split())
l=[]
for _ in range(a):
    l1=input()
    l.append(l1)
flag=True
for i in range(b):
    for j in range(a):
        if i>=1 and j!=a-1 and l[j][i]=='
            for k1 in range(i):
                for k2 in range(j+1,a):
                    if l[k2][k1]=='
                        flag=False
                        break
for i in range(b):
    for j in range(a):
        if i!=b-1 and j>=1 and l[j][i]=='
            for k3 in range(j):
                for k4 in range(i+1,b):
                    if l[k3][k4]=='
                        flag=False
                        break
if flag==True:
    print('Possible')
else:
    print('Impossible')

Solution (Python):
def myAnswer(H:int,W:int,A:list) -> str:
   counter = 0
   for a in A:
      counter += a.count("
   return "Possible" if(counter == H + W - 1) else "Impossible"

   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   


def modelAnswer():
   return
def main():
   H,W = map(int,input().split())
   A = []
   for _ in range(H):
      A.append(list(input()))
   print(myAnswer(H,W,A))
if __name__ == '__main__':
   main()

Solution (Python):
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")

Solution (Python):


h, w = map(int, input().split())
a = [str(input()) for _ in range(h)]
jud = [[] for _ in range(h)]

for i in range(h):
    for j in range(w):
        if a[i][j] == '
            jud[i].append(j)



flag = True

for k in range(len(jud) - 1):
    if max(jud[k]) in jud[k + 1] and jud[k][-1] == jud[k + 1][0]:
        continue
    else:
        flag = False

if flag:
    print("Possible")
else:
    print('Impossible')

Solution (Python):
import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal

sys.setrecursionlimit(10000001)
INF = sys.maxsize
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))



def main():
    h, w = ns()
    mat = [list(sys.stdin.readline()) for _ in range(h)]

    total = h + w - 1
    cnt = 0
    for i in range(h):
        for j in range(w):
            if mat[i][j] == "
                cnt += 1

    if cnt != total:
        print("Impossible")
        exit(0)

    def dfs(x, y):
        if x == w-1 and y == h-1:
            print("Possible")
            exit(0)

        if x + 1 < w:
            if mat[y][x + 1] == "
                dfs(x + 1, y)
        if y + 1 < h:
            if mat[y + 1][x] == "
                dfs(x, y + 1)

    dfs(0, 0)
    print("Impossible")


if __name__ == '__main__':
    main()

Solution (Python):


H, W = map(int, input().split())
now = 0
judge = 0

for h in range(H):
    route = input()
    w = 0
    while w<W and route[w]=='.':
        w += 1
    if w!=now:
        break
    while w<W-1 and route[w+1]=='
        w += 1
    now = w
    while w<W-1 and route[w+1]=='.':
        w += 1
    if w<W-1:
        break
    if h==H-1 and now==W-1:
        judge = 1

ans = ['Impossible', 'Possible']
print(ans[judge])

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

Solution (Python):
def main():
  H, W = list(map(int, input().split()))

  count = 0

  for i in range(H):
    row = input()
    for j in range(W):
      if(row[j] == '
        count += 1

  print("Possible" if W + H - 1 == count else "Impossible")

if __name__ == "__main__":
  main()

Solution (Python):
def main():
  H, W = list(map(int, input().split()))

  count = 0

  for i in range(H):
    row = input()
    for j in range(W):
      if(row[j] == '
        count += 1

  print("Possible" if W + H - 1 == count else "Impossible")

if __name__ == "__main__":
  main()

Solution (Python):
h,w = [int(x) for x in input().split()]
a = [input() for _ in range(h)]

ans = "Possible"
for i in range(h-1):
    for j in range(w-1):
        if a[i][j+1] == a[i+1][j] == "
            ans = "Impossible"
            break
print(ans)

Solution (Python):
h, w = map(int, input().split())
a = []
for i in range(h):
    a.append(list(input()))

now_x = 0
now_y = 0
while(True):
    if now_x+1 <w and a[now_y][now_x+1] == "
        a[now_y][now_x] = "."
        now_x+=1

    elif now_y+1 <h and a[now_y+1][now_x] == "
        a[now_y][now_x] = "."
        now_y+=1

    else:
        a[now_y][now_x] = "."
        break

check = True
for i in a:
    for j in i:
        if j == "
            check = False

print("Possible" if check else "Impossible")

Solution (Python):
import numpy as np


H,W = map(int,input().split())
board = [[] for _ in range(H)]
for i in range(H):
    board[i] = list(input())

board = np.array(board)

minnum = W
maxnum = 0
for row in board[::-1]:
    S = "".join(row)
    left = S.find("
    right = len(S) - 1 - S[::-1].find("
    if right > minnum:
        print("Impossible")
        exit()
    minnum = left
    maxnum = right

board = board.T

minnum = H
maxnum = 0
for row in board[::-1]:
    S = "".join(row)
    left = S.find("
    right = len(S) - 1 - S[::-1].find("
    if right > minnum:
        print("Impossible")
        exit()
    minnum = left
    maxnum = right

print("Possible")

Solution (Python):
h,w = map(int,input().split())
A = [input() for _ in range(h)]
D  = ((0,1), (1,0))

from collections import deque
queue = deque([((0,0), [])])

cand = []
while queue:
  p, path = queue.popleft()
  x, y = p
  path = path + [p]
  for dx,dy in D:
    nx,ny = x+dx, y+dy
    if not (0<=nx < h and 0<= ny < w):
      continue
    if A[nx][ny] != '
      continue
    if nx == h-1 and ny == w-1:
      cand.append(path+[(nx,ny)])
      continue
    queue.append(((nx,ny),path))

for c in cand:
  for i in range(h):
    for j in range(w):
      if A[i][j] == '.':
        continue
      elif (i,j) not in c:
        break
    else:
      continue
    break
  else:
    print('Possible')
    break
else:
  print('Impossible')

Solution (Python):
import sys
from collections import deque
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    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"))


if __name__ == '__main__':
    main()

Solution (Python):
h, w = map(int, input().split())

ans = 0
for i in range(h):
  ans += input().count("

print("Possible" if h + w - 1 == ans else "Impossible")

Solution (Python):
h , w = map(int,input().split())
ma = [list(input()) for i in range(h)]
ans = []
for i in range(h):
    kar = []
    for j in range(w):
        if ma[i][j] =="
            kar.append(j)
    ans.append(kar)


for i in range(h-1):
    if max(ans[i]) != min(ans[i+1]):
        print("Impossible")
        exit()
        
print("Possible")

Solution (Python):
import numpy as np
h, w = map(int,input().split())
way = []
for i in range(h):
    s = input()
    for j in range(w):
        if s[j] == "
            way.append([i,j])

for i in range(len(way)-1):
    if (way[i+1][0]-way[i][0])+(way[i+1][1]-way[i][1]) == 1 and (way[i+1][0]-way[i][0])*(way[i+1][1]-way[i][1]) == 0:
        continue
    else:
        print("Impossible")
        exit()

print("Possible")

Solution (Python):
def resolve():
    '''
    code here
    '''
    import collections
    H, W = [int(item) for item in input().split()]

    grid = [[item for item in input()] for _ in range(H)]

    cnt = 0
    for line in  grid:
        for i in line:
            if i == '
                cnt += 1

    if cnt > H + W -1:
        print('Impossible')
    else:
        print('Possible')

if __name__ == "__main__":
    resolve()

Solution (Python):
h, w = map(int, input().split())
a = []
for _ in range(h):
    a.append(input())

pos = (0, 0)
pre = 1
nxt = 0
while True:
    x, y = pos
    if x<w-1 and a[y][x+1]=='
        nxt += 1
        pos = (x+1, y)
    if y<h-1 and a[y+1][x]=='
        nxt += 1
        pos = (x, y+1)
    if x>0 and a[y][x-1]=='
        pre += 1
    if y>0 and a[y-1][x]=='
        pre += 1
    if pos==(w-1, h-1) and nxt==0 and pre==1:
        print('Possible')
        break
    if nxt!=1 or pre!=1:
        print('Impossible')
        break
    pre = 0
    nxt = 0

Solution (Python):
h, w = map(int, input().split())
a = []
for _ in range(h):
    a.append(input())

pos = (0, 0)
pre = 1
nxt = 0
while pos!=(w-1, h-1):
    x, y = pos
    if x<w-1 and a[y][x+1]=='
        nxt += 1
        pos = (x+1, y)
    if y<h-1 and a[y+1][x]=='
        nxt += 1
        pos = (x, y+1)
    if x>0 and a[y][x-1]=='
        pre += 1
    if y>0 and a[y-1][x]=='
        pre += 1
    if nxt!=1 or pre!=1:
        print('Impossible')
        break
    pre = 0
    nxt = 0
else:
    tmp = 0
    for i in a:
        tmp += i.count('
    if tmp!=h+w-1:
        print('Impossible')
    else:
        print('Possible')

Solution (Python):
import collections
h,w = map(int,input().split())
a = []
cnt = 0
for i in range(h):
    aa = list(input())
    c = collections.Counter(aa)
    cnt += c['
    a.append(aa)
cnt -= 1
if cnt == h+w-2:
    print('Possible')
else:
    print('Impossible')

Solution (Python):
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"))