19861번 - 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$ --- описание двух выбранных клеток. Если оптимальных ответов несколько, выведите любой.