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
86
87
88
89
90
91
92
93
94
#include <bits/stdc++.h>

const int MAX_N = 2000;

char T[MAX_N + 3][MAX_N + 3];
int cnt[2][MAX_N + 3][30];
bool pushed[2][MAX_N + 3];

int n, m;

int main() {
  std::ios_base::sync_with_stdio(0);
  std::cin.tie(NULL);

  std::cin >> n >> m;

  for (int i = 1; i <= n; i++) {
    std::string s;
    std::cin >> s;
    for (int j = 0; j < m; j++) {
      T[i][j + 1] = s[j];
      cnt[0][i][s[j] - 'A']++;
      cnt[1][j + 1][s[j] - 'A']++;
    }
  }

  std::queue<std::pair<int, int>> q;

  auto get_col = [&](int i, int j) {
    for (char c = 'A'; c <= 'Z'; c++)
      if (cnt[i][j][c - 'A'] > 0)
        return c;
    return 'A';
  };

  auto is_good = [&](int i, int j) {
    int found = 0;
    for (char c = 'A'; c <= 'Z'; c++)
      if (cnt[i][j][c - 'A'] > 0)
        found++;
    return found <= 1;
  };

  for (int i = 1; i <= n; i++)
    if (is_good(0, i)) {
      q.push({0, i});
      pushed[0][i] = true;
    }
  for (int i = 1; i <= m; i++)
    if (is_good(1, i)) {
      q.push({1, i});
      pushed[1][i] = true;
    }

  std::vector<std::pair<char, std::pair<int, char>>> R;

  while (!q.empty()) {
    auto [i, j] = q.front();

    q.pop();

    R.push_back({(i == 0) ? 'R' : 'K', {j, get_col(i, j)}});

    if (i == 0) {
      for (int k = 1; k <= m; k++) {
        if (T[j][k] != '?') {
          cnt[1][k][T[j][k] - 'A']--;
          if (!pushed[1][k] && is_good(1, k)) {
            q.push({1, k});
            pushed[1][k] = true;
          }
          T[j][k] = '?';
        }
      }
    } else {
      for (int k = 1; k <= n; k++) {
        if (T[k][j] != '?') {
          cnt[0][k][T[k][j] - 'A']--;
          if (!pushed[0][k] && is_good(0, k)) {
            q.push({0, k});
            pushed[0][k] = true;
          }
          T[k][j] = '?';
        }
      }
    }
  }

  std::reverse(R.begin(), R.end());
  std::cout << R.size() << "\n";
  for (int i = 0; i < R.size(); i++)
    std::cout << R[i].first << " " << R[i].second.first << " "
              << R[i].second.second << "\n";
}