В конце полного приключений и опасностей путешествия Индиана Джонс добрался до входа в подземный замок крестоносцев, где хранится чаша Грааля. В руках у него находится план замка, состоящего из M этажей размера N×N. Хотя путь до чаши тернист и извилист, у профессора археологии есть все, что беспрепятственно передвигаться по замку – кнут, лестницы и динамит. Узкие коридоры и тупики-ловушки не могут остановить Джонса, единственной проблемой остаются преграды, которые необходимо взрывать, рискуя быть похороненным под обломками древнего замка. Напишите программу, определяющую наименьшее количество стен, которые необходимо уничтожить, чтобы можно было добраться до чаши Грааля.

В первой строке входного файла записаны числа M и N (1 ≤ M, N ≤ 20). Далее приведены планы M этажей, каждый из которых задан таблицей N×N символов, где символ "." (точка) означает свободное пространство, а "#" соответствует монолитной стене. Местоположение Индианы указано буквой "I", а чаши Грааля – буквой "G". Планы этажей разделяются пустыми строками.

Выведите в выходной файл наименьшее количество стенок, которые требуется уничтожить, чтобы по образовавшимся полостям можно было добраться до чаши Грааля. Далее выведите в выходной файл план замка с разрушенными стенками в том же формате, что и в файле входных данных. Разрушенную стенку обозначайте на плане знаком "-". Пример входных данных выходных данных

input.txt	output.txt
3 4 #### ...# #### ###I .### ##.. ###. #### G### ###. ###. ###.	2 -### ...# #### ###I .### ##.. ###. ###- G### ###. ###. ###.