Wards

Hanbyeol was hit by an Isekai Chaos Bus on his way to work.

Figure B.1: Isekai Chaos Bus

Figure B.2: Hanbyeol going to work

He used up all of his vacation days this year and needs to get back to Pangyo right away. To find a way home, he decides to explore the isekai.

The isekai is an $R\times C$ grid. It is night, so Hanbyeol can see only the cell he is standing on and the cells directly above, below, left, or right of it. Placing a ward lets him see a wider area. Every cell belongs to exactly one region. When a ward is placed, Hanbyeol can see every cell in the region that contains the cell where the ward was placed.

Given Hanbyeol's travel log, compute how much of the isekai he can see.

The first line contains two integers $R$ and $C$, the size of the grid. ($1 \le R,C \le 1\,000$)

The next $R$ lines describe the grid. Each line has $C$ lowercase English letters. If two orthogonally adjacent cells have the same letter, they belong to the same region.

The next line contains two integers $H\_R$ and $H\_C$, the cell where Hanbyeol fell into the isekai. He landed in row $H\_R$ from the top and column $H\_C$ from the left. ($1 \le H\_R \le R$, $1 \le H\_C \le C$)

The last line contains a string of at most $200\,000$ characters describing Hanbyeol's travel log. Each character is one of U, D, L, R, or W. U, D, L, and R mean he moved one cell up, down, left, or right. W means he placed a ward on his current cell. The log never takes him outside the grid.

Print $R$ lines of $C$ characters each, showing Hanbyeol's view. In row $i$, column $j$, print . if that cell is visible to Hanbyeol, and # if it is not.