CEOI '20 - Chess Rush (51pts)

#include <bits/stdc++.h>
#define NDEBUG

using namespace std;

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

int R, C;
inline bool sameDiagonal(int x1, int y1, int x2, int y2) {
    return x1-y1 == x2-y2 || x1+y1 == x2+y2;
}
inline bool sameColor(int x1, int y1, int x2, int y2) {
    return ((x1+y1)-(x2+y2)) % 2 == 0;
}
inline bool inBoard(int r, int c) {
    return r >= 1 && c >= 1 && r <= R && c <= C;
}
inline 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};
}

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

inline 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
inline 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]});
}

inline int mult(int x, int y) {
    return (long long)x*y % BASE;
}
struct Matrix {
    int n, m;
    vector<vector<int>> v;
    Matrix() {}
    Matrix(int N, int M): n(N), m(M) {
        v.assign(n, vector<int>(m));
    }
    inline Matrix operator * (const Matrix &m2) const {
        assert(m == m2.n);
        int k = m2.m;
        Matrix m3(n, k);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < k; ++j) {
                for (int l = 0; l < m; ++l) {
                    m3.v[i][j] = add(m3.v[i][j], mult(v[i][l], m2.v[l][j]));
                }
            }
        }
        return m3;
    }
    inline Matrix bin_pow(int y) {
        assert(n == m);
        Matrix res(n, n);
        for (int i = 0; i < n; ++i) res.v[i][i] = 1;
        Matrix x = *this;
        while (y) {
            if (y & 1) res = res * x;
            y >>= 1;
            x = x * x;
        }
        return res;
    }
};

Matrix kingSquareMatrix;
bool calculatedKingSquareMatrix = false;
inline pair<int, int> solveKing(int c1, int cr) {
    if (!calculatedKingSquareMatrix) {
        Matrix multiplier(C, C);
        for (int i = 0; i < C; ++i) {
            for (int j = i-1; j <= i+1; ++j) {
                if (0 <= j && j < C) multiplier.v[j][i] = 1;
            }
        }
        kingSquareMatrix = multiplier.bin_pow(R-1);
        calculatedKingSquareMatrix = true;
    }
    return {R-1, kingSquareMatrix.v[cr-1][c1-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);
            cout << m << ' ' << w << '\n';
        }
    }
    return 0;
}