Rock-Paper-Scissors War

Statement

Goal

On a two-dimensional rectangular grid, a new civilization emerged.

Within the grid terrain, each location is occupied by one of the five life forms: Rocks, Papers, Scissors, Lizards or Spocks.

The life forms have these code names:
Rock (R)
Paper (P)
sCissors (C)
Lizard (L)
Spock (S)

They defeat each others in a fixed pattern:
Scissors cuts Paper
Paper covers Rock
Rock crushes Lizard
Lizard poisons Spock
Spock smashes Scissors
Scissors decapitates Lizard
Lizard eats Paper
Paper disproves Spock
Spock vaporizes Rock
Rock crushes Scissors

Each day, different life forms occupying horizontally or vertically adjacent grid locations wage war.

At the end of the day, the victor life form will occupy the adjacent location originally owned by the loser.

Day 0          Day 1
+---+---+---+  +---+---+---+
| P | S | C |  | P | P | S |
+---+---+---+  +---+---+---+

A two-front war - Spock wins the war on the right but loses the war on the left.

A life form on a location can have at most four fronts of war on the same day. If it wins at any frontier, it expands to the adjacent location of that front. At the same time if It is defeated by other life forms, it retreats from the original location, or just dies out.

When two different life forms are defeating the life form on the same location at the same time, the two winners will fight each other again to decide who is the final winner to occupy the location at the end of the day.

Day 0          Day 1
+---+---+---+  +---+---+---+
| P | S | L |  | P | L | L |
+---+---+---+  +---+---+---+

Another two-front war - Spock loses both wars at two frontiers. The winners fight again and Lizard wins.

Your task is to determine the territory occupied by each life form after n days.

👉 Life form design is borrowed from another puzzle https://www.codingame.com/training/easy/rock-paper-scissors-lizard-spock. Code reuse is possible.

Input

Line 1: Integers w h n, separated by a space.
w is the width of the terrain
h is the height of the terrain
n is the number of days to pass

The following h lines: Showing what life forms are initially occupying the grid.

Output

Write out what life forms are occupying the grid after battling for n days. The output should have h lines of width w,

Constraints

1 ≤ n ≤ 50
1 ≤ w, h ≤ 100

Example

Input

10 2 4
PPPPPCCCCC
PPPPPPPCCC

Output

PCCCCCCCCC
PPCCCCCCCC

Tags

Rock Paper Scissors, 2D array, Conditions

Difficulty

Medium

Test cases

Example Test

Input

10 2 4 PPPPPCCCCC PPPPPPPCCC

Output

PCCCCCCCCC PPCCCCCCCC

Validator 1 Validator

Input

10 2 5 RRRCCCCCCC RCCCCCCCCC

Output

RRRRRRRRCC RRRRRRRCCC

Win and lose Test

Input

3 3 1 CSC SLS CSC

Output

SLS LLL SLS

Validator 2 Validator

Input

3 3 1 SRS RLR SRS

Output

SSS SRS SSS

Propagation Test

Input

11 9 5 LLLLLLLLLLR LLLLLLLLLLL LLLLLLLLLLL LLRRRRRLLLL LLRPPPRLLLL LLRPCPRLLLL LLRPPPRLLLL LLRRRRRLLLL LLLLLLLLLLL

Output

RRPPCPPRRRR RPPCCCPPRRR PPCCCCCPPRR PCCCCCCCPPR CCCCCCCCCPP CCCCCCCCCCP CCCCCCCCCPP PCCCCCCCPPR PPCCCCCPPRR

Validator 3 Validator

Input

11 8 8 CCCCCCCCCCC CCCCCLCSPCC CCCCCLCSSSC CCCCCLLLCCC CCCCCCCCCCC CCCCCCCCCCC CSCCCCCCCCC CCCCCCCCCCC

Output

SPCSSPCSCPS PCSSPCSSPCP LCSPCSSPSSC SLCSPCSCSCP SSLCSPCPCPS SSSLCSPSPSS SSSSLCSSSSC SSSSSLCCSCP

One fights a hundred Test

Input

14 8 12 CCCCCCCCCCSPCR CCCCCCCCCCCSPC CCCCCCCCCCCCSP CCCCCCCCCCCCCS CCCCCCCCCCCCCC CCCCCCCCCCCCCC CCCCCCCCCCCCCC SCCCCCCCCCCCCC

Output

CRRRRRRRRRRRRR PCRRRRRRRRRRRR SPCRRRRRRRRRRR SSPCRRRRRRRRRR SSSPCRRRRRRRRR SSSSPCRRRRRRRR SSSSSPCRRRRRRR SSSSSSPCRRRRRR

Validator 4 Validator

Input

14 8 6 LLLLLLLLLLLLLL LLLLLLLLLLLLLL LLRRRRLLLLLLLL LLRPRRLLLLLLLL LLRRRRLLLLLLLL LLLLLLLLLLLLLL LLLLLLLLLLLLLL LLLLLLLLLLLLLC

Output

PPPPPPPRRRLLLL PPPPPPPPRRRLLC PPPPPPPPPRRRCC PPPPPPPPPPRRCC PPPPPPPPPRRRCC PPPPPPPPRRRCCC PPPPPPPRRRCCCC RPPPPPRRRCCCCC

Linear 1 Test

Input

100 1 30 PLPLPCLLCSPLCPPSSPCLLSPSCLLLLLSPSRSCPPRPPPRLRCSCPCCRSSSCSSSRLCCSPRRCCSPSRPPLSRSLPCRCCLCPSLPLLPSRLCLS

Output

CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCLLPPSCLLLLLPPSSSRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR

Validator 5 Validator

Input

100 1 15 LLRRSPPSLLRSPPSRRSRLLLSSPLCLLCSCLRSLPCSSCCCRLCSSCRLRSCPLSRRLCSRSRRPRLPPLLLSPSRPSRCSLPRRRLLLPPLCRLLSR

Output

PPPPPPPPPPPPPPPPPPPPLLCSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSCLLPPPPPPPPPPPRLLLLLLLLLLLLLLLLP

Linear 2 Test

Input

1 15 5 P R R S C C S L L S C R P R P

Output

P P L L L L L L L L L L L L P

Validator 6 Validator

Input

1 15 5 P L R C C L C C C R S P S C R

Output

R R R R R S P P P P P P P P P

Random Test

Input

30 20 35 SLRLRPCCPCRSRPLPPSPSCRLSRLSLSR SLCPRPSRLLCPCRRSPCSPLCSPPSRRPC LSLSSSPCCCCSSLLLRRCRRLCPPRLSLS PPCRLRRCSPLCRLPPSRCRLSCSPCSRLC PPPCCCPCLRPCCLLSLLPPSLSCPCPLPL RSRLCCSSCSRLSCLCSPLSLCLRRSLSLC CRCPCRLCCRSLPSRRRLPCCPSSRRLCRR RLCCCPSSSRPSSRRCSSCCPPRPSRRRRC PPRSCLCLPRCPCCCRSSLLCSSLRCCCPP CSSCLCLPPRRRCRRRSRPSCSPPLRRSCP RPRRCRPLRCSCSPPRCCCPCPPCCRRLPP RCRRPLCLCPPPLSRCCPLPRLCRCSRRSC LLPCSSCPPSSRLRCPPLSLRPPRSSLPRP RSSRPLPLRCSSPPCCSRSSCCCPSRLRPR CSRSSRCLPCRSSSCRLPCSSCSRCRPSCL PSCSRPSSLRPPLRPCSLSPCCSCLLPSLP CRPPCCRCCSPLCSSPSRSLPRLRPCPRLL PLLRLPCPRRSSPSPSCRRPPCCCRRLLRS RCRLLLLRSCRCRSPPRRRPLCSSRCCRLP SRCSSSSLPPRRCSPSLCSSLLLPLCCLRC

Output

PCSPCRPRSCSLSLLLSCLRLCPLPRSLSC RPCSCCCPPSCCRSRPLLRPCSLLCLCLRP SPCCCCSPCPSLPCLCSCLRLRPRSCPRSC PCRPRPCCRSCSPSCPRCLLLLCSLLRLLP SPCRRPSPPCSPCPSCPLSRPCSCPLSLSR SSPSPCCCPPCPRCPPRSLPCSLLRLRSSR PSSCSLSLSPCRCPSRCLLRLCSCLLPCLS CPPRCRCRLCCCPSCCCSCLCPCPLSSLRL RSCPRPCPRLSCSCLLCRPCRPPCSRPLPS PCPRRPPRLSPCPSCLCRPLPLPCRPLRLP CRCPPLRCSSLPCPSCLCLRPRCSCRPSPS PPLCRPPRCCCSSCPSCSCRCPSSSPSLRL RRRPCRCPRLLCLLSSSLSPLRRLPCSCRS PCLPLRPPLPPCSRSLCRCRCPPRLPPLRR SPPSPSPRRSLCSCLSRSLCPPCLPCSCPL SCPPSLLRSLCSLRSLCSCRPCSCPPRLRP PCSCRRPLLSLCSLRSRLLLRLSLRSCPSR SPSPSRSPRLSLCLLRLSPCSSSSLSSSSL CPSSRSLRRLLSLSSLSCRPCSRPSSCCRL PSPCLRSLSPRLSRSLCLLRPCPCSCPPLP

Validator 7 Validator

Input

30 20 35 CLLCLLCCCPRSSLLSRLPLRPRRRLCPPR SRCSLCLCCCLRCPPPPLPPPSSSRRLSPC CRLPPRPPPLRRSRPCPCRRCPPSPPLRPS PPPCLPRLRRCCLSLSLPRPLLSCCSLSCS PLPPCLPRRLRRRSCRCCSSPRPCCRSRLL PRPRPSSPRRPRLLSSPSLRRCCCLRCPLP SPRSPSLCPPSLLPRPLSCCLRLPRPSSLS PPSCSCLCLLRCLRCLCSPPLPCPSPPCLR SRCRLRSRPLRCRCLPRSLRSCPSRLSCLR CLSCPCPRLSPRSLPCRCLRPPCSPSSLCS PCPPSRPSPPPPRSPRSLSCPSCCLRCSLP LSLLCLPLRRLRLRLCSPCPCPCPLSLCPS SCRSLCRSRCRSLPRLLLPLLPPSLPLCCP CPCSSLPPPRCSRLCCPPLSCLLCLCPSRP SRSRSLRLRSLRLSLRLSRRSLSPCCRCSP LCRRRRLSSPCCSPSLRPCCCPCPSLSSRL SLLRRCCPPRCLLSSSSLLRSLLCRSLRSL PPPPCSSSSLPLRPCCRCCCRRCRSLLRSC CRSRPCPLSCCPSSLPRPRRSRPLPRRSPS PLLCSLPRPCPSLRPSPPRPSRCRCSCLPR

Output

LRPCPPRRLCPLCSSLSCRPLPRSLLSCCL RPCRPLPPRRSPCPLCLCCRRCPLCCLSSL RPPRRRPCPPPCSLCSCSPCPRCCSSLCSC CLRLCLRRRLPPSSLPCSCCRSCCLCSCLC LRLLRCSPRCPSPCCSSLCLCLRPSLCCLS PSLRSSLLPRCPSCSPCCSSPLSRPPLSSC SLRSLLRRLPRPPSPCSCPSLLLSCLCCCL LRSLCLSPRLRLLCSSLCSCSRSCLRSLSS CSPSSLRCRRPRRLCRCCSLCPRLLSRLPR CSCPSSRLPRCPPCRPLLPCRRPLRRRPRP SLSSCLLRRCLPPLRLCSRLPRCPPLLRRL CRPSLSRPCPRRRPPCRPLPRRPRRRSLSR PLLRSPLRLPRPCPRPRRPRSRRLCLRSRL LSPLRRCCPPSRLPLRRRPRLSRPSCLPRP RRLPLRPSPLRPRLCRSRCLCRCSLSPRCS PLPRPRRCLRPCSCRSLRPSPSLSCCLSCL RPRSRRPRCLPPPSCRCRRPCSSPCSCCCS RRCLRPCCSPSPLRPCLSPRPSPCSSSRLS SLLPLRCSCCPSCLRPRRCPSLRPRLSPRL RSRRSLCLRPRCSPLRLCPRSSSRSSSCPR

Diamonds Test

Input

20 20 35 RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRSRRRR RRRRCRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRLLRRRRRRR RRRRRRRRRRPLLRRRRRRR RRRRRRRRRRRLLRRRRRRR RRRRRRRRRRRLLRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRPRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR

Output

RPLLRPLLRPLPRLLPRLLP PLLRPLLRPLLLPRLLPRLL LLRPLLRPLLRLLPRLLPRL LRPLLRPLLRPRLLPRLLPR RPLLRPLLRPLPRLLPRLLP PLLRPLLRPLLLPRLLPRLL LLRPLLRPLLRLLPRLLPRL LRPLLRPLLRPRLLPRLLPR RPLLRPLLRPLPRLLPRLLP PLLRPLLRPLLLPRLLPRLL LLRPLLRPLLRPRLLPRLLP PLLRPLLRPLLLPRLLPRLL RPLLRPLLRPLPRLLPRLLP LRPLLRPLLRPRLLPRLLPR LLRPLLRPLLRLLPRLLPRL PLLRPLLRPLLLPRLLPRLL RPLLRPLLRPLPRLLPRLLP LRPLLRPLLRPRLLPRLLPR LLRPLLRPLLRLLPRLLPRL PLLRPLLRPLLLPRLLPRLL

Validator 8 Validator

Input

20 20 35 LLLLLLLLLLLLLLLLLLLL LLLLLLLLLLLLLLLLLLLL LLLLLLLLLLLLLLLLLLLL LLLLLLLLLLLLLLLLLLLL LLLLLLLLLLLLLLLLLLLL LLLLLLLLLLLLLLLLLLLL LLLLLLLLLLLLLLLLLLLL LLLLLLLLLLLLLLLLLLLL LLLLLLLLLLLLLLLLLLLL LLLLLLLLLLLLLLLLLLLL LLLLLLLLLLLLLLLLLLLL LLLLLLLLLLLLLLLLLLLL LLLLRLLLLLLLLLLLLLLL LLLPRLLLLLLLLLLLLLLL LLLLRLLLLLLLLLLLLLLL LLLLLLLLLLLLLLLLLLLL LLLLLLLLLLLLLLLLLLLL LLLLLLLLLLLLLLLLLLLL LLLLLLLLLLLLLLLLLLLL LLLLLLLLLLLLLLLLLLLL

Output

LRRPLPRRLPRRLPRRLPRR RRPLRLPRRLPRRLPRRLPR RPLRRRLPRRLPRRLPRRLP PLRRPRRLPRRLPRRLPRRL LRRPLPRRLPRRLPRRLPRR RRPLRLPRRLPRRLPRRLPR RPLRRRLPRRLPRRLPRRLP PLRRPRRLPRRLPRRLPRRL LRRPLPRRLPRRLPRRLPRR RRPLRLPRRLPRRLPRRLPR RPLRRRLPRRLPRRLPRRLP PLRRPRRLPRRLPRRLPRRL LRRPLPRRLPRRLPRRLPRR PLRRRLPRRLPRRLPRRLPR LRRPLPRRLPRRLPRRLPRR PLRRPRRLPRRLPRRLPRRL RPLRRRLPRRLPRRLPRRLP RRPLRLPRRLPRRLPRRLPR LRRPLPRRLPRRLPRRLPRR PLRRPRRLPRRLPRRLPRRL

United Kingdom Test

Input

10 10 40 LLLLLLLLLL LLLLLLLLLL LLLLLLLLLL LLLLLLLLLL LLLLLLLLLL LLLLLLLLLL LLLLLLLLLL LLLLLLLLLL LLLLLLLLLL LLLLLLLLLL

Output

LLLLLLLLLL LLLLLLLLLL LLLLLLLLLL LLLLLLLLLL LLLLLLLLLL LLLLLLLLLL LLLLLLLLLL LLLLLLLLLL LLLLLLLLLL LLLLLLLLLL

Validator 9 Validator

Input

10 7 39 CCCCCCCCCC CCCCCCCCCC CCCCCCCCCC CCCCCCCCCC CCCCCCCCCC CCCCCCCCCC CCCCCCCCCC

Output

CCCCCCCCCC CCCCCCCCCC CCCCCCCCCC CCCCCCCCCC CCCCCCCCCC CCCCCCCCCC CCCCCCCCCC

United States Test

Input

10 10 38 LLLLLLLLLL LLLLLLLPLL LPPPPPPPLL LPPPPPLPLL LLLPCPLLLL PLLPPPLLLL LLLLLLLPLL LPPLLPPPLL LPPLLLLLLL LLLLLLLLLL

Output

CCCCCCCCCC CCCCCCCCCC CCCCCCCCCC CCCCCCCCCC CCCCCCCCCC CCCCCCCCCC CCCCCCCCCC CCCCCCCCCC CCCCCCCCCC CCCCCCCCCC

Validator 10 Validator

Input

10 10 37 CCCCCCCCCC CSCCCCCCCC CCCCCCCCCC CCCCCCCCCC CCCCCCCCCC CCCCCCCCCC CCCCCCCCCC CCCCCCCCCC CCCCRCCCCC CCCCCCCCCC

Output

SSSSSSSSSS SSSSSSSSSS SSSSSSSSSS SSSSSSSSSS SSSSSSSSSS SSSSSSSSSS SSSSSSSSSS SSSSSSSSSS SSSSSSSSSS SSSSSSSSSS

Solution language

Solution

Stub generator input

Comments

7 Comments

CyberLemonade Unnamed CodinGamer

about 5 years ago

✅ Approved the contribution. Comment: Cool problem

selenae Unnamed CodinGamer

✅ Approved the contribution. Comment: I like it!

Stilgart Unnamed CodinGamer

❌ Rejected the contribution. Comment: 1 ≤ n ≤ 1,000,000,000 -> We already have dozens of puzzles that demand memoization and loop detection. We don't need yet another one, so please remove this aspect of the puzzle. edit: I have removed my refusal.

java_coffee_cup Unnamed CodinGamer

The loop can be from 1 to some hundreds for different cases. If the limit was adjusted to 1000 do you think it will improve the puzzle?

Deltaspace Unnamed CodinGamer

✅ Approved the contribution. Comment: