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 ≤ n, m ≤ 500 000, n * m ≤ 10^6).
Следующие n строк содержат по m строчных латинских букв - описание таблицы, j-й символ i-й из этих строк задает цвет клетки (i, j). Одинаковые буквы обозначают одинаковый цвет, а разные - разный.
В следующей строке находится число q - количество вопросов экзаменатора (1 ≤ q ≤ 200 000).
Следующие q строк содержат описание вопросов. В i-й из этих строк находятся два числа x[i] и y[i] - номер строки и столбца, на пересечении которых находится клетка, для которой требуется найти ответ (1 ≤ x[i] ≤ n, 1 ≤ y[i] ≤ m).
Выходные данные
Для каждого вопроса выведите ответ в отдельной строке. Если невозможно найти пару клеток, удовлетворяющих всем условиям, выведите -1. Иначе выведите четыре числа r[1], c[1], r[2], c[2] - описание двух выбранных клеток. Если оптимальных ответов несколько, выведите любой.