12102. Де було печиво?
Задається сітка з \(H\) рядків і \(W\) стовпців. Нехай \((i,j)\) позначає квадрат у \(i\)-му рядку зверху та \(j\)-му стовпчику зліва.
Спочатку було одне печиво на кожному квадраті всередині прямокутника, висота та ширина якого становила принаймні 2 квадрати, а на інших квадратах не було печива.
Формально існувала рівно одна четвірка цілих чисел \((a,b,c,d)\), яка задовольняла всі наступні умови:
- \(1≤a<b≤H\)
- \(1≤c<d≤W\)
- Було одне печиво на кожному квадраті \((i,j)\), так що \(a≤i≤b,c≤j≤d\), і жодного печива на інших квадратах.
Однак Степан взяв і з'їв одне з печива на сітці. Квадрат, який містив це печиво, тепер порожній.
У якості вхідних даних вам надається стан сітки після того, як Степан з’їв печиво.
Стан квадрата \((i,j)\) задається символом \(S_{i,j}\) , де # означає квадрат із печивом, а . означає квадрат без нього.
Знайдіть квадрат, у якому було печиво, яке зʼїв Степан. (Відповідь визначається однозначно.)
Обмеження
- \(2≤H,W≤500\)
- \(S_{i,j}\) дорівнює # або .
Формат вхідних даних
Перший рядок містить цілі числа \(H,W\).
Наступні \(H\) рядків містять по \(W\) символів \(A_{i,j}\).
Формат вихідних даних
У вихідний потік виведіть шукані \(i\) та \(j\) у такому порядку, розділивши їх пробілом.
Приклад вхідних даних
5 6
......
..#.#.
..###.
..###.
......
Приклад вихідних даних
2 4
Спочатку печиво було на квадратах усередині прямокутника з (2,3) у верхньому лівому куті та (4,5) у нижньому правому куті, і Степан з’їв печиво на (2,4). Таким чином, ви повинні вивести (2,4).
Приклад вхідних даних
3 2
#.
##
##
Приклад вихідних даних
1 2
Приклад вхідних даних
6 6
..####
..##.#
..####
..####
..####
......
Приклад вихідних даних
2 5
Коментарі