Problem 1. Hoof Paper Scissors Minus One

USACO 2025 US Open Contest, Bronze

注意：本题的时间限制为 3 秒，通常限制的 1.5 倍。

在一局蹄子剪刀布游戏中，Bessie 和 Elsie 可以出 $N$ （$1 \leq N \leq 3000$）种不同的蹄子手势，编号为 $1\dots N$，每个手势对应一种不同的材料。不同材料之间的相互关系有一个复杂的表格，基于该表格，可能会：

• 一种手势获胜，另一种失败。
• 两种手势平局。

蹄子剪刀布-1.0 的规则类似，但 Bessie 和 Elsie 可以各自出两个手势，每只蹄子出一个。在观察到她们所出的四个手势后，她们各自选择其中一个手势进行游戏。结果根据正常的蹄子剪刀布的规则决定。

给定 Elsie 计划在每局游戏中出的 $M$（$1 \leq M \leq 3000$）个手势组合，Bessie 想知道有多少种不同的手势组合可以确保战胜 Elsie。一个手势组合定义为一个有序对 $(L,R)$，其中 $L$ 为奶牛用左蹄出的手势，$R$ 为奶牛用右蹄出的手势。你能为每局游戏进行计算吗？

输入格式（从终端 / 标准输入读入）：

输入的第一行包含两个空格分隔的整数 $N$ 和 $M$，表示蹄子手势的数量，以及 Bessie 与 Elsie 进行的游戏局数。

以下 $N$ 行，第 $i$ 行由 $i$ 个字符 $a_{i,1}a_{i,2}\ldots a_{i,i}$ 组成，其中 $a_{i,j} \in \{\texttt D,\texttt W,\texttt L\}$。如果 $a_{i,j} = \texttt D$，则手势 $i$ 平于手势 $j$。如果 $a_{i,j} = \texttt W$，则手势 $i$ 胜于手势 $j$。如果 $a_{i,j} = \texttt L$，则手势 $i$ 负于手势 $j$。输入保证 $a_{i,i} = \texttt D$。

以下 $M$ 行，每行包含两个空格分隔的整数 $s_1$ 和 $s_2$，其中 $1 \leq s_1,s_2 \leq N$，表示 Elsie 在该局游戏中的手势组合。

输出格式（输出至终端 / 标准输出）：

输出 $M$ 行，其中第 $i$ 行包含在第 $i$ 局游戏中 Bessie 可以确保战胜 Elsie 的手势组合数量。

输入样例：

3 3
D
WD
LWD
1 2
2 3
1 1

输出样例：

0
0
5

在这个例子中，这对应于

原始的蹄子剪刀布

，我们可以设蹄子为 1，布为 2，剪刀为 3。 布战胜蹄子，蹄子战胜剪刀，剪刀战胜布。Bessie 无法确保战胜蹄子+布或布+剪刀的组合。然而，如果 Elsie 出蹄子+蹄子，Bessie 可以采用以下任一组合进行反击。

• 布+布
• 布+剪刀
• 布+蹄子
• 蹄子+布
• 剪刀+布

如果 Bessie 出这些组合中的任意一个，她可以确保通过出布来获胜。

测试点性质： 测试点 2-6：$N,M\le 100$。测试点 7-12：没有额外限制。

供题：Suhas Nagar