AT_abc405_d [ABC405D] Escape Route

> ある日、映画館を訪れた高橋君は、館内の全ての床に、最寄りの非常口の方向を示す矢印を描くことにしました。 縦 $ H $ マス、横 $ W $ マスのグリッドが与えられます。グリッドの上から $ i $ 行目、左から $ j $ 列目のマスを $ (i, j) $ と呼びます。 各マスの状態は、次のいずれかの文字 $ S_{i,j} $ で表されます。 - `.` : 通路マス - `#` : 壁マス - `E` : 非常口 任意の通路マス $ (i, j) $ に対して、 $ (i, j) $ と最寄りの非常口との距離 $ d(i, j) $ を次のように定義します。 - $ (i, j) $ からスタートして、上下左右に隣接する **壁マスでないマス** へ移動することを繰り返して非常口に到達する際の、必要な最小の移動回数。 ここで、**入力として与えられるグリッドにおいて、全ての通路マスに対し $ d(i, j) $ が定義可能であることが保証されます**。すなわち、すべての通路マス $ (i, j) $ において、通路マスのみを経由することで到達可能な非常口が少なくとも $ 1 $ つ存在します。 このとき、以下の条件を満たすように、すべての通路マスに対して「上下左右いずれかの方向の矢印」を書き込んでください。 - 各通路マス $ (i, j) $ について、 $ (i,j) $ にいる状態から開始して、以下の操作を $ d(i, j) $ 回行うことで非常口に到達することができる。 - 現在いるマスに書かれた矢印の方向に従って $ 1 $ マス移動する。(ただし、壁マスやグリッドの外へは移動できない。)

入力は以下の形式で標準入力から与えられる。 > $ 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} $

矢印を書き込んだ後のマス $ (i, j) $ の状態を $ T_{i,j} $ とする。 $ T_{i,j} $ は次のいずれかである。 - `^` : 上矢印が書かれた通路マス - `v` : 下矢印が書かれた通路マス - `` : 右矢印が書かれた通路マス - `#` : 壁マス - `E` : 非常口 これらを以下の形式で出力せよ。 > $ 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} $ 答えが複数ある場合は、どれを出力しても正答とみなされる。

### Sample Explanation 1 出力例の $ (2, 3) $ について問題文の条件が成立することを確認します。 $ (2, 3) $ と最寄りの非常口の距離は $ 2 $ です。そして、出力例のように書き込まれた矢印に従って移動することで $ 2 $ 回の移動で非常口に到達することができます。 他の通路マスについても問題文の条件が成立することが確認できます。 ### Sample Explanation 2 通路マスおよび非常口が存在しない場合もあります。 ### Constraints - $ 2 \leq H \leq 1000 $ - $ 2 \leq W \leq 1000 $ - $ S_{i,j} $ は `.`, `#` または `E` - 全ての通路マス $ (i, j) $ について、そこからいずれかの非常口に到達することが可能である - $ H, W $ は整数である