Chess Land là một bàn cờ hình chữ nhật gồm \(R\) hàng và \(C\) cột, trong đó \(R\ge C\). Các hàng được đánh số từ \(1\) đến \(R\), các cột được đánh số từ \(1\) đến \(C\).

Ở đây có năm loại quân cờ: tốt, xe, tượng, hậu và vua; không có quân mã. Trong một nước đi:

• Tốt đi lên một hàng, từ hàng \(r\) sang hàng \(r+1\), không đổi cột.
• Xe đi tùy ý số ô theo hàng hoặc theo cột.
• Tượng đi đến một ô bất kỳ trên một trong hai đường chéo đi qua ô hiện tại.
• Hậu có thể đi như xe hoặc như tượng.
• Vua đi đến một trong tám ô kề cạnh hoặc kề góc.

Hình dưới đánh dấu bằng chữ X các ô mà mỗi quân có thể đi tới trong một nước. Trong hình, các hàng được đánh số từ dưới lên và các cột từ trái sang phải.

Quân cờ có thể bị bắt bất ngờ khi đang đi qua bàn cờ và biến mất. Vì vậy, mỗi quân muốn tới đích với số nước đi ít nhất có thể; trong số các cách dùng ít nước nhất, ta cũng cần đếm số đường đi khác nhau. Hai đường đi khác nhau nếu chúng có ít nhất một ô được ghé thăm khác nhau.

Mỗi câu hỏi cho biết loại quân, cột xuất phát ở hàng \(1\) và cột đích ở hàng \(R\). Hãy tìm số nước đi ít nhất và số đường đi đạt được số nước đi đó. Nếu không thể tới ô đích, in 0 0.

Số đường đi cần được tính modulo \(10^9+7\).

Dữ liệu vào

Dòng đầu gồm ba số nguyên \(R,C,Q\): số hàng, số cột và số câu hỏi.

Mỗi dòng trong \(Q\) dòng tiếp theo gồm một ký tự \(T\) và hai số nguyên \(c_1,c_R\). Ký tự \(T\) là loại quân (P là tốt, R là xe, B là tượng, Q là hậu, K là vua); \(c_1\) là cột xuất phát ở hàng \(1\), còn \(c_R\) là cột cần tới ở hàng \(R\).

Dữ liệu ra

In \(Q\) dòng. Dòng thứ \(i\) gồm hai số nguyên: số nước đi ít nhất và số đường đi dùng số nước ít nhất cho câu hỏi thứ \(i\). Số đường đi phải được lấy modulo \(10^9+7\).

Ví dụ

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

Ràng buộc

• \(1\le Q\le1000\).
• \(2\le C\le1000\).
• \(C\le R\le10^9\).

Phân nhóm

1. \(0\) điểm: Bộ dữ liệu mẫu.
2. \(8\) điểm: Mọi câu hỏi đều hỏi về tốt, xe hoặc hậu.
3. \(15\) điểm: Mọi câu hỏi đều hỏi về tượng; \(C,R\le100\).
4. \(22\) điểm: Mọi câu hỏi đều hỏi về tượng.
5. \(5\) điểm: Mọi câu hỏi đều hỏi về vua; \(C,R\le100\) và \(Q\le50\).
6. \(8\) điểm: Mọi câu hỏi đều hỏi về vua; \(C,R\le100\).
7. \(15\) điểm: Mọi câu hỏi đều hỏi về vua; \(C\le100\).
8. \(20\) điểm: Mọi câu hỏi đều hỏi về vua.
9. \(7\) điểm: Không có ràng buộc nào khác.