Vakond#265
Egy nehéz kutatás után Anton úgy döntött, hogy kikapcsolódik a vidéki házában. Gyönyörű kertje van sok különböző virággal. De, ó ne, megérkezésekor jelentős számú lyukat látott a földön. Ez egy vakond!
Most, egy ásóval felfegyverkezve, Anton várni fogja a vakondot. A vakond bármelyik lyukból előbukkanhat. Anton olyan pozíciót szeretne választani, hogy a legrosszabb esetben a lehető minimális idő alatt fussa le a vakondot.
A kertet egy n \times m mátrixként lehet reprezentálni, ahol a sorok száma, és az oszlopok száma. A sorokat felülről lefelé, -től -ig számozzuk. Az oszlopokat balról jobbra, -től -ig számozzuk. Így a indexű cella a bal felső sarokban található.
A kert minden cellája, a_{i, j}, leírja a cella állapotát:
a_{i, j} = "." — ez a cella nem tartalmaz virágokat vagy lyukakat;
a_{i, j} = "F" — ez a cella virágokat tartalmaz;
a_{i, j} = "H" — ez a cella lyukat tartalmaz.
Anton tudja, hogy a lyukak száma nem haladja meg a -at.
Mint olyan, aki sok időt fektetett ezekbe a virágokba, a szíve nem bírja elviselni, hogy letapossa azokat. Ezért olyan utat kell találnia, amely nem halad át rajtuk.
Bármikor Anton át tud menni a pozícióból az alábbi pozíciók egyikére: (x-1,y), (x+1,y), (x,y-1), (x,y+1), feltéve, hogy az új pozíció nem tartalmaz virágokat, és a kertben van.
Keressük meg az összes olyan pozíciót (), ahonnan Anton a legrosszabb esetben a lehető legkevesebb idő alatt fog futni a vakondhoz.
Az első sor két egész számot tartalmaz, , (1 \le n \cdot m \le 2 \cdot 10^5) — a kert hosszát és szélességét.
A következő sor mindegyike karaktert tartalmaz — a kert leírása.
Biztosított, hogy minden olyan cellából, amely nem tartalmaz virágokat, elérhető másik olyan cella, amely nem tartalmaz virágokat, a cellákon keresztüli mozgással, amelyek nem tartalmaznak virágokat.
Biztosított, hogy legalább egy lyuk van, és a lyukak száma a kertben nem haladja meg a -at.
Az első sorban egyetlen egész számot kell kiírni, (1 \leq x \leq n \cdot m) — az optimális pozíciók száma.
Minden következő sorban ki kell írni az optimális pozíciókat () a vakondra várásra (1 \le x \le n, 1 \le y \le m).
A pozíciókat bármilyen sorrendben ki lehet írni.
Példa
1. példa
Fent látható az első példa és az optimális várakozási pozíciók vannak megjelölve.
Legyen a lyukak száma a kertben.
( pont): n = 1, m = 2;
( pont): n = 1;
( pont): k = 1, n \cdot m \le 5 \cdot 10^3;
( pont): n \cdot m \le 5 \cdot 10^3;
( pont): k = 1;
( pont): további korlátozások nélkül.