题解说明

问题背景：
给定一个 $n \times m$ 网格，格子取值为 '.'（空）、'B'、'C'。给出一串操作序列（字符 $U/D/L/R$ 或映射自其他字母），每个操作会把所有非空格子往指定方向“紧缩”（不改变相对顺序，去掉中间空白，贴到边）。要求执行整段操作后输出最终网格。

核心逻辑：

1. 移动模型（move）：

• 对 $U/D$：逐列独立处理，把非零元素依次紧缩到列顶/列底。
• 对 $L/R$：逐行独立处理，把非零元素依次紧缩到行左/行右。
• 移动本质上是稳定压缩：保留相对顺序，不跨越其他非空格。

2. 操作序列优化（消冗）：

• 先 unique 去连续重复（如 $UUU \to U$）。
• 再把自定义字符映射到方向：$G \to U$，$P \to R$。
• 使用相反方向抵消（如已有 $U$，遇到 $D$ 则删去 $U$），减少无效往返。
• 避免周期重复（如 $ABA\dots$ 的重复结构），确保 $opt$ 尽量短。

3. 直接执行与周期优化：

• 若 $|opt| \leq 6$：直接逐步调用 move，输出即可。
• 若 $|opt| > 6$：
  • 先执行 $opt$ 的前 $2$ 步，对当前网格非空元素分配唯一 ID，并记录其初始坐标 $pos$。
  • 再执行接下来的 $4$ 步操作对 ID 矩阵进行同样的移动，得到映射 $to$：一个周期（$4$ 步）后的 ID 置换关系。
  • 每个 ID 所在的置换环可一次性按 $r = \dfrac{|opt|-2}{4}$ 周期移动（环位移），把环内元素类型（B/C）旋转到最终位置。
  • 最后执行剩余不足一个周期的操作步（尾巴），得到最终网格。

实现亮点：

• 移动用稳定压缩实现，复杂度 $O(nm)$ 每步。
• 抵消与去重减少冗余操作，防止 TLE。
• 周期优化将大量重复 $4$ 步周期折算为置换环旋转，避免逐步仿真，显著加速长序列。
• ID 映射过程基于“把值替换成 ID，再移动 ID”，从而不依赖具体字符，先求置换，再回填字符。

复杂度分析：

• 直接执行部分：每步 $O(nm)$。
• 周期部分：构造置换 $O(nm)$，环分解与旋转总 $O($非空元素数$)$。
• 总体复杂度接近 $O(nm + |opt|)$ 的常数倍，在大网格和长操作序列下仍可接受。

边界与注意：

• 输入用 fast IO，避免大数据堵塞。
• 映射时确保 '.' $\to 0$，'B' $\to 1$，'C' $\to 2$；输出时反向映射。
• 周期优化需先执行 $2$ 步，使 ID 静态化，随后 $4$ 步为一个稳定周期。
• 尾部剩余操作按次序执行，避免越界与逻辑遗漏。

总结：
本解法将“全局紧缩移动”的网格仿真与“操作序列周期性”的组合优化起来：先规整指令，再把大段重复周期折算为置换环旋转，最后处理尾部步。兼顾正确性与效率，适合大规模输入与长序列。

#include <bits/stdc++.h>

signed main() {
    // 关闭cin与stdio的同步，取消cin的默认缓冲区，加速输入速度
    std::ios::sync_with_stdio(false);
    // 解除cin与cout的绑定，避免cout自动刷新缓冲区，进一步提升输入效率
    std::cin.tie(nullptr);

    // 定义输入流引用fin（默认关联标准输入cin）、输出流引用fout（默认关联标准输出cout）
    std::istream &fin = std::cin;
    std::ostream &fout = std::cout;
    // 以下两行是文件输入输出的备选方案（当前注释未启用）：
    //   std::ifstream fin("puzzle.in");  // 从puzzle.in文件读取输入
    //   std::ofstream fout("puzzle.out");  // 输出结果到puzzle.out文件

    // 定义变量n（网格行数）、m（网格列数），并从输入流读取n和m
    int n, m;
    fin >> n >> m;

    // 创建二维向量a作为网格容器，维度为(n+1)×(m+1)（采用1-based索引，方便后续循环）
    // 其中0表示空位置（对应原字符'.'），1表示'B'，2表示'C'
    std::vector<std::vector<int>> a(n + 1, std::vector<int>(m + 1));

    // 双重循环读取网格的每一个字符，并转换为数字存入a中
    for (int i = 1; i <= n; ++i) {  // 遍历每一行（1~n行）
        for (int j = 1; j <= m; ++j) {  // 遍历每一列（1~m列）
            char ch;  // 临时存储当前读取的字符
            fin >> ch;
            // 字符转数字：'B'→1，'C'→2，其他（'.'）→0
            a[i][j] = ch == 'B' ? 1 : ch == 'C' ? 2 : 0;
        }
    }

    // 定义变量k（操作序列的原始长度），并读取k和操作字符串st
    int k;
    fin >> k;
    std::string st;
    fin >> st;

    // 定义lambda表达式move：实现网格按指定方向（ch）移动的逻辑
    // 参数a为当前网格，ch为移动方向（U上、D下、L左、R右），返回移动后的新网格
    auto move = [&](auto a, char ch) {
        // 创建新二维向量b，初始化与原网格同维度，用于存储移动后的结果
        std::vector<std::vector<int>> b(n + 1, std::vector<int>(m + 1));

        // 处理上下方向的移动（U：上移，D：下移）
        if (ch == 'U' || ch == 'D') {
            // 上下移动按“列”处理：每一列的元素独立移动
            for (int j = 1; j <= m; ++j) {
                // 初始化计数器cnt：U方向从顶部（0）开始，D方向从底部（n）开始
                int cnt = ch == 'U' ? 0 : n;

                if (ch == 'U') {  // 处理上移逻辑
                    // 从第1行到第n行遍历当前列，将非空元素（a[i][j]≠0）依次放到顶部
                    for (int i = 1; i <= n; ++i) {
                        if (a[i][j] != 0) {
                            b[++cnt][j] = a[i][j];  // cnt自增后，将元素存入b的对应位置
                        }
                    }
                } else {  // 处理下移逻辑（ch == 'D'）
                    // 从第n行到第1行反向遍历当前列，将非空元素依次放到底部
                    for (int i = n; i >= 1; --i) {
                        if (a[i][j] != 0) {
                            b[cnt--][j] = a[i][j];  // cnt自减后，将元素存入b的对应位置
                        }
                    }
                }
            }
        } else {  // 处理左右方向的移动（L：左移，R：右移）
            // 左右移动按“行”处理：每一行的元素独立移动
            for (int i = 1; i <= n; ++i) {
                // 初始化计数器cnt：L方向从左侧（0）开始，R方向从右侧（m）开始
                int cnt = ch == 'L' ? 0 : m;

                if (ch == 'L') {  // 处理左移逻辑
                    // 从第1列到第m列遍历当前行，将非空元素依次放到左侧
                    for (int j = 1; j <= m; ++j) {
                        if (a[i][j] != 0) {
                            b[i][++cnt] = a[i][j];  // cnt自增后，将元素存入b的对应位置
                        }
                    }
                } else {  // 处理右移逻辑（ch == 'R'）
                    // 从第m列到第1列反向遍历当前行，将非空元素依次放到右侧
                    for (int j = m; j >= 1; --j) {
                        if (a[i][j] != 0) {
                            b[i][cnt--] = a[i][j];  // cnt自减后，将元素存入b的对应位置
                        }
                    }
                }
            }
        }

        // 返回移动后的新网格b
        return b;
    };

    // 定义lambda表达式print：将网格（数字形式）转换为原字符形式并输出
    // 参数a为待输出的网格
    auto print = [&](auto a) {
        // 双重循环遍历网格的每一个元素
        for (int i = 1; i <= n; ++i) {  // 遍历每一行
            for (int j = 1; j <= m; ++j) {  // 遍历每一列
                // 数字转字符：0→'.'，1→'B'，2→'C'，输出到fout
                fout << (a[i][j] == 0 ? '.' : a[i][j] == 1 ? 'B' : 'C');
            }
            // 每一行输出结束后，换行
            fout << '\n';
        }
    };

    // 优化操作序列st：去除连续重复的操作（例如"UUU"→"U"，"LRR"→"LR"）
    // unique函数将连续重复元素移到末尾，erase删除末尾的重复部分
    st.erase(std::unique(st.begin(), st.end()), st.end());

    // 替换操作字符：将"G"映射为"U"（上移），"P"映射为"R"（右移），其他字符保持不变
    for (auto &ch : st) {
        ch = ch == 'G' ? 'U' : ch == 'P' ? 'R' : ch;
    }

    // 定义map容器oppo：存储“相反方向”的映射关系，用于后续优化无效操作
    std::map<char, char> oppo;
    oppo['U'] = 'D';  // 上的相反方向是下
    oppo['D'] = 'U';  // 下的相反方向是上
    oppo['L'] = 'R';  // 左的相反方向是右
    oppo['R'] = 'L';  // 右的相反方向是左

    // 定义字符串opt：存储进一步优化后的操作序列
    std::string opt = "";

    // 遍历处理优化后的st，生成最终的有效操作序列opt
    for (int i = 0; i < st.size(); ++i) {
        // 若opt非空，且当前操作是opt最后一个操作的相反方向（例如opt最后是U，当前是D）
        // 则这两个操作相互抵消，删除opt的最后一个操作
        if (!opt.empty() && oppo[opt.back()] == st[i]) {
            opt.pop_back();
        }

        // 若opt为空，或当前操作满足“非连续重复、非周期重复”条件，则将当前操作加入opt
        if (opt.empty() || ((opt.size() == 1 || opt[opt.size() - 2] != st[i])) && opt.back() != st[i]) {
            opt += st[i];
        }
    }

    // 若优化后的操作序列opt长度≤6，直接依次执行所有操作（无需周期优化）
    if (opt.size() <= 6) {
        for (auto ch : opt) {  // 遍历opt的每个操作
            a = move(a, ch);   // 执行移动，更新网格a
        }
        print(a);  // 输出最终网格
        return 0;  // 程序结束
    }

    // 以下为操作序列opt长度>6的情况：使用周期优化（避免重复执行大量相同周期操作）
    // 先执行opt的前2个操作，更新网格a
    a = move(move(a, opt[0]), opt[1]);

    // 定义二维向量id：存储网格中每个非空元素的“唯一标识ID”
    std::vector<std::vector<int>> id(n + 1, std::vector<int>(m + 1));
    // 定义向量pos：存储每个ID对应的“初始位置”（i行j列），pos[0]占位，从pos[1]开始使用
    std::vector<std::tuple<int, int, int>> pos(1);
    // 定义变量tot：统计网格中非空元素的总数（即ID的最大值）
    int tot = 0;

    // 遍历当前网格a，为每个非空元素分配唯一ID，并记录其位置
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (a[i][j]) {  // 仅处理非空元素（a[i][j]≠0）
                // 为当前位置分配ID（tot自增后赋值），并将位置(i,j,ID)存入pos
                pos.emplace_back(i, j, id[i][j] = ++tot);
            }
        }
    }

    // 执行opt的第3~6个操作（共4个操作），更新id矩阵：模拟ID随网格移动的变化
    for (int i = 2; i <= 5; ++i) {
        id = move(id, opt[i]);
    }

    // 定义向量to：存储“ID映射关系”，to[x]表示ID=x的元素经过4个操作后，新的ID
    std::vector<int> to(tot + 1);
    // 定义变量ind：辅助记录新ID的序号（从1开始）
    int ind = 0;

    // 遍历网格a，建立ID的映射关系to
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (a[i][j]) {  // 仅处理非空元素
                assert(id[i][j]);  // 断言：确保当前位置的id不为0（避免逻辑错误）
                to[id[i][j]] = ++ind;  // 记录映射关系：原ID→新ID（ind自增）
            }
        }
    }

    // 定义向量vis：标记ID是否已处理（用于检测周期链），初始为0（未处理）
    std::vector<int> vis(tot + 1);
    // 计算周期重复次数r：(总操作数-前2个操作) / 4（因为每4个操作构成一个周期）
    int r = (opt.size() - 2) / 4;

    // 遍历所有非空元素的ID，处理每个周期链的移动
    for (int i = 1; i <= tot; ++i) {
        if (!vis[i]) {  // 若当前ID未处理
            // 定义向量p：存储当前周期链中的所有ID
            // 定义向量num：存储周期链中每个ID对应的元素类型（1=B，2=C）
            std::vector<int> p, num;

            // 遍历周期链：从ID=i开始，沿to映射关系移动，直到回到已处理的ID
            for (int j = i; !vis[j]; j = to[j]) {
                vis[j] = 1;          // 标记当前ID为已处理
                p.emplace_back(j);   // 将当前ID加入周期链p
                // 获取当前ID对应的元素类型（从pos中取初始位置，再从a中取类型）
                num.emplace_back(a[std::get<0>(pos[j])][std::get<1>(pos[j])]);
            }

            // 根据周期次数r，更新周期链中每个元素的最终位置和类型
            for (int j = 0; j < p.size(); ++j) {
                // 计算经过r次周期后，当前元素（原序号j）的新ID：(j + r) % 周期长度
                int now = p[(j + r) % p.size()];
                // 将原元素类型num[j]，赋值到新ID对应的初始位置
                a[std::get<0>(pos[now])][std::get<1>(pos[now])] = num[j];
            }
        }
    }

    // 执行opt中剩余的操作（总操作数 - 前2个操作 - r个周期（每个周期4个操作））
    for (int i = r * 4 + 2; i < opt.size(); ++i) {
        a = move(a, opt[i]);  // 执行移动，更新网格a
    }

    // 输出最终的网格状态
    print(a);
}