Однажды Алиса делала уборку в своем подвале и заметила кое-что любопытное: бесконечное множество одинаковых деревянных фигур! Каждая фигура была сделана из пяти квадратных плиток, одна из была центральной, а остальные четыре примыкали к ней:
Около кусочков лежала большая квадратная доска. Доска разделена на \(n^2\) клеток, расположенных в \(n\) строках и \(n\) столбцах. Некоторые клетки уже заняты плитками, прибитыми к клеткам. Остальные клетки свободны.
Алиса подумала, сможет ли она заполнить доску полностью, используя найденные фигуры? Конечно, каждая фигура должна покрывать ровно пять ячеек доски, никакие две фигуры не должны перекрываться и ни одна фигура не должна вылезать за пределы доски. Однако доска была слишком большой, и Алиса не смогла покрыть ее вручную. Можете ли вы помочь ей определить, возможно ли полностью покрыть доску фигурами?
Выходные данные
Выведите «YES» если доска может быть полностью покрыта фигурами Алисы и «NO» иначе. Вы можете выводить каждую букву в любом регистре (верхнем или нижнем).
Примечание
Следующие иллюстрации описывают доски из примера и их замощения, если они существуют:
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
#.#
...
#.#
|
YES
|
|
2
|
4
##.#
#...
####
##.#
|
NO
|
|
3
|
5
#.###
....#
#....
###.#
#####
|
YES
|
|
4
|
5
#.###
....#
#....
....#
#..##
|
NO
|