output_description: If it is possible that Shik only uses right and down moves, print `Possible`.
  Otherwise, print `Impossible`.
  
  * * *
input_description: 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}
attempt: from collections import deque
  
  # 下右1マスを検索するために必要とする
  dis_x = [1, 0]
  dis_y = [0, 1]
  
  # 迷路の縦幅,横幅
  max_h, max_w = map(int, input().split())
  
  s = []
  av_count = 0
  for _ in range(max_h):
      line = input()
      av_count += line.count("#")
      # 横1マスを壁でPadding. これでindex out of boundを防ぐ
      s.append(list(".{}.".format(line)))
  
  # 縦1マスを壁でPadding. これでindex out of boundを防ぐ
  s = [list("." * (max_w + 2))] + s + [list("." * (max_w + 2))]
  
  # 迷路と同じサイズの距離表を作成.
  # 値が0 -> 未訪問, それ以外 -> スタート地点からそれまでの距離となる
  dist = [[0] * (max_w + 2) for _ in range(max_h + 2)]
  
  # キューにスタート地点をプッシュ
  que = deque([(1, 1)])
  
  # キューに値が格納されている間
  while que:
      # 先頭の値を取り出す
      h, w = que.popleft()
  
      for i in range(2):
          # 移動距離
          dx, dy = dis_x[i], dis_y[i]
          if s[h + dy][w + dx] == "#" and dist[h + dy][w + dx] == 0:
              # ここまでの距離+1して訪問済みに
              dist[h + dy][w + dx] = dist[h][w] + 1
              # キューに加える -> (h+dy, w+dx) を起点にまた上下左右4マスをチェックする,という意味
              que.append((h + dy, w + dx))
              break
  
  dist[1][1] = 1
  
  dis = 0
  for line in dist:
      dis += len(list(filter(lambda x: x != 0, line)))
  
  print("Possible" if av_count == dis else "Impossible")
  
problem_description: 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.
samples: [{"input": "4 5\n    ##...\n    .##..\n    ..##.\n    ...##", "output": "Possible\n    \n\nThe matrix can be generated by a 7-move sequence: right, down, right, down,\nright, down, and right.\n\n* * *"}, {"input": "5 3\n    ###\n    ..#\n    ###\n    #..\n    ###", "output": "Impossible\n    \n\n* * *"}, {"input": "4 5\n    ##...\n    .###.\n    .###.\n    ...##", "output": "Impossible"}]