Задача F. Обработка картинок ≡

Условие

У юного программиста Васи есть младший брат Петя.

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

Тогда Вася решил найти сложную картинку и посоревноваться со своим младшим братом в нахождении геометрических фигур.

Картинка представляет из себя набор из N строк по M символов в каждом. Каждый символ может принимать значения с кодами от 33 до 126 в кодировке ASCII.

Петя и Вася решили искать на картинке ромбы специального вида. Контур таких ромбов можно задать уравнением |x − a| + |y − b| = r, где a  — номер столбца центра фигуры, b — номер строки центра фигуры, а r  — ее радиус. Фигура засчитывается только в том случае, если все клетки ее контура содержат один и тот же символ, а также не вылезают за границы картинки. Также не учитываются фигуры, радиус r которых равен 0.

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

Отправка решения и тестирование

В качестве решения принимается как программа, так и текстовый файл, содержащий ответ к задаче в требуемом формате (при его отправке следует выбрать в тестирующей системе среду разработки "Answer text").

Баллы будут начисляться пропорционально количеству правильных ответов в выходном файле. Если правильный ответ на какой-то из тестов получить не удалось, выведите вместо него число −1.

Формат входного файла

Первая строка входного файла содержит целое число T — количество тестов. Следующие строки содержат описания тестов.

Первая строка каждого теста содержит два целых числа N, M — размеры картинки.

Следующие N строк содержат M символов — описание картинки.

Формат выходного файла

Выходной файл должен содержать T ответов на тесты. Каждый ответ состоит из одной или двух строк.

Первая строка содержит целое число K — количество ромбов на картинке. Вторая строка содержит K четверок a, b, r, c, разделенных пробелами, где целые числа a и b — строка и столбец центра ромба, целое число r — радиус ромба и c — символ, которым заполнен его контур. Четверки, описывающие каждый ромб, можно выводить в любом порядке.

В случае, если ответ на тест найти не удалось, выведите для этого теста одну строку с −1.

Примеры тестов

2
7 7
1111111
1~~A~~1
1.A.A.1
1A...A1
1~A~A~1
1~~A~~1
1111111
7 7
1111111
1~~A~~1
1.A.A.1
1A...A1
1BA~AB1
B~BAB~B
1B111B1

1
4 4 2 A
3
4 4 2 A 6 2 1 B 6 6 1 B