染色

题目描述

现有一个 $n \times m$ 的原本为白色网格，你需要从点 $(1, 1)$ 走到 $(n, m)$。每走到一个格子，你都会将这个格子从任意颜色染成黑色。

现在给你一串长度为 $n+m-2$、由 R 、D 和 ? 组成的字符串 $s$，你在这个白色格子上的每一步移动都要按照这个字符串 $s$ 来进行。移动方式如下：

• 你需要走一条从 $(1, 1)$ 到 $(n, m)$ 的路径，且每一步只能右走或者向下走。若 $s_i$ 为 D，则第 $i$ 步只能向下走，若 $s_i$ 为 R，则第 $i$ 步只能向右走。否则，这一步可以朝右或者下中的一个方向走。

现在你需要求所有能被你染色的点格子的个数。

输入格式

本题包含多组数据。

第一行一个整数 $T$ 表示测试数据的组数。对于每一组测试数据：

第一行两个整数 $n, m$，分别表示网格的行数和列数。
第二行一个长度为 $n+m-2$ 的字符串 $s$，表示移动的方式。

输出格式

对于每一组测试数据，共一行，表示答案。

样例 #1

样例输入 #1

4
2 2
RD
4 5
DDRRRDR
3 4
?????
4 5
D?RRD?R

样例输出 #1

3
8
12
12

数据范围

对于所有数据，保证：
$1 \le T \le 5$，$1 \le n + m \le 4 \times 10^4$。

提示

本题输入可参考下列方式实现：

n, k, x = map(int, input().split())
a = list(map(int,input().split()))