CF1202C You Are Given a WASD-string...

你有一个字符串 $s$，表示你玩具机器人的一系列指令。机器人被放置在一个矩形网格的某个格子中。它可以执行四种指令： - 'W' —— 向上移动一格； - 'S' —— 向下移动一格； - 'A' —— 向左移动一格； - 'D' —— 向右移动一格。 设 $Grid(s)$ 为面积最小的网格，使得存在一个位置可以放置机器人，并且在执行指令序列 $s$ 时，机器人不会从网格上掉落。例如，如果 $s = \text{DSAWWAW}$，那么 $Grid(s)$ 是 $4 \times 3$ 的网格： 1. 你可以将机器人放在格子 $(3, 2)$； 2. 机器人执行指令 'D'，移动到 $(3, 3)$； 3. 机器人执行指令 'S'，移动到 $(4, 3)$； 4. 机器人执行指令 'A'，移动到 $(4, 2)$； 5. 机器人执行指令 'W'，移动到 $(3, 2)$； 6. 机器人执行指令 'W'，移动到 $(2, 2)$； 7. 机器人执行指令 'A'，移动到 $(2, 1)$； 8. 机器人执行指令 'W'，移动到 $(1, 1)$。  你有 4 个额外的字母：一个 'W'，一个 'A'，一个 'S'，一个 'D'。你可以在序列 $s$ 的任意位置插入至多一个这样的字母，以最小化 $Grid(s)$ 的面积。 你能得到的 $Grid(s)$ 的最小面积是多少？

第一行包含一个整数 $T$（$1 \le T \le 1000$），表示询问的数量。 接下来的 $T$ 行，每行一个字符串 $s$（$1 \le |s| \le 2 \cdot 10^5$，$s_i \in \{\text{W}, \text{A}, \text{S}, \text{D}\}$），表示指令序列。 保证所有询问中 $s$ 的总长度不超过 $2 \cdot 10^5$。

输出 $T$ 个整数，每个询问输出一行。对于每个询问，输出你能得到的 $Grid(s)$ 的最小面积。

对于第一个询问，你需要得到字符串 $\text{DSAWW}\underline{D}\text{AW}$。 对于第二个和第三个询问，你无法减小 $Grid(s)$ 的面积。 由 ChatGPT 4.1 翻译