1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
// clang-format off
#include<bits/stdc++.h>
using namespace std;
using LL=long long;
#define FOR(i,l,r) for(auto i=(l);i<=(r);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) int(x.size())
template<class A,class B>auto&operator<<(ostream&o,pair<A,B>p){return o<<"("<<p.first<<", "<<p.second<<")";}
template<class T>auto operator<<(ostream&o,T x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<(", ")+2*!i++<<e;return o<<"}";}
#ifdef DEBUG
#define debug(x...) cerr<<"["#x"]: ",[](auto...$){((cerr<<$<<"; "),...);}(x),cerr<<'\n'
#else
#define debug(...) {}
#endif
// clang-format on

#define BOARD(r, c) board[(r)*dim[1] + (c)]

// Global variables
const int nchars = 'Z' - 'A' + 1;
int dim[2], nrc;  // [0] nrows, [1] ncols
vector<char> board;
vector<int> diff_chars;  // number of different chars in given row/column
vector<array<int, nchars>> char_cnt;  // count of each chars in row/column
vector<int> to_process;
vector<pair<int, char>> ans;  // (row/col, char) in reverse order


int
main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin >> dim[0] >> dim[1];
    board.resize(dim[0] * dim[1]);
    for (auto& ch : board) cin >> ch;

    // Preprocess the data
    diff_chars.resize(nrc = dim[0] + dim[1]);
    char_cnt.resize(nrc);
    REP (r, dim[0]) {
        REP (c, dim[1]) {
            int ch = BOARD(r, c) - 'A';
            if (char_cnt[r][ch]++ == 0) ++diff_chars[r];
            if (char_cnt[dim[0] + c][ch]++ == 0) ++diff_chars[dim[0] + c];
        }
    }
    debug(diff_chars);

    // Find rows/cols to be processed first
    REP (i, nrc)
        if (diff_chars[i] == 1) to_process.emplace_back(i);
    debug(to_process);

    // Compute the answer in a DFS manor
    ans.reserve(nrc);
    while (!to_process.empty()) {
        int id = to_process.back();
        to_process.pop_back();
        bool ifrow = id < dim[0];
        char ans_ch;
        REP (i, dim[ifrow]) {
            auto& ch = ifrow ? BOARD(id, i) : BOARD(i, id - dim[0]);
            if (ch == 0) continue;
            ans_ch     = ch;
            int oth_id = (ifrow ? dim[0] + i : i);
            if (--char_cnt[id][ch - 'A'] == 0)
                if (--diff_chars[id] == 1) to_process.emplace_back(id);
            if (--char_cnt[oth_id][ch - 'A'] == 0)
                if (--diff_chars[oth_id] == 1) to_process.emplace_back(oth_id);
            ch = 0;
        }
        ans.emplace_back(id, ans_ch);
    }

    // Output
    cout << ssize(ans) << "\n";
    for (auto it = ans.rbegin(); it != ans.rend(); ++it)
        cout << (it->first < dim[0] ? "R " : "K ")
             << (it->first < dim[0] ? it->first : it->first - dim[0]) + 1 << " "
             << it->second << "\n";
#ifdef LOCAL
    system("grep VmPeak /proc/$PPID/status >&2");
#endif
    return 0;
}