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