Legendary Dango Maker 2

Time limit1sMemory limit512 MB

Summary

Find non-overlapping runs of three consecutive grid cells that read P-W-G or G-W-P, then mark each chosen run by its direction in the output grid.

Level: Medium6 of 10
Topics: Greedy, Matrix, Implementation
Solved: No attempts yet

Problem

You are a professional making delicious rice dumplings, called dangos. Now you are skewering dangos with sticks.

Dangos are located in a rectangular grid of $R$ rows and $C$ columns. Each cell contains one dango. The color of a dango is pink (P), white (W), or green (G).

You choose three consecutive dangos in the vertical direction (top to bottom), the horizontal direction (left to right), or the oblique direction (left-top to right-bottom, or right-top to left-bottom). Then you take the three dangos from these cells, end to end, and skewer them onto a stick in order to get a stick of dangos. For example, if you choose three consecutive dangos vertically, you can take them from the top-middle-bottom or bottom-middle-top cells, in this order. You cannot take them from the middle-bottom-top or bottom-top-middle cells. You cannot skewer a dango onto more than one stick.

A stick of dangos is beautiful if its colors, in order, are pink-white-green or green-white-pink.

How many beautiful sticks of dangos can you make?

Input

The input is given in the following format.

R C
D1
.
.
.
DR

$D_i$ ( $1 \le i \le R$ ) is a string of length $C$ consisting of P, W, and G. The $j$ -th character of $D_i$ ( $1 \le j \le C$ ) is the color of the dango in the cell in row $i$ from the top and column $j$ from the left.

Output

Output $S_1$ to $S_R$ , where each $S_i$ is a string of length $C$ consisting of P, W, G, |, -, \, and /. The $j$ -th character of $S_i$ is:

| if the dango in that cell, the adjacent cell above, and the adjacent cell below form a beautiful stick.
- if the dango in that cell, the adjacent cell to the left, and the adjacent cell to the right form a beautiful stick.
\ if the dango in that cell, the cell diagonally left above, and the cell diagonally right below form a beautiful stick.
/ if the dango in that cell, the cell diagonally right above, and the cell diagonally left below form a beautiful stick.
Otherwise, the color character P, W, or G of that cell, the same as the $j$ -th character of $D_i$ .

Constraints

$3 \le R \le 500$
$3 \le C \le 500$
Each $D_i$ is a string of length $C$ consisting of P, W, and G.

Examples2

Example 1
Input
```
3 4
PWGP
WGPW
GWPG
```
Expected output
```
P-GP
WGP|
G-PG
```
Example 2
Input
```
3 4
PWWP
WWWW
PGGP
```
Expected output
```
PWWP
W\/W
PGGP
```