CEOI '20 - Chess Rush (36pts)

#include <bits/stdc++.h>

using namespace std;

const int INF = 1e8;
const int BASE = 1e9 + 7;
int add(int x, int y) {
    x += y;
    if (x >= BASE) return x-BASE;
    return x;
}

int R, C;
bool sameDiagonal(int x1, int y1, int x2, int y2) {
    return x1-y1 == x2-y2 || x1+y1 == x2+y2;
}
bool sameColor(int x1, int y1, int x2, int y2) {
    return ((x1+y1)-(x2+y2)) % 2 == 0;
}
bool inBoard(int r, int c) {
    return r >= 1 && c >= 1 && r <= R && c <= C;
}
pair<int, int> diagonalIntersect(int x1, int y1, int x2, int y2) {
    // x + y = x1 + y1
    // x - y = x2 - y2
    // x = (x1 + y1 + x2 - y2) / 2
    // y = (x1 + y1 - x2 + y2) / 2
    return {(x1+y1+x2-y2)/2, (x1+y1-x2+y2)/2};
}

pair<int, int> downRight(int r, int c) {
    return {r+C-c, C};
}
pair<int, int> downLeft(int r, int c) {
    return {r+c-1, 1};
}

pair<int, int> combine(pair<int, int> a, pair<int, int> b) { // (moves, ways)
    if (a.first == b.first) return {a.first, add(a.second, b.second)};
    else if (a.first < b.first) return a;
    else return b;
}

// going right
pair<int, int> solveBishop(int c1, int cr) {
    vector<int> ways(2*C), moves(2*C, INF);
    ways[c1-1] = 1, moves[c1-1] = 1;
    for (int r = 2; r <= R; ++r) {
        vector<int> ways2(2*C), moves2(2*C, INF);

        auto can = [&](int pos, int dir, int w, int m) {
            if (0 <= pos && pos < C) {
                if (m < moves2[dir*C+pos]) moves2[dir*C+pos] = m, ways2[dir*C+pos] = w;
                else if (m == moves2[dir*C+pos]) ways2[dir*C+pos] = add(ways2[dir*C+pos], w);
            }
        };
        for (int i = 0; i < 2*C; ++i) {
            int c = i%C, dir = i/C;
            if (dir == 0) { // going right
                can(c+1, 0, ways[i], moves[i]);
                can(c-1, 1, ways[i], moves[i]+1);
            } else { // going left
                can(c+1, 0, ways[i], moves[i]+1);
                can(c-1, 1, ways[i], moves[i]);
            }
        }
        ways = ways2, moves = moves2;
    }
    return combine({moves[cr-1], ways[cr-1]}, {moves[cr-1+C], ways[cr-1+C]});
}

pair<int, int> solveKing(int c1, int cr) {
    vector<int> ways(C), moves(C, INF);
    ways[c1-1] = 1, moves[c1-1] = 0;
    for (int r = 2; r <= R; ++r) {
        vector<int> ways2(C), moves2(C, INF);

        auto can = [&](int pos, int w, int m) {
            if (0 <= pos && pos < C) {
                if (m < moves2[pos]) moves2[pos] = m, ways2[pos] = w;
                else if (m == moves2[pos]) ways2[pos] = add(ways2[pos], w);
            }
        };
        for (int c = 0; c < C; ++c) {
            can(c+1, ways[c], moves[c]+1);
            can(c-1, ways[c], moves[c]+1);
            can(c  , ways[c], moves[c]+1);
        }
        ways = ways2, moves = moves2;
    }
    return {moves[cr-1], ways[cr-1]};
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int Q; cin >> R >> C >> Q;
    while (Q--) {
        char t; int c1, cr;
        cin >> t >> c1 >> cr;
        if (t == 'P') {
            if (c1 == cr) cout << R-1 << " 1\n";
            else cout << "0 0\n";
        } else if (t == 'R') {
            if (c1 == cr) cout << "1 1\n";
            else cout << "2 2\n";
        } else if (t == 'Q') {
            if (c1 == cr || sameDiagonal(1, c1, R, cr)) cout << "1 1\n";
            else { // 2 moves
                int ways = 2 + 2; // Rook Rook, vertical Rook and Bishop (or vice versa)
                if (R == C && (c1 == 1 || c1 == C)) ++ways; // bishop + horizontal rook move
                if (R == C && (cr == 1 || cr == C)) ++ways; // horizontal rook move + bishop
                // both bishop moves:
                if (sameColor(1, c1, R, cr)) {
                    auto [x1, y1] = diagonalIntersect(1, c1, R, cr);
                    if (inBoard(x1, y1)) ++ways;
                    auto [x2, y2] = diagonalIntersect(R, cr, 1, c1);
                    if (inBoard(x2, y2)) ++ways;
                }
                cout << "2 " << ways << '\n';
            }
        } else if (t == 'B') {
            pair<int, int> a = solveBishop(c1, cr), b = solveBishop(C+1-c1, C+1-cr);
            auto [m, w] = combine(a, b);
            if (m == INF) cout << "0 0\n";
            else cout << m << ' ' << w << '\n';
        } else { // t == 'K'
            auto [m, w] = solveKing(c1, cr);
            if (m == INF) cout << "0 0\n";
            else cout << m << ' ' << w << '\n';
        }
    }
    return 0;
}