Chess Rush

1000ms

262144K

Description:

The mythic world of Chess Land is a rectangular grid of squares with $$$R$$$ rows and $$$C$$$ columns, $$$R$$$ being greater than or equal to $$$C$$$. Its rows and columns are numbered from $$$1$$$ to $$$R$$$ and $$$1$$$ to $$$C$$$, respectively.

The inhabitants of Chess Land are usually mentioned as pieces in everyday language, and there are $$$5$$$ specific types of them roaming the land: pawns, rooks, bishops, queens and kings. Contrary to popular belief, chivalry is long dead in Chess Land, so there are no knights to be found.

Each piece is unique in the way it moves around from square to square: in one step,

a pawn can move one row forward (i.e. from row $$$r$$$ to $$$r+1$$$), without changing columns;
a rook can move any number of columns left/right without changing rows OR move any number of rows forward/backward without changing columns;
a bishop can move to any square of the two diagonals intersecting at its currently occupied square;
a queen can move to any square where a rook or a bishop could move to from her position;
and a king can move to any of the $$$8$$$ adjacent squares.

In the following figure, we marked by X the squares each piece can move to in a single step (here, the rows are numbered from bottom to top, and the columns from left to right). $\text{[math]}$

Recently, Chess Land has become a dangerous place: pieces that are passing through the land can get captured unexpectedly by unknown forces and simply disappear. As a consequence, they would like to reach their destinations as fast (i.e. in as few moves) as possible, and they are also interested in the number of different ways it is possible for them to reach it, using the minimal number of steps – because more paths being available could mean lower chances of getting captured. Two paths are considered different if they differ in at least one visited square.

For this problem, let us assume that pieces are entering Chess Land in a given column of row $$$1$$$, and exit the land in a given column of row $$$R$$$. Your task is to answer $$$Q$$$ questions: given the type of a piece, the column it enters row $$$1$$$ and the column it must reach in row $$$R$$$ in order to exit, compute the minimal number of moves it has to make in Chess Land, and the number of different ways it is able to do so.

Scoring

$$$ \begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & 0 & \text{samples}\\ \hline 2 & 8 & T\in\{\text{'P','R','Q'}\}\text{, i.e. all pieces are pawns, rooks or queens} \\ \hline 3 & 15 & T=\text{'B' and } \: C,R\leq 100 \\ \hline 4 & 22 & T=\text{'B'} \\ \hline 5 & 5 & T=\text{'K' and }\:C,R\leq 100\:\text{and}\:Q\leq 50 \\ \hline 6 & 8 & T=\text{'K' and }\:C,R\leq 100\\ \hline 7 & 15 & T=\text{'K' and }\:C\leq 100\\ \hline 8 & 20 & T=\text{'K'}\\ \hline 9 & 7 & \text{no additional constraints}\\ \hline \end{array} $$$

Input:

The first line contains three space-separated integers $$$R$$$, $$$C$$$, and $$$Q$$$ $$$(1 \leq Q \leq 1000$$$, $$$2 \leq C \leq 1000$$$ and $$$C \leq R \leq 10^9)$$$ – the number of rows and columns of Chess Land, and the number of questions, respectively. Then $$$Q$$$ lines follow.

Each line consists of

a character $$$T$$$, corresponding to the type of the piece in question ('P' for pawn, 'R' for rook, 'B' for bishop, 'Q' for queen and 'K' for king);
two integers $$$c_1$$$ and $$$c_R$$$, $$$1\leq c_1,c_R\leq C$$$, denoting that the piece starts from the $$$c_1$$$-th column of row $$$1$$$, and has to reach the $$$c_R$$$-th column of row $$$R$$$.

Output:

You have to print $$$Q$$$ lines, the $$$i$$$-th one containing two space separated integers, the answer to the $$$i$$$-th question: the first one is the minimal number of steps needed, the second is the number of different paths available using this number of steps. Since the answer can be quite large, you have to compute it modulo $$$10^9+7$$$.

If it is impossible to reach the target square, output the line "0 0".

Sample Input:

Sample Output:

Note:

You can download the above example and an additional (bigger) sample input here: https://gofile.io/d/GDzwfC

Informação

Provedor Codeforces

Código CF1403C