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

После тяжёлой рабочий недели Поликарп предпочитает развлечься. Любимое развлечение Поликарпа — это рисование змеек. Поэтому он берёт прямоугольный лист клетчатой бумаги размера $$$n \times m$$$ ($$$n$$$ — количество строк, $$$m$$$ — количество столбцов) и начинает рисовать змей в клеточках.

Поликарп рисует змеек строчными латинскими буквами. Первую змейку он всегда рисует символом 'a', вторую змейку он рисует символом 'b', третью — символом 'c' и так далее. Все змейки имеют свой уникальный символ. Так как в латинице всего $$$26$$$ букв, а Поликарп очень уставший и не хочет придумывать новые символы, то суммарное количество нарисованных змеек не превосходит $$$26$$$.

Поскольку к концу недели Поликарп очень уставший, то он рисует змеек прямыми линиями, без изгибов. Таким образом, каждая змейка может располагаться либо вертикально, либо горизонтально. Ширина любой змейки всегда равна $$$1$$$, то есть каждая змейка имеет размеры либо $$$1 \times l$$$, либо $$$l \times 1$$$, где $$$l$$$ — её длина. Обратите внимание, что изгибаться змейки не могут.

Когда Поликарп рисует очередную змейку, то его новая змейка может использовать клетки, в которых до этого были нарисованы другие змейки. В этом случае новую змейку он рисует «поверх», затирая предыдущее значение в клетке.

Недавно на работе Поликарп нашёл лист клетчатой бумаги с латинскими буквами. Ему стало интересно, мог ли этот лист получиться из пустого путём рисования на нём некоторого количества змеек по описанным выше правилам. Если ответ положительный, то ему также интересен способ рисования этих змеек.

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

В первой строке входных данных содержится целое число $$$t$$$ ($$$1 \le t \le 10^5$$$) — количество наборов входных данных в тесте. Далее содержатся описания $$$t$$$ наборов.

В первой строке описания набора содержатся два целых числа $$$n$$$, $$$m$$$ ($$$1 \le n,m \le 2000$$$) — длина и ширина клетчатого листа, соответственно.

В каждой из последующих $$$n$$$ строк описания набора содержатся $$$m$$$ символов, отвечающих за содержимое соответствующей клетки на листе. Это может быть либо строчная латинская буква, либо символ точка ('.'), обозначающий пустую клетку.

Гарантируется, что суммарная площадь всех листов в одном тесте не превосходит $$$4\cdot10^6$$$.

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

Выведите ответ для каждого из набора входных данных.

В первой строке ответа выведите YES, если существует способ нарисовать змеек так, чтобы получить в точности лист из набора входных данных. Если искомого способа не существует, то выведите NO.

В случае положительного ответа выведите его в следующем формате. В следующей строке выведите целое число $$$k$$$ ($$$0 \le k \le 26$$$) — количество змеек. В следующих $$$k$$$ строках выведите по четыре целых числа $$$r_{1,i}$$$, $$$c_{1,i}$$$, $$$r_{2,i}$$$ и $$$c_{2,i}$$$ — координаты крайних клеток $$$i$$$-й змейки ($$$1 \le r_{1,i}, r_{2,i} \le n$$$, $$$1 \le c_{1,i}, c_{2,i} \le m$$$). Змейки должны быть выведены в порядке их рисования. Если ответов несколько, выведите любой из них.

Обратите внимание, что Поликарп начинает процесс рисования змеек с чистого (пустого) листа.

Примеры
Входные данные
1
5 6
...a..
..bbb.
...a..
.cccc.
...a..
Выходные данные
YES
3
1 4 5 4
2 3 2 5
4 2 4 5
Входные данные
3
3 3
...
...
...
4 4
..c.
adda
bbcb
....
3 5
..b..
aaaaa
..b..
Выходные данные
YES
0
YES
4
2 1 2 4
3 1 3 4
1 3 3 3
2 2 2 3
NO
Входные данные
2
3 3
...
.a.
...
2 2
bb
cc
Выходные данные
YES
1
2 2 2 2
YES
3
1 1 1 2
1 1 1 2
2 1 2 2