AT_abc405_d [ABC405D] Escape Route

> One day, Takahashi visited a cinema and decided to draw arrows on every floor tile, each pointing toward the nearest emergency exit. You are given a grid with $ H $ rows and $ W $ columns. Let $ (i, j) $ denote the cell at the $ i $ -th row from the top and the $ j $ -th column from the left. Each cell is represented by one of the following characters $ S_{i,j} $ : - `.` : corridor cell - `#` : wall cell - `E` : emergency exit For any corridor cell $ (i, j) $ , define $ d(i, j) $ , the distance to the nearest emergency exit, as follows: - Starting from $ (i, j) $ , repeatedly move to an adjacent **non-wall cell** in one of the four cardinal directions (up, down, left, right) until you reach an emergency exit. $ d(i, j) $ is the minimum number of moves required. **It is guaranteed that $ d(i, j) $ is definable for every corridor cell in the given grid**; that is, every corridor cell $ (i, j) $ has at least one emergency exit reachable by passing through only corridor cells. Write exactly one arrow (up, down, left, or right) in every corridor cell so that the following condition holds: - For every corridor cell $ (i, j) $ , if you start at $ (i, j) $ and perform the following action $ d(i, j) $ times, you reach an emergency exit: - Move one cell in the direction of the arrow written in your current cell. (You cannot move into a wall cell or outside the grid.)

The input is given from Standard Input in the following format: > $ H $ $ W $ $ S_{1,1}S_{1,2}\dots S_{1,W} $ $ S_{2,1}S_{2,2}\dots S_{2,W} $ $ \vdots $ $ S_{H,1}S_{H,2}\dots S_{H,W} $

Let $ T_{i,j} $ be the state of cell $ (i, j) $ after writing the arrows. $ T_{i,j} $ is one of the following: - `^` : corridor cell with an upward arrow - `v` : corridor cell with a downward arrow - `` : corridor cell with a rightward arrow - `#` : wall cell - `E` : emergency exit Output the grid in the following format: > $ T_{1,1}T_{1,2}\dots T_{1,W} $ $ T_{2,1}T_{2,2}\dots T_{2,W} $ $ \vdots $ $ T_{H,1}T_{H,2}\dots T_{H,W} $ If multiple solutions exist, any of them will be accepted.

### Sample Explanation 1 Let us verify the condition for $ (2, 3) $ in the sample output. The distance from $ (2, 3) $ to the nearest emergency exit is $ 2 $ , and following the arrows written in the sample output leads to an emergency exit in two moves. The condition can be verified for every other corridor cell as well. ### Sample Explanation 2 There may be cases with no corridor cells or emergency exits. ### Constraints - $ 2 \le H \le 1000 $ - $ 2 \le W \le 1000 $ - Each $ S_{i,j} $ is `.`, `#`, or `E`. - Every corridor cell $ (i, j) $ has at least one reachable emergency exit. - $ H $ and $ W $ are integers.