시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.000%

문제

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

예제 입력 1

3 4
abbb
baab
babb
4
1 1
1 4
3 1
3 4

예제 출력 1

-1
1 1 2 4
3 2 2 1
2 4 3 2