Petunjuk Kasar

Hari acara penutupan OSN 2009 akhirnya tiba juga. Pak Dengklek dan bebek-bebeknya sudah bangun pagi-pagi dan hendak berangkat ke tempat acara. Baru saja keluar dari rumahnya, Pak Dengklek menyadari bahwa ia hanya ingat petunjuk jalan kasar dari rumahnya menuju ke tempat acara penutupan. Petunjuk tersebut adalah petunjuk kasar seperti “lurus, belok kiri, belok kanan, belok kiri, belok kanan, lurus, sampai deh…”. Karena banyaknya persimpangan di tengah kota, Pak Dengklek menyadari bahwa petunjuk ini tidaklah akurat, petunjuk ini dapat mengantarkannya ke beberapa tempat. Bantulah Pak Dengklek untuk mencapai tempat acara penutupan setidaknya dengan membantu menemukan tempat-tempat yang mungkin dicapai dari rumah Pak Dengklek dengan petunjuk yang ada.

Untuk menyederhanakan persoalan, peta kota diberikan dalam bentuk matriks berukuran R kali C, dimana R adalah banyak baris dan C adalah banyak kolom. Sebagai catatan, Pak Dengklek memulai perjalanan dari rumahnya dengan arah mula-mula menghadap ke utara.

FORMAT MASUKAN

Baris pertama berisi dua buah bilangan bulat R dan C (1 ≤ R, C ≤ 200) yakni banyaknya baris dan kolom pada peta. Setiap kotak pada peta diwakilkan oleh sebuah karakter. Terdapat tiga kemungkinan karakter sebagai berikut:

Baris ke-(R+2) berisi sebuah bilangan bulat N (1 ≤ N ≤ 20) yang merupakan banyaknya instruksi pada petunjuk kasar yang Pak Dengklek ingat. Terdapat tiga kemungkinan instruksi sebagai berikut: Ingat bahwa tentunya dalam pencarian, Anda ataupun Pak Dengklek tidak boleh keluar dari peta yang diberikan.

FORMAT KELUARAN

Baris pertama berisi sebuah bilangan bulat M yang merupakan banyaknya tempat yang mungkin dicapai dari rumah Pak Dengklek dengan petunjuk yang ada. M baris berikutnya masing-masing berisi dua buah bilangan bulat dipisahkan spasi yang merupakan posisi baris lalu posisi kolom dari tempat yang mungkin dicapai dari rumah Pak Dengklek, diurutkan berdasarkan posisi baris dahulu baru posisi kolom. Dengan urutan instruksi tertentu, walaupun cukup aneh, bisa jadi salah satu tempat yang mungkin menjadi tempat acara penutupan adalah tempat dimana rumah Pak Dengklek berada. Dan karena tugas Anda hanyalah membantu menemukan tempat-tempat yang mungkin dicapai dari rumah Pak Dengklek dengan petunjuk yang ada, Anda tetap perlu mencetak posisi rumah Pak Dengklek jika posisi tersebut dapat dicapai dengan petunjuk yang ada.

CONTOH MASUKAN

9 14
##############
##...##.##.#.#
#..#.......#..
#..#.##.##.#.#
#....##....#.#
#.##.##.##.#..
#.##....##.###
#H##.##.##.###
##############
5
LURUS
KANAN
LURUS
KIRI
LURUS

CONTOH KELUARAN

6
2 3
2 5
3 3
3 5
4 3
4 5

Penjelasan Contoh

Gambar di bawah ini menjelaskan cara mencapai tiga dari enam kemungkinan tempat tujuan sesuai dengan petunjuk kasar yang ada.