Under construction

Still being built. Things may change

Legendary Dango Maker 1

Time limit1sMemory limit512 MB

Summary
Given a grid of pink, white, and green dangos, maximize the number of sticks in pink-white-green or green-white-pink order, with each dango used once.
Level

Medium6 of 10

Topics
Matrix, Graph, 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 cells with R rows and C columns. Each cell contains one dango. The color of a dango is pink (P), white (W), or green (G). You will choose three consecutive dangos in the vertical direction (from top to bottom), the horizontal direction (from left to right), or the oblique direction (from left-top to right-bottom, or from right-top to left-bottom). Then you will take three dangos from these cells from end to end, and skewer them to a stick in order, to get a stick of dangos. For example, if you choose three consecutive dangos in the vertical direction, you can take dangos from top-middle-bottom or bottom-middle-top cells, in this order, and skewer them to a stick. You cannot take dangos from middle-bottom-top or bottom-top-middle cells. You cannot skewer a dango to more than one stick.

A stick of dangos is beautiful if the colors of the dangos in the stick are pink-white-green or green-white-pink, in this order. You want to make as many beautiful sticks of dangos as possible.

How many beautiful sticks of dangos can you make?

Input

For this task, there is one input data.

The input is given in the following format.

R C
D1
.
.
.
DR

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

Output

Print the following format.

S1
.
.
.
SR

Each Si (1 ≤ i ≤ R) is a string of length C consisting of P, W, G, |, -, , and /. The j-th character of Si describes how to skewer the dango in the cell located in the i-th row from the top and the j-th column from the left.

  • The j-th character is | if you make a beautiful stick using that cell, the adjacent cell above, and the adjacent cell below.
  • The j-th character is - if you make a beautiful stick using that cell, the adjacent cell to the left, and the adjacent cell to the right.
  • The j-th character is \ if you make a beautiful stick using that cell, the touching cell left above, and the touching cell right below.
  • The j-th character is / if you make a beautiful stick using that cell, the touching cell right above, and the touching cell left below.
  • Otherwise, the j-th character is P, W, or G according to the color of the dango in that cell, the same as the j-th character of Di.

Constraints

3 ≤ R ≤ 500. 3 ≤ C ≤ 500. Di (1 ≤ i ≤ R) is a string of length C consisting of P, W, and G.

Examples2

  1. Example 1

    Input
    3 4
    PWGP
    WGPW
    GWPG
    
    Expected output
    P-GP
    WGP|
    G-PG
    
  2. Example 2

    Input
    3 4
    PWWP
    WWWW
    PGGP
    
    Expected output
    PWWP
    W\/W
    PGGP