Вам дана таблица \(n \times n\).
Обозначим за \((i, j)\) клетку из \(i\)-й строки и \(j\)-го столбца. Для каждой клетки известно, можно ее удалить или нет.
Дано целое число \(k\), вам необходимо удалить ровно \((n-k+1)^2\) клеток из таблицы так, чтобы выполнялось следующее условие.
- Нельзя найти \(k\) неудаленных клеток \((x_1, y_1), (x_2, y_2), \dots, (x_k, y_k)\) которые строго возрастают, т.е. \(x_i < x_{i+1}\) и \(y_i < y_{i+1}\) для всех \(1 \leq i < k\).
Ваша задача найти любое решение, или сказать, что его нет.
Выходные данные
Для каждого набора входных данных, если не существует способа удалить ровно \((n-k+1)^2\) клеток, чтобы выполнить условие, выведите «NO» (без кавычек).
В противном случае выведите «YES» (без кавычек). Затем, выведите \(n\) строк. \(i\)-я строка должна содержать бинарную строку \(t_i\) длины \(n\). \(j\)-й символ \(t_i\) это 0 если клетка \((i, j)\) удалена, и 1 в противном случае.
Если существуют несколько решений, выведите любое из них.
Вы можете выводить «YES» и «NO» в любом регистре (например, строки «yEs», «yes» и «Yes» будут распознаны как положительный ответ).
Примечание
В первом примере достаточно удалить клетку \((1, 1)\).
Во втором примере можно выбрать для удаления клетки \((1,1)\), \((1,2)\), \((4,3)\) и \((4,4)\).
Для третьего примера нет решения, потому что клетки по диагонали всегда будут образовывать строго возрастающую последовательность длины \(5\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
2 2
10
01
4 3
1110
0101
1010
0111
5 5
01111
10111
11011
11101
11110
5 2
10000
01111
01111
01111
01111
|
YES
01
11
YES
0011
1111
1111
1100
NO
YES
01111
11000
10000
10000
10000
|