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