탈옥

당신은 21세기 최고의 컴퓨터 과학자 중 한 명이며, 방금 정수 인수분해를 다항 시간에 푸는 알고리즘을 발견했다. 안타깝게도 비밀경호국이 이 연구를 알아챘다. 그들은 알고리즘을 압수하고 당신을 지하 감옥인 연방 범죄자 교도소에 가뒀다. 당신은 탈출해서 연구 결과를 공개하고 정의를 찾기로 굳게 마음먹었다.1

감옥에서 탈출할 수 있는 출구는 감옥의 최상층에만 있다. 당신은 지금 최하층의 가장 왼쪽 칸에 있으며, 이 층은 지면에서 $h$층 아래에 있다. 천장의 구멍을 통해 위로 올라가려면 사다리가 필요하다. 다만 낙법을 연습해 두었고 위아래로 바로 겹치는 구멍 두 개는 없으므로, 사다리 없이도 구멍으로 뛰어내릴 수 있다. 주어진 감옥의 구조에서 탈출이 가능한지 판단하라.

감옥 안에는 사다리가 있다. 사다리를 들고 구멍을 통해 위아래로 이동할 수는 없고, 다른 층의 사다리를 가져올 수도 없다. 하지만 같은 층에서 벽으로 둘러싸인 같은 구역 안의 다른 칸으로는 사다리를 옮길 수 있다. 바닥이나 천장의 구멍은 (몇 개든) 뛰어넘을 수 있다.

1 걱정하지 마라. 이 알고리즘은 다항 시간에 동작하지만 실제로는 빠르지 않다.

입력은 다음과 같다.

첫 줄에 두 정수 $w$와 $h$가 주어진다($3 \leq w \leq 10^5$, $1 \leq h \leq 10^5$, $w \cdot h \leq 3 \cdot 10^5$). 감옥의 너비와 높이다.

이어서 각각 $w$개의 문자로 이루어진 $2h+1$개의 줄이 주어진다.

• 홀수 번째 줄의 문자는 - 또는 .이며, 각각 천장 또는 천장의 구멍을 나타낸다. 마지막 줄은 바닥이므로 -만 있다.
• 짝수 번째 줄의 문자는 |, ., L 중 하나이며, 각각 벽, 빈 칸, 사다리를 나타낸다. 첫 문자와 마지막 문자는 항상 벽이다.

천장의 구멍(홀수 번째 줄) 바로 위와 아래에 있는 층(짝수 번째 줄)의 칸에는 벽이 없다. 천장에서 위아래로 바로 겹치는 구멍은 두 개가 없다. 시작 칸(왼쪽 아래 칸)은 벽이 아니다.

탈출할 수 있으면 possible을, 그렇지 않으면 impossible을 출력한다.