IQ тест для роботов
IQ тест для роботов
Лёша готовит своего робота к тестированию IQ. В 2116 году тестирование IQ для роботов проходит следующим образом. Роботу демонстрируется прямоугольная таблица, содержащая n строк и m столбцов, каждая клетка которой покрашена в какой-либо цвет.
Затем экзаменатор q раз просит робота выполнить следующее задание. Экзаменатор указывает на некоторую клетку в таблице, а робот в качестве ответа должен выбрать две другие клетки. При этом должны выполняться следующие условия.
- Ни одна из выбранных роботом клеток не должна совпадать с указанной экзаменатором.
- Одна из выбранных клеток должна лежать в одном столбце с указанной, а другая - в одной строке.
- Цвета двух выбранных роботом клеток должны быть различны.
- Расстояние между выбранными клетками должно быть минимально. Расстояние между клетками (
r1
,c1
) и (r2
,c2
) определяется как |r1
-r2
| + |c1
-c2
|.
Бывает, что выбрать две клетки описанным образом невозможно, в этом случае в качестве ответа на задание робот должен сообщить об этом.
Лёша хочет научить своего робота справляться с заданием как можно лучше. Помогите ему запрограммировать робота.
Входные данные
В первой строке находятся целые числа n и m - количество строк и столбцов в таблице, соответственно (2 ≤ n, m ≤ 500 000, n * m ≤ 106
).
Следующие n строк содержат по m строчных латинских букв - описание таблицы, j-й символ i-й из этих строк задает цвет клетки (i, j). Одинаковые буквы обозначают одинаковый цвет, а разные - разный.
В следующей строке находится число q - количество вопросов экзаменатора (1 ≤ q ≤ 200 000).
Следующие q строк содержат описание вопросов. В i-й из этих строк находятся два числа xi
и yi
- номер строки и столбца, на пересечении которых находится клетка, для которой требуется найти ответ (1 ≤ xi
≤ n, 1 ≤ yi
≤ m).
Выходные данные
Для каждого вопроса выведите ответ в отдельной строке. Если невозможно найти пару клеток, удовлетворяющих всем условиям, выведите -1. Иначе выведите четыре числа r1
, c1
, r2
, c2
- описание двух выбранных клеток. Если оптимальных ответов несколько, выведите любой.
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