题目描述

翁老师和聪聪老师在玩一款“石头剪刀布（升级版）”游戏。游戏中一共有 $n$ 种不同的手势，编号为 $1 \dots n$，每种手势对应一种不同的“材料/招式”。不同材料之间的胜负关系由一张复杂的对照表给出，对于任意两种手势，可能出现：

• 一方获胜，另一方失败；
• 双方平局。

在“石头剪刀布-1.0”的规则中，翁老师和聪聪老师每局各出两个手势（左手一个、右手一个）。当四个手势都出完后，两人各自从自己出的两个手势中选择一个用于对战，最终胜负按普通石头剪刀布的胜负表判定。

现在给定聪聪老师在接下来 $m$ 局中计划出的手势组合，翁老师想知道：在每一局中，有多少种不同的手势组合能保证无论聪聪老师怎么选，翁老师都能获胜。

一个手势组合定义为一个有序对 $(l, r)$，其中 $l$ 是左手出的手势编号，$r$ 是右手出的手势编号。注意：$(1,2)$ 和 $(2,1)$ 算不同的手势组合。

请你对每一局分别计算答案。

输入格式

输入第一行包含两个用空格分隔的整数 $n$ 和 $m$，分别表示手势种类数与对局数。

接下来有 $n$ 行描述胜负关系表：第 $i$ 行由 $i$ 个字符 $a_{i,1}a_{i,2}\dots 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 \le s_1,s_2 \le n$），表示聪聪老师在该局中出的手势组合（左手为 $s_1$，右手为 $s_2$）。

输出格式

输出 $m$ 行，其中第 $i$ 行输出一个整数，表示在第 $i$ 局中，翁老师可以确保获胜的手势组合 $(l,r)$ 的数量。

3 3
D
WD
LWD
1 2
2 3
1 1

0
0
5

附加样例

提示

样例 1 解释

• $1$ 表示石头。
• $2$ 表示布。
• $3$ 表示剪刀。

并满足：布胜石头，石头胜剪刀，剪刀胜布。

• 当聪聪老师出 $(1,2)$（石头+布）或 $(2,3)$（布+剪刀）时，翁老师无法保证必胜；

• 当聪聪老师出 $(1,1)$（石头+石头）时，翁老师可以选择以下任一组合应对并保证胜利（只要最后选择“布”即可）：

  • $(2,2)$
  • $(2,3)$
  • $(2,1)$
  • $(1,2)$
  • $(3,2)$

因此第三局答案为 $5$。

数据范围

• 对于 $40\%$ 的数据满足：$n, m \le 100$。
• 对于 $100\%$ 的数据满足：$n, m \le 3000$。