Задача №113458. IQ тест для роботов
Лёша готовит своего робота к тестированию IQ. В 2116 году тестирование IQ для роботов проходит следующим образом. Роботу демонстрируется прямоугольная таблица, содержащая \(n\) строк и \(m\) столбцов, каждая клетка которой покрашена в какой-либо цвет.
Затем экзаменатор \(q\) раз просит робота выполнить следующее задание. Экзаменатор указывает на некоторую клетку в таблице, а робот в качестве ответа должен выбрать две другие клетки. При этом должны выполняться следующие условия.
- Ни одна из выбранных роботом клеток не должна совпадать с указанной экзаменатором.
- Одна из выбранных клеток должна лежать в одном столбце с указанной, а другая — в одной строке.
- Цвета двух выбранных роботом клеток должны быть различны.
- Расстояние между выбранными клетками должно быть минимально. Расстояние между клетками \((r_1, c_1) \ и \ (r_2, c_2)\) определяется как \(|r_1 \ − \ r_2| \ + \ |c_1 \ − \ c_2\)|.
Лёша хочет научить своего робота справляться с заданием как можно лучше. Помогите ему запрограммировать робота.
В первой строке находятся целые числа \(n\) и \(m\) — количество строк и столбцов в таблице, соответственно (\(2 \le n, m \le 500 000; n \times m \le 10^6\) ).
Следующие \(n\) строк содержат по \(m\) строчных латинских букв — описание таблицы, \(j\)-й символ \(i\)-й из этих строк задает цвет клетки (\(i, \ j\)). Одинаковые буквы обозначают одинаковый цвет, а разные — разный.
В следующей строке находится число \(q\) — количество вопросов экзаменатора (\(1 \le q \le 200 000\)).
Следующие \(q\) строк содержат описание вопросов. В \(i\)-й из этих строк находятся два числа \(x_i\) и \(y_i\) — номер строки и столбца, на пересечении которых находится клетка, для которой требуется найти ответ (\(1 \le x_i \le n, 1 \le y_i \le m\)).
Для каждого вопроса выведите ответ в отдельной строке. Если невозможно найти пару клеток, удовлетворяющих всем условиям, выведите -1. Иначе выведите четыре числа \(r_1, \ c_1, \ r_2, \ c_2\) — описание двух выбранных клеток. Если оптимальных ответов несколько, выведите любой.
3 4 abbb baab babb 4 1 1 1 4 3 1 3 4
-1 1 1 2 4 3 2 2 1 2 4 3 2