---

题目描述

题目译自 CEOI 2020 Day2 T3「Chess Rush」

象棋世界是一个 $R$ 行 $C$ 列的棋盘，其中 $R \geq C$。所有的行依此编号为 $1$ 到 $R$，所有的列依此编号为 $1$ 到 $C$。

在象棋世界里，共有五种棋子：兵，车，象，后，王。与现实世界不同的是，骑士精神在象棋世界中已经死亡，因此象棋世界里找不到马。

象棋世界里，每种棋子可以按如下规则进行一步移动：

• 兵 只能向行号增大的方向走一步（从第 $r$ 行到第 $r+1$ 行），且其所处的列不变。
• 车 只能沿水平方向或竖直方向移动。
• 象 只能沿对角线方向移动。
• 后 可以沿水平方向，竖直方向，或对角线方向移动。
• 王 可以向与之相邻的八个格子移动。

为了方便你理解，我们在下图给出了每种棋子的合法移动范围。其中 X 代表该棋子能移动到的位置。

最近一段时间，象棋世界发生了不少诡异的事情：某些棋子可能会被不明来源的力量所劫持，随后从象棋世界中消失。在这种情况下，所有棋子都希望能尽快前往他们想要到达的目的地，他们还想知道，在走的步数最少的前提下，到达目的地的方案数有多少。两种方案是不同的，当且仅当这两种方案中有一步经过的格子不同。

在本题中，你需要解决下面这个问题：某个棋子将从第 $1$ 行的第 $c_1$ 列出发，到达第 $R$ 行的第 $c_R$ 列。现在给出这个棋子的类型，以及 $c_1, c_R$ 的值，你需要求出，这个棋子最少需要走多少步，以及在步数最少的前提下，行走方案有多少种。

---

输入格式

第一行包含三个整数 $R, C, Q$，表示象棋世界中棋盘的行数，列数，以及需要回答的询问数。

接下来 $Q$ 行，每行包含一个字母 $T$，代表棋子种类，以及两个整数 $c_1, c_R$，代表起点为第 $1$ 行的第 $c_1$ 列，终点为第 $R$ 行的第 $c_R$ 列。

各字母与棋子种类对应关系如下所示：

字母	棋子种类
$\texttt{P}$	兵
$\texttt{R}$	车
$\texttt{B}$	象
$\texttt{Q}$	后
$\texttt{K}$	王

---

输出格式

对于每个询问，输出两个整数，第一个整数代表从起点到终点需要走的最少步数，第二个整数代表在步数最少的前提下，从起点到终点的方案数。

因为方案数可能很大，请输出其对 $10^9+7$ 取模后的结果。

特别地，若无法从起点到达终点，请输出一行 0 0。

---

样例

输入

8 8 5
P 1 2
R 4 8
Q 2 3
B 3 6
K 5 5

输出

0 0
2 2
2 5
2 2
7 393

---

数据范围与提示

所有测试点均满足：
$1 \leq Q \leq 1000$，
$2 \leq C \leq 1000$，
$C \leq R \leq 10^9$，
$T \in \{\texttt{P},\texttt{R},\texttt{Q},\texttt{B},\texttt{K}\}$，
$1 \leq c_1, c_R \leq C$。

各子任务的约束条件如下：

子任务编号	分值	约束
1	0	样例
2	8	$T \in \{\texttt{P},\texttt{R},\texttt{Q}\}$
3	15	$T=\texttt{B}$，$C,R \leq 100$
4	22	$T=\texttt{B}$
5		$T=\texttt{K}$，$C,R \leq 100$，$Q \leq 50$
6	8	$T=\texttt{K}$，$C,R \leq 100$
7	15	$T=\texttt{K}$，$C \leq 100$
8	20	$T=\texttt{K}$
9	7	无特殊约束

---