1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
#include <cstdio>
#include <cassert>
#include <cstdlib>
#include <vector>

const int N = 505;
const int K = 500005;
int n, m, k, a[N][N], b[N][N], p[N * N], res[N * N], r[N * N];
char s[N][N + 1], next[N][N + 1], ops[K + 1];
std::vector<int> op;
bool f[N * N];

int tonum(char ch) {
	if (ch == 'L') return 0;
	if (ch == 'D') return 1;
	if (ch == 'P') return 2;
	return 3;
}

void rotate() {
	for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) b[j][n - i - 1] = a[i][j];
	std::swap(a, b);
	std::swap(n, m);
}

void shift() {
	for (int i = 0; i < n; ++i) {
		for (int j = 0, k = 0; k < m;) {
			for (; j < m && !f[a[i][j]]; ++j);
			if (j < m) {
				b[i][k] = a[i][j];
				++k;
			}
			++j;
			if (j >= m) for (j = 0; k < m; ++k, ++j) {
				for (; f[a[i][j]]; ++j);
				b[i][k] = a[i][j];
			}
		}
	}
	std::swap(a, b);
}

void perform_a(int dir) {
	for (int i = 0; i < dir; ++i) rotate();
	shift();
	for (int i = dir; i < 4; ++i) rotate();
}

void perform(int dir) {
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			a[i][j] = i * m + j;
			f[i * m + j] = s[i][j] != '.';
		}
	}
	perform_a(dir);
	for (int i = 0; i < n; ++i) 
		for (int j = 0; j < m; ++j) 
			next[i][j] = s[a[i][j] / m][a[i][j] % m];
	std::swap(next, s);
}

void mul(int *p, int *q) {
	for (int i = 0; i < n * m; ++i) r[i] = q[p[i]];
	for (int i = 0; i < n * m; ++i) p[i] = r[i];
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; ++i) scanf("%s", s[i]);
	scanf("%d%s", &k, ops);
	for (int i = 0; i < k; ++i) {
		int cur = tonum(ops[i]);
		if (op.empty()) op.push_back(cur);
		else if (cur != op.back()) {
			if ((cur ^ 2) == op.back()) {
				op.pop_back();
				if (op.size() <= 1) op.push_back(cur);
			} else if (op.size() == 1 || op[(int)op.size() - 2] != cur) op.push_back(cur);
		}
	}
	for (int i = 0; i < 2; ++i) if (!op.empty()) {
		perform(op.front());
		op.erase(op.begin());
	}
	if (op.size() >= 4) {
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < m; ++j) {
				a[i][j] = i * m + j;
				f[i * m + j] = s[i][j] != '.';
			}
		}
		for (int i = 0; i < 4; ++i) perform_a(op[i]);
		for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) p[a[i][j]] = i * m + j;
		for (int i = 0; i < n * m; ++i) res[i] = i;
		int cnt = op.size() / 4;
		while (cnt) {
			if (cnt & 1) mul(res, p);
			mul(p, p);
			cnt >>= 1;
		}
		for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) next[res[i * m + j] / m][res[i * m + j] % m] = s[i][j];
		std::swap(next, s);
	}
	for (int i = op.size() - op.size() % 4; i < op.size(); ++i) perform(op[i]);
	for (int i = 0; i < n; ++i) printf("%s\n", s[i]);
	return 0;
}