Time Limit: 1s
Memory Limit: 128MB
r x c 격자공간의 마을에 사람들이 살고있다. 각 사람들은 가위타입 바위타입 보타입 세 종류의 성질(?)을 지니고있다. 이 마을사람들은 사이가 좋지않아 매일밤마다 이웃끼리 대판 싸움을 벌인다고한다. 그런데 모두가 알다시피 가위는 보를 이기고, 보는 바위를 이기고 바위는 가위를 이긴다. 상성상 우위를 가진 이웃은 자신의 능력을 활용해서 다음날 아침에 자신의 타입으로 바꿔버린다고 한다. 즉, 바위타입과 가위타입이 이웃이라면, 다음날 아침에 가위타입이 바위타입으로 전향해버린다. 타입이 같으면 아무 일도 일어나지 않는다.
타입의 전향은 다음날 아침에 일어나는 일이기 때문에 이웃을 회귀시킨 자기 자신의 타입도 전향될 수 있다. 즉 PRS 이렇게 한줄로 이웃된 경우, 하루뒤 가위타입은 바위타입으로 전향되고, 바위타입은 보타입으로 전향된다. 즉 PPR 이 된다.
가위바위보 타입은 완벽한 상하관계에 놓여있기 때문에 타입이 전향된 결과는 유일하다.
오늘 아침에 이 마을사람들의 타입에 대한 정보를 알고있다. N일이 지난 뒤 아침에 마을사람들의 타입을 구해보자. 이웃은 격자좌표상에서 택시기하거리가 1인 사람들을 의미하며, 마을 사람들은 매일 밤마다 하루도 거르지않고 싸운다.
입력의 첫째줄엔 테스트케이스의 개수 t가 주어진다.
각 테스트케이스마다 첫째줄에는 세 정수 r, c, 그리고 n이 주어진다. r과 c는 격자의 크기이다.( 1 <= r,c <= 100, 1 <= n <= 100 )
그 다음 r개의 줄에 걸쳐 길이가 c인 문자열이 주어진다. 이는 마을주민들의 타입의 정보이다. P는 보, R는 바위, S는 가위 타입이다. 이 이외의 타입을 가진 사람은 없으며, 마을에 빈집도 없다.
각 테스트케이스마다 n일 뒤 아침에 마을사람들의 타입 상태를 출력한다. 케이스결과물 사이에 줄바꿈으로 구분한다.
2 3 3 1 RRR RSR RRR 3 4 2 RSPR SPRS PRSP
RRR RRR RRR RRRS RRSP RSPR