描述

Bart 的妹妹 Lisa 在一个二维矩阵上创造了新的文明。矩阵上每个位置被三种生命形式之一占据：石头 (R)、剪刀 (S)、布 (P)。

每天，上下左右相邻的不同生命形式将会发生战斗，规则如下：

• 石头 (R) 永远胜剪刀 (S)
• 剪刀 (S) 永远胜布 (P)
• 布 (P) 永远胜石头 (R)

在战斗中，败者的领地会被胜者占领。

你的任务是计算出经过 n 天 后矩阵的占据情况。

输入

• 第一行包含三个正整数 r, c, n，分别表示矩阵的行数、列数以及天数。

  • 1 <= r, c, n <= 100

• 接下来 r 行，每行包含 c 个字符，描述矩阵初始时的情况。

  • 每个位置上的字符只能是 R、S、P
  • 相邻字符之间无空格

输出

• 输出 n 天之后的矩阵占据情况。
• 每个位置上的字符只能是 R、S、P，相邻字符之间无空格。

样例输入

3 3 1
RRR
RSR
RRR

样例输出

RRR
RRR
RRR