国际象棋之地的神话世界是一个拥有 $R$ 行 $C$ 列的矩形网格，其中 $R \ge C$。其行和列分别从 $1$ 到 $R$ 和 $1$ 到 $C$ 进行编号。

国际象棋之地的居民通常被称为“棋子”，这片土地上有 5 种特定的棋子：兵（pawn）、车（rook）、象（bishop）、后（queen）和王（king）。与大众的认知相反，国际象棋之地早已没有了骑士精神，因此这里没有马（knight）。

每种棋子在从一个方格移动到另一个方格的方式上都是独特的：在一步之内，

• 兵可以向前移动一行（即从第 $r$ 行移动到 $r+1$ 行），且不能改变列；
• 车可以在不改变行的情况下向左/向右移动任意数量的列，或者在不改变列的情况下向前/向后移动任意数量的行；
• 象可以移动到与其当前所在方格相交的两条对角线上的任意方格；
• 后可以移动到车或象在当前位置可以移动到的任意方格；
• 王可以移动到周围 8 个相邻方格中的任意一个。

在下图中，我们用 X 标记了每种棋子在一步之内可以移动到的方格（此处行从下到上编号，列从左到右编号）。

最近，国际象棋之地变得危险起来：穿过这片土地的棋子可能会意外地被未知力量捕获并直接消失。因此，它们希望以尽可能快的速度（即尽可能少的步数）到达目的地，并且它们也对以最少步数到达目的地的不同路径数量感兴趣。如果两条路径在至少一个经过的方格上不同，则认为它们是不同的。

对于本题，假设棋子从第 $1$ 行的某一列进入国际象棋之地，并从第 $R$ 行的某一列离开。你需要回答 $Q$ 个问题：给定棋子的类型、进入第 $1$ 行的列以及必须到达第 $R$ 行的列，计算该棋子在国际象棋之地所需的最少移动步数，以及以该步数到达目的地的不同路径数量。

输入格式

第一行包含三个空格分隔的整数 $R$、$C$ 和 $Q$，分别表示国际象棋之地的行数、列数以及询问次数。随后有 $Q$ 行。

每一行包含：

• 一个字符 $T$，对应所询问的棋子类型（'P' 代表兵，'R' 代表车，'B' 代表象，'Q' 代表后，'K' 代表王）；
• 两个整数 $c_1$ 和 $c_R$（$1 \le c_1, c_R \le C$），表示棋子从第 $1$ 行的第 $c_1$ 列出发，必须到达第 $R$ 行的第 $c_R$ 列。

输出格式

你需要打印 $Q$ 行，第 $i$ 行包含两个空格分隔的整数，即第 $i$ 个问题的答案：第一个整数是所需的最少步数，第二个整数是使用该步数可用的不同路径数量。由于答案可能非常大，你需要使用评分系统提供的库函数计算其对 $10^9 + 7$ 取模的结果。

如果无法到达目标方格，输出一行 "0 0"。

实现细节

评分系统提供了以下库函数，用于执行涉及模 $10^9 + 7$ 的基本算术运算。在所有情况下，输入可以是任何有效的 int 值，输出范围为 $0, 1, 2, \dots, 10^9 + 6$。

• int Add(int a, int b)：计算 $a$ 与 $b$ 的和，并返回模 $10^9 + 7$ 的结果。
• int Sub(int a, int b)：计算 $a$ 减去 $b$ 的差，并返回模 $10^9 + 7$ 的结果。
• int Mul(int a, int b)：计算 $a$ 与 $b$ 的积，并返回模 $10^9 + 7$ 的结果。
• int Div(int a, int b)：计算 $a$ 除以 $b$（$b \neq 0$）的商，并返回模 $10^9 + 7$ 的结果。即当且仅当 Mul(b, q) == a mod (10^9 + 7) 时，返回 $0 \le q < 10^9 + 7$ 的值。

你可以假设上述所有操作都在常数时间内完成。

要访问这些函数，你必须在你的解决方案的包含列表中添加 #include "arithmetics.h"。

注意：arithmetics.h 头文件不可用。

样例

输入 1

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

输出 1

0 0
2 2
2 5
2 2
7 393

数据范围

$1 \le Q \le 1000$ $2 \le C \le 1000$ $C \le R \le 10^9$

子任务