Пазл
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано клеточное поле $$$n \times m$$$. Некоторые клетки имеют углубления, в которые можно вставлять фигурки; они обозначены символом «.», остальные клетки обозначены символом «#».

Также у вас есть фигурки трех видов, которые вы можете вставлять в любые свободные клетки поля. Они изображены на рисунке ниже:

Ваша задача состоит в том, чтобы заполнить все свободные клетки указанными фигурками или сказать, что это невозможно.

Входные данные

Первая строка ввода содержит одно число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Затем следуют описания наборов.

Первая строка каждого набора содержит пару чисел $$$n$$$ и $$$m$$$ ($$$2 \le n, m \le 10^6$$$) — высоту и ширину поля, соответственно.

Затем следуют $$$n$$$ строк, каждая из которых состоит из $$$m$$$ символов «.» или «#».

Сумма $$$n \cdot m$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^6$$$.

Выходные данные

Для каждого набора входных данных выведите «No», если ответа не существует.

В ином случае в первой строке выведите «Yes», а затем выведите $$$n$$$ строк, каждая из которых состоит из $$$m$$$ чисел от $$$0$$$ до $$$10^9$$$. Клетки, в которых нет фигурок, должны быть обозначены числом $$$0$$$, а остальные клетки могут содержать произвольные числа, при чем каждая фигурка должна быть обозначена множеством клеток, содержащих одинаковые числа.

Пример

Входные данные

    36 6#....#.#..#..............#..#.#....#4 4....#..##..#....4 7...#.....###.....#.....###..

Выходные данные

    Yes
    0 1 1 2 2 0
    1 0 1 2 0 2
    1 1 3 3 2 2
    4 4 3 3 5 5
    4 0 4 5 0 5
    0 4 4 5 5 0
    No
    No