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
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, lower, upper) for(int (i) = (lower); i <= (int)(upper); (i)++)
#define FORD(i, upper, lower) for(int (i) = (upper); i >= (int)(lower); (i)--)

struct op {
    char type;
    int num;
    char color;
};
vector<op> ans;

struct Ptr {
    int next;
    int prev;
};

const int N = 2000, base = 1 << 11;
int n, m;
char a[N + 1][N + 1];
Ptr rowPtr[N + 2];
Ptr colPtr[N + 2];
unordered_set<char> color;

char tRow[N + 1][base * 2 + 1];
char tCol[N + 1][base * 2 + 1];

void mergeSons(char t[], int v) {
    if(v > base) return;
    int l = v * 2, r = v * 2 + 1;
    if(t[l] == t[r]) {
        t[v] = t[l];
    }
    else if(t[l] == 0) {
        t[v] = t[r];
    }
    else if(t[r] == 0) {
        t[v] = t[l];
    }
    else {
        t[v] = '#';
    }
}

void upd(char t[], int v, char c) {
    v += base;
    t[v] = c;
    while(v) {
        mergeSons(t, v);
        v /= 2;
    }
}

int findRow() {
    for(int i = rowPtr[0].next; i <= n; i = rowPtr[i].next) {
        if(tRow[i][1] != '#') {
            return i;
        }
    }
    return 0;
}

int findCol() {
    for(int i = colPtr[0].next; i <= m; i = colPtr[i].next) {
        if(tCol[i][1] != '#') {
            return i;
        }
    }
    return 0;
}

void delRow(int row) {
    rowPtr[rowPtr[row].prev].next = rowPtr[row].next;
    rowPtr[rowPtr[row].next].prev = rowPtr[row].prev;
    for(int i = colPtr[0].next; i <= m; i = colPtr[i].next) {
        upd(tCol[i], row, 0);
    }
}

void delCol(int col) {
    colPtr[colPtr[col].prev].next = colPtr[col].next;
    colPtr[colPtr[col].next].prev = colPtr[col].prev;
    for(int i = rowPtr[0].next; i <= n; i = rowPtr[i].next) {
        upd(tRow[i], col, 0);
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    FOR(i, 1, n) {
        FOR(j, 1, m) {
            cin >> a[i][j];
            color.insert(a[i][j]);
        }
    }
    /// inicjalizacja wskaznikow
    rowPtr[0].prev = 0; rowPtr[0].next = 1;
    rowPtr[n + 1].prev = n; rowPtr[n + 1].next = n + 1;
    FOR(i, 1, n) { 
        rowPtr[i].prev = i - 1;    
        rowPtr[i].next = i + 1;
    }  
    colPtr[0].prev = 0; colPtr[0].next = 1;
    colPtr[m + 1].prev = m; colPtr[m + 1].next = m + 1;
    FOR(i, 1, m) {
        colPtr[i].prev = i - 1;
        colPtr[i].next = i + 1;
    }
    /// inicjalizacja drzew
    FOR(i, 1, n) {
        FOR(j, 1, m) {
            upd(tRow[i], j, a[i][j]);
            upd(tCol[j], i, a[i][j]);
        }
    }
    /// usuwanie kolumn i rzedow
    while(rowPtr[0].next != n + 1 && colPtr[0].next != m + 1) {
        int row = findRow();
        if(row == 0) { 
            int col = findCol();
            delCol(col);
            ans.push_back({'K', col, tCol[col][1]});
        }
        else {
            delRow(row);
            ans.push_back({'R', row, tRow[row][1]});
        }
    }
    cout << ans.size() << '\n';
    for(int i = ans.size() - 1; i >= 0; i--) {
        cout << ans[i].type << ' ' << ans[i].num << ' ' << ans[i].color << '\n';
    }
    return 0;
}