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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <cstring>

#include <utility>
#include <vector>

enum class axis { horizontal, vertical };

char command[500 * 1000 + 10];

char tab[500 * 500];
int perm[500 * 500];
int cycle_perm[500 * 500];
int tmp[500 * 500];

static axis axis_of(char c) {
    return (c == 'G' || c == 'D') ? axis::vertical : axis::horizontal;
}

template<typename Getter>
static void print_state(int height, int width, Getter&& g) {
    char tmp[1024];
    for (int i = 0; i < height; i++) {
        for (int j = 0; j < width; j++) {
            tmp[j] = g(j, i);
        }
        fwrite(tmp, width, sizeof(char), stdout);
        putchar('\n');
    }
}

template<typename Transform, typename Recorder>
static void do_simulate_move(int height, int width, Transform t, Recorder&& r) {
    for (int y = 0; y < height; y++) {
        int stacked = 0;
        for (int x = 0; x < width; x++) {
            const int curr_idx = t(x, y);
            char& curr = tab[curr_idx];
            if (curr == '.') {
                continue;
            }

            const int slot_idx = t(stacked, y);
            char& slot = tab[slot_idx];
            std::swap(curr, slot);
            r(curr_idx, slot_idx);
            stacked++;
        }
    }
}

template<typename Recorder>
static void simulate_move(int height, int width, char c, Recorder&& r) {
    // printf("SIM [%c]\n", c);
    switch (c) {
    case 'P':
        do_simulate_move(height, width, [=] (int x, int y) -> int { return width * y + (width - 1 - x); }, std::move(r));
        break;
    case 'L':
        do_simulate_move(height, width, [=] (int x, int y) -> int { return width * y + x; }, std::move(r));
        break;
    case 'D':
        do_simulate_move(width, height, [=] (int y, int x) -> int { return width * (height - 1 - y) + x; }, std::move(r));
        break;
    case 'G':
        do_simulate_move(width, height, [=] (int y, int x) -> int { return width * y + x; }, std::move(r));
        break;
    default:
        assert(false);
    }
    // print_state(height, width);
}

int main() {
    int height, width;
    scanf("%d %d", &height, &width);

    for (int i = 0; i < width * height; i++) {
        int c = ' ';
        while (c != '.' && c != 'B' && c != 'C') {
            c = getchar();
        }
        tab[i] = (char)c;
    }

    int command_len;
    scanf("%d", &command_len);

    int curr_len = 0;
    
    // Load the command string and perform some cleanups
    for (int i = 0; i < command_len; i++) {
        int c = ' ';
        while (c != 'L' && c != 'G' && c != 'P' && c != 'D') {
            c = getchar();
        }

        command[curr_len] = c;
        curr_len++;

        // printf("Trying to add %c\n", (char)c);

        // Clean up the end of the string
        do {
            // If the command from the top of the stack invalidates the previous
            // command, then override the earlier one
            if (curr_len >= 2 && axis_of(command[curr_len - 2]) == axis_of(command[curr_len - 1])) {
                command[curr_len - 2] = command[curr_len - 1];
                curr_len--;
                // printf("  Overriding previous because it modifies the same axis\n");
                continue;
            }

            // If the command two places before the top command is the same,
            // then pop the last command because it has no effect
            if (curr_len >= 3 && command[curr_len - 3] == command[curr_len - 1]) {
                curr_len--;
                // printf("  Popping because we have no effect\n");
                continue;
            }

            break;
        } while (true);

        // printf("Command so far: %.*s\n", curr_len, command);
    }

    // printf("Cleaned up command: %.*s\n", curr_len, command);

    // Now, the string should only constitute of repeated 4 letter cycles.

    // If there is a small number of commands, execute them manually and quit.
    if (curr_len <= 10) {
        for (int i = 0; i < curr_len; i++) {
            simulate_move(height, width, command[i], [] (int, int) {});
        }
        print_state(height, width, [=] (int x, int y) { return tab[width * y + x]; });
        return 0;
    }

    // Execute some of the first commands, at least two of them
    int initial_to_execute = curr_len % 4;
    if (initial_to_execute < 2) {
        initial_to_execute += 4;
    }
    for (int i = 0; i < initial_to_execute; i++) {
        simulate_move(height, width, command[i], [] (int, int) {});
    }

    // Execute next four moves, recording them to the permutation
    for (int j = 0; j < width * height; j++) {
        cycle_perm[j] = j;
    }
    for (int i = 0; i < 4; i++) {
        simulate_move(height, width, command[initial_to_execute + i], [] (int src, int dst) {
            std::swap(cycle_perm[src], cycle_perm[dst]);
        });
    }

    for (int j = 0; j < width * height; j++) {
        perm[j] = j;
    }

    int cycles = (curr_len - initial_to_execute - 4) / 4;
    while (cycles > 0) {
        if (cycles & 1) {
            for (int i = 0; i < width * height; i++) {
                perm[i] = cycle_perm[perm[i]];
            }
        }
        for (int i = 0; i < width * height; i++) {
            tmp[i] = cycle_perm[i];
        }
        for (int i = 0; i < width * height; i++) {
            cycle_perm[i] = tmp[cycle_perm[i]];
        }

        cycles /= 2;
    }

    print_state(height, width, [=] (int x, int y) { return tab[perm[width * y + x]]; });

    return 0;
}