题目描述

小Z和小K准备玩升级版的“左一拳右一拳”。

现在两人的出拳花样不止三种，而是拓展到了 $n$ 种，分别编号为 $1\sim n$，其中两两花样的胜负关系会给出。

因为上次比赛中小Z输的太惨，小K打算让他，由小K先出两拳，小Z需要快速计算出有多少种必胜的出拳方式。

输入格式

输入的第一行包含两个空格分隔的整数 $n$ 和 $m$，表示出拳手势花样的数量，以及 小Z 与 小K 进行的游戏局数。

接下来 $n$ 行，第 $i$ 行由 $i$ 个字符 $a_{i,1}a_{i,2}\ldots a_{i,i}$ 组成，其中 $a_{i,j} \in \{\texttt P,\texttt S,\texttt F\}$。如果 $a_{i,j} = \texttt P$，则手势 $i$ 平于手势 $j$。如果 $a_{i,j} = \texttt S$，则手势 $i$ 胜于手势 $j$。如果 $a_{i,j} = \texttt F$，则手势 $i$ 负于手势 $j$。输入保证 $a_{i,i} = \texttt P$。

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

输出格式

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

输入输出样例

3 3
P
SP
FSP
1 2
2 3
1 1

0
0
5

样例 $\tt \#1$说明

这对应于原始的剪刀石头布，我们可以设石头为 $1$，布为 $2$，剪刀为 $3$。布战胜石头，石头战胜剪刀，剪刀战胜布。小Z 无法确保战胜石头 + 布或布 + 剪刀的组合。

然而，如果 小K 出石头 + 石头，小Z 可以采用以下任一组合进行反击。

• 布 + 布
• 布 + 剪刀
• 布 + 石头
• 石头 + 布
• 剪刀 + 布

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

数据范围

$2\le n, m\le 1000$