Однажды Лёша решил вспомнить детство, когда компьютеры были не такими мощными, и многие играли только в стандартные игры. Лёша тогда любил играть в «Сапёра», представляя что спасает мир от бомб, заложенных террористами, но у него нечасто получалось выигрывать.
Но Лёша вырос, и поэтому сейчас с легкостью проходил самые сложные уровни. Это быстро ему наскучило, и он задумался: а что если в детстве компьютер подсовывал ему некорректные поля с бомбами, и поэтому Лёша не мог выиграть?
Чтобы проверить это, ему требуется ваша помощь.
Поле игры в «Сапер» представляет из себя прямоугольник \(n \times m\), каждая клетка в котором либо пустая, либо содержит бомбу, либо содержит цифру от \(1\) до \(8\). Поле является корректным, если для всех клеток выполняется следующее:
- если в клетке записано число \(k\), то среди соседей данной клетки ровно \(k\) клеток с бомбами,
- если клетка пустая, то среди ее соседей нет клеток с бомбами.
Соседними считаются клетки, имеющие общую вершину или сторону (т. е. у клетки может быть максимум \(8\) соседей).
Выходные данные
Выведите «YES», если поле корректно, иначе выведите «NO».
Вы можете выводить каждую из букв в любом регистре (строчную или заглавную).
Примечание
Во втором примере ответ «NO», потому что, если оставить позиции бомб такими же, то первая строка поля должны быть *2*1.
Подробнее про Сапёр можно прочитать в статье Википедии.