在纸上玩太多之后,Iahub 已经转向电脑游戏。他玩的游戏叫“Block Towers”。它在 n 行 m 列的矩形网格中进行(包含 n × m 个单元)。游戏的目标是建造自己的城市。网格中的一些单元是大洞,Iahub 无法在其中建造任何建筑物。其余单元格为空。在一些空单元中,Iahub 可以精确建造一座以下两种类型的塔:
1. 蓝塔。每个的人口限制等于 100。
2. 红塔。每个单元的人口限制等于 200。但是,只有当至少一个相邻单元具有蓝塔时,才能在某个单元中构建它。两个牢房是邻居,因为它们共享一侧。
Iahub 还可以从任何单元摧毁建筑物。这个手术他想做多少就做多少。摧毁一座建筑物后,其他建筑物不受影响,被摧毁的单元变空(因此如果需要,Iahub可以在该单元中建造一座塔,这种情况请参见第二个示例)。
Iahub 可以说服尽可能多的人进入他的城市。因此他需要配置他的城市以允许尽可能多的人口。因此,他应该找到一系列以最佳方式建造城市的操作序列,以使总人口限制尽可能大。
他说他是这个游戏中最好的,但他没有最优解。编写一个程序来计算最佳的,以向他表明他并不像他想象的那么好。
输入
输入的第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 500)。接下来的 n 行每行包含 m 个字符,描述网格。第 i 行中的第 j 个字符是“.”如果你被允许在坐标(i,j)的单元格上建造一座塔(空单元格),或者如果那里有一个大洞,则建造“#”。
输出
在第一行打印一个整数 k (0 ≤ k ≤ 106) — Iahub 为获得最佳结果而应执行的操作数。
以下 k 行中的每一行必须包含以下格式的单个操作:
1. «B x y» (1 ≤ x ≤ n, 1 ≤ y ≤ m) — 在单元格(x, y)处建造一座蓝色塔;
2. «R x y» (1 ≤ x ≤ n, 1 ≤ y ≤ m) — 在单元格 (x, y) 处建造一座红塔;
3. «D x y» (1 ≤ x ≤ n, 1 ≤ y ≤ m) — 摧毁单元 (x, y) 处的一座塔。
如果有多个解决方案,您可以输出其中任何一个。请注意,您不应该最小化操作数量。
示例
输入 #1
2 3 ..# .#.
输出 #1
4 B 1 1 R 1 2 R 2 1 B 2 3
输入 #2
1 3 ...
输出 #2
5 B 1 1 B 1 2 R 1 3 D 1 2 R 1 2