Chess Rush

The mythic world of Chess Land is a rectangular grid of squares with $R$ rows and $C$ columns, where $R \ge C$. Rows are numbered 1 to $R$, and columns are numbered 1 to $C$.

The inhabitants of Chess Land are called pieces. Five types roam the land: pawns, rooks, bishops, queens and kings. Chivalry has been dead in Chess Land for a long time, so there are no knights.

Each piece moves in its own way. In one step:

• a pawn can move one row forward (from row $r$ to row $r + 1$) without changing columns;
• a rook can move any number of columns left or right without changing rows, or any number of rows forward or backward without changing columns;
• a bishop can move to any square on the two diagonals that cross its current square;
• a queen can move to any square that a rook or a bishop could reach from her position;
• a king can move to any of the 8 adjacent squares.

The figure marks with X the squares each piece can reach in one step. Rows are numbered bottom to top, and columns are numbered left to right.

Recently, pieces passing through Chess Land have been captured by unknown forces without warning and disappeared. Pieces want to reach their destinations in as few moves as possible. They also care how many different paths use that minimal number of steps, since more paths mean a lower chance of being captured. Two paths are different if they differ in at least one visited square.

A piece enters Chess Land at a given column of row 1 and exits at a given column of row $R$. Answer $Q$ questions. Each question gives the piece type, the column $c_1$ where it enters row 1, and the column $c_R$ it must reach in row $R$. For each question, find the minimal number of moves and the number of different paths that use that many moves.

The first line contains three integers $R$, $C$, and $Q$, separated by spaces. Then $Q$ lines follow. Each line contains a character $T$ for the piece type (P for pawn, R for rook, B for bishop, Q for queen, K for king), followed by two integers $c_1$ and $c_R$, separated by spaces.

Print $Q$ lines. The $i$-th line contains two integers separated by a space: the minimal number of moves for the $i$-th question, and the number of different paths that reach the target in that many moves, taken modulo $10^9 + 7$. If the target cannot be reached, print 0 0.

• $1 \le Q \le 1000$
• $2 \le C \le 1000$
• $C \le R \le 10^9$
• $1 \le c_1, c_R \le C$