Отец Мадоки достиг отметки в \(1\) миллион подписчиков на Mathub! В честь этого вебсайт решил отправить ему персонализированную награду — Битовую Кнопку Mathub!
Награда представляет из себя таблицу из \(n\) строк и \(m\) столбцов, в каждой клетке которой записано число \(0\) или \(1\). Изучив таблицу, она вывела следующие характеристики:
- Подпрямоугольник \(A\) лежит в подпрямоугольнике \(B\), если нет клетки, которая лежит внутри \(A\), но при этом не лежит внутри \(B\).
- Два подпрямоугольника пересекаются, если найдется клетка, лежащая внутри обоих подпрямоугольников.
- Подпрямоугольник называется чёрным, если в нём нет клетки со значением \(0\).
- Подпрямоугольник называется красивым, если он чёрный и не лежит в каком-то другом чёрном подпрямоугольнике.
- Таблица называется элегантной, если никакие два красивых подпрямоугольника не пересекаются.
Например, на первой картинке красный подпрямоугольник является красивым, а на второй нет, так как он лежит внутри фиолетового подпрямоугольника.
Помогите Мадоке определить, является ли таблица элегантной.
Выходные данные
Для каждого набора входных данных выведите «YES», если данная таблица является элегантной. Иначе, выведите «NO».
Вы можете выводить каждую букву в любом регистре (например, «YES», «Yes», «yes», «yEs» будут распознаны как положительный ответ).
Примечание
Во втором наборе входных данных таблица не элегантная, поскольку красный красивый подпрямоугольник пересекается с фиолетовым.
В четвертом наборе входных данных таблица не элегантная, поскольку красный красивый подпрямоугольник пересекается с фиолетовым.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
3 3
100
011
011
3 3
110
111
110
1 5
01111
4 5
11111
01010
01000
01000
3 2
11
00
11
|
YES
NO
YES
NO
YES
|