Escape the Maze

You are given a maze represented as a grid of size \(n \times m\) along with a corresponding trap grid of the same size. Each cell in the maze is either open (represented by .) or blocked by a wall (represented by #). Similarly, each cell in the trap grid contains either 0 (safe) or 1 (trap). Your task is to determine whether it is possible to escape the maze from the top-left corner \((0,0)\) to the bottom-right corner \((n-1, m-1)\) using only moves in the four cardinal directions (up, down, left and right).

A valid move must satisfy the following conditions:

• The destination cell is within the bounds of the maze.
• The destination cell is not a wall (#).
• The destination cell does not contain a trap (i.e. the corresponding trap value is 0).

If there exists a sequence of moves that leads from the start to the goal, output "Escaped"; otherwise, output "Trapped".

inputFormat

The input is given via standard input (stdin) and has the following format:

<n> <m>
<row 1 of maze>
<row 2 of maze>
... 
<row n of maze>
<row 1 of traps>
<row 2 of traps>
... 
<row n of traps>

Each maze row contains exactly m tokens (each token is either . or #), and each trap row contains m integers (either 0 or 1) separated by spaces.

outputFormat

Output a single line to standard output (stdout) containing either Escaped if there exists a valid path from the top-left corner to the bottom-right corner, or Trapped otherwise.

3 3
. # .
. . .
# # .
0 0 0
0 0 0
0 1 0

Escaped