You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

在一局蹄子剪刀布游戏中，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 的手势组合数量。

输入输出样例 #1

输入 #1

3 3
D
WD
LWD
1 2
2 3
1 1

输出 #1

0
0
5

说明/提示

在样例 1 解释：这对应于原始的蹄子剪刀布，我们可以设蹄子为 $1$，布为 $2$，剪刀为 $3$。布战胜蹄子，蹄子战胜剪刀，剪刀战胜布。Bessie 无法确保战胜蹄子 + 布或布 + 剪刀的组合。然而，如果 Elsie 出蹄子 + 蹄子，Bessie 可以采用以下任一组合进行反击。

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

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

• 测试点 $2\sim 6$：$N,M\le 100$。

• 测试点 $7\sim 12$：没有额外限制。