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
#include <bits/stdc++.h>
using namespace std;
#define ssize(x) int(x.size())
#define pb push_back

struct DSU {
	struct info {
		char c; // c - jaka literka
		int s, l, r; // s - ile ma literek, l, r - rep. lewego i prawego sasiada
	};
	vector <int> rep, siz;
	vector <info> comp;

	void init(int n) {
		rep.clear(), siz.clear(), comp.clear();
		rep.resize(n), siz.resize(n, 1), comp.resize(n);
		for(int i=0; i<n; ++i) rep[i]=i;
	}

	int Find(int x) {
		if(rep[x]!=x) rep[x]=Find(rep[x]);
		return rep[x];
	}

	void Union(int a, int b) { // a jest przed b
		a=Find(a), b=Find(b);
		if(a==b) return;
		if(!comp[a].s) comp[a].c=comp[b].c;
		if(!comp[b].s) comp[b].c=comp[a].c;

		int l=comp[a].l, r=comp[b].r;
		if(siz[a]<siz[b]) swap(a, b);
		rep[b]=a, siz[a]+=siz[b];
		comp[a].s+=comp[b].s;
		comp[a].l=l, comp[a].r=r;
	}

	void Merge(int a) { // sprobuj zlaczyc z sasiadami
		a=Find(a);
		int b=Find(comp[a].l);
		if(comp[b].c==comp[a].c || !comp[a].s) Union(b, a);
		a=Find(a), b=Find(comp[a].r);
		if(comp[b].c==comp[a].c || !comp[a].s) Union(a, b);
	}
};

int n, m;

int h(int i, int j) {
	return m*i+j;
}

struct oper {
	int x;
	bool t;
	char c;
};

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin>>n>>m;
	vector <vector <char> > board(n, vector <char> (m));
	for(vector <char> &r : board) for(char &c : r) cin>>c;
	DSU dsu_row, dsu_col;
	dsu_row.init(n*m), dsu_col.init(n*m);
	for(int i=0; i<n; ++i) for(int j=0; j<m; ++j) {
		int h1=h(i, j);
		dsu_row.comp[h1]={board[i][j], 1, j ? h(i, j-1) : h1, j+1<m ? h(i, j+1) : h1};
		dsu_col.comp[h1]={board[i][j], 1, i ? h(i-1, j) : h1, i+1<n ? h(i+1, j) : h1};
	}
	for(int i=0; i<n; ++i) for(int j=0; j<m; ++j) dsu_row.Merge(h(i, j)), dsu_col.Merge(h(i, j));
	queue <oper> upd;
	for(int i=0; i<n; ++i) if(dsu_row.siz[dsu_row.Find(h(i, 0))]==m) upd.push({i, 0, dsu_row.comp[dsu_row.Find(h(i, 0))].c});
	for(int j=0; j<m; ++j) if(dsu_col.siz[dsu_col.Find(h(0, j))]==n) upd.push({j, 1, dsu_col.comp[dsu_col.Find(h(0, j))].c});

	vector <oper> ans;
	while(!upd.empty()) {
		oper o=upd.front();
		upd.pop();

		if(o.t==0 && dsu_row.comp[dsu_row.Find(h(o.x, 0))].s==0) continue;
		if(o.t==1 && dsu_col.comp[dsu_col.Find(h(0, o.x))].s==0) continue;

		ans.pb(o);

		if(o.t==0) {
			int i=o.x;
			for(int j=0; j<m; ++j) if(board[i][j]!='?') {
				board[i][j]='?', --dsu_col.comp[dsu_col.Find(h(i, j))].s, dsu_col.Merge(h(i, j));
				if(dsu_col.siz[dsu_col.Find(h(i, j))]==n) upd.push({j, 1, dsu_col.comp[dsu_col.Find(h(i, j))].c});
			}
			dsu_row.comp[dsu_row.Find(h(i, 0))].s=0;
		}
		else {
			int j=o.x;
			for(int i=0; i<n; ++i) if(board[i][j]!='?') {
				board[i][j]='?', --dsu_row.comp[dsu_row.Find(h(i, j))].s, dsu_row.Merge(h(i, j));
				if(dsu_row.siz[dsu_row.Find(h(i, j))]==m) upd.push({i, 0, dsu_row.comp[dsu_row.Find(h(i, j))].c});
			}
			dsu_col.comp[dsu_col.Find(h(0, j))].s=0;
		}
	}
	reverse(ans.begin(), ans.end());
	cout<<ssize(ans)<<"\n";
	for(oper &o : ans) cout<<(o.t?"K":"R")<<" "<<o.x+1<<" "<<o.c<<"\n";
	exit(0);
}