D. Блок Цамхаг

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Цаасан дээр тоглодог тоглоом ихээр тоглосоныхоо дараа Иахуб компьютер тоглоом тоглохоор шийдсэн. Түүний тоглох тоглоомын нэр нь "Блок Цамхагууд" юм. Үүнийг $n$ мөр $m$ баганатай тэгш өнцөгт хүснэгтэн дээр тоглоно ($n × m$ нүд агуулна). Тоглоомын гол зорилго нь та өөрийн хотоо байгуулах явдал юм. Зарим нүднүүд нь маш том нүх буюу энэ нүдэнд Иахуб юу ч барьж чадахгүй. Бусад нүднүүд нь хоосон байна. Хоосон нүдэнд Иахуб дараах хоёр төрлийн цамхагийн яг нэгийг нь барьж чадна:

  1. Хөх цамхагууд. Тус бүрийнх нь нягтаршлын хязгаар нь $100$.
  2. Улаан цамхагууд. Тус бүрийнх нь нягтаршлын хязгаар $200$. Гэсэн ч энэ цамхагийг барих мөчид ядаж нэг хөрш нүдэнд нь хөх цамхаг байх ёстой. Аль нэг талаараа давхцаж байвал уг хоёр нүд нь хөрш болно.

Иахуб дурын нүдэн дахь барилгыг устгаж болно. Тэр энэ үйлдлийг хүссэн тоогоороо хийж болно. Барилгыг устгасаны дараа бусад барилгад нөлөөлөхгүй ба уг нүд нь хоосон болно (хэрвээ Иахуб хүсвэл уг нүдэнд цамхаг барьж болох ба ийм тохиолдлыг хоёр дахь жишээнээс харна уу).

Иахуб хотдоо хүссэн хэмжээний хүн амыг ирүүлэхээр ятгаж чадна. Тэр өөрийн хотыг боломжит хамгийн их нягтаршилтай байлгах хэрэгтэй байна. Иймд Иахуб хотын нийт нягтаршлын хязгаар боломжит хамгийн их байхаар хотыг хамгийн тохиромжтойгоор байгуулах үйлдлүүдийн дарааллыг олох шаардлагатай.

Тэр өөрийгөө энэ тоглоомон дээр хамгийн шилдэг нь гэж байгаа боловч хамгийн тохиромжтой шийдлийг мэдэхгүй байна. Түүнд өөрийг нь бодож байгаа шиг нь сайн биш гэдгийг нь харуулах хамгийн тохиромжтой шийдлийг тооцоолдог програм бичнэ үү.

Оролт

Оролтын эхний мөрөнд хоёр бүхэл тоо $n$ ба $m$ ($1 ≤ n, m ≤ 500$) байна. Дараагийн $n$ мөр бүрт хүснэгтийг илэрхийлэх $m$ тэмдэгт байна. Хэрвээ та $(i, j)$ координаттай нүдэнд цамхаг барьж болохоор бол (хоосон бол) $i$-р мөрний $j$-р тэмдэгт нь '$.$' байна, харин уг нүдэнд том нүх байгаа бол уг тэмдэгт нь '$#$' байна.

Гаралт

Иахуб хамгийн тохиромжтой үр дүнг гаргахын тулд хийх ёстой үйлдлүүдийн тоог илэрхийлэх $k$ $(0 ≤ k ≤ 10^{6})$ тоог эхний мөрөнд хэвлэ.

Дараагийн $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)$ нүдэнд байгаа цамхагийг устгах.

Хэрвээ хэд хэдэн шийдэл байвал та алийг нь ч хэвлэж болно. Та үйлдлүүдийн тоог хамгийн бага байлгах шаардлагагүй.

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
2 3
..#
.#.
Гаралт
4
B 1 1
R 1 2
R 2 1
B 2 3
Оролт
1 3
...
Гаралт
5
B 1 1
B 1 2
R 1 3
D 1 2
R 1 2
Сэтгэгдлүүдийг ачааллаж байна...