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 ≤ n, m ≤ 500 000, n * m ≤ 10^6).
Наступні n рядків містять по m малих латинських літер — опис таблиці, де j-й символ i-го рядка задає колір клітинки (i, j). Однакові літери позначають однаковий колір, а різні — різний.
У наступному рядку знаходиться число q — кількість запитань екзаменатора (1 ≤ q ≤ 200 000).
Наступні q рядків містять опис запитань. У i-му рядку знаходяться два числа x[i] і y[i] — номер рядка і стовпця, на перетині яких знаходиться клітинка, для якої потрібно знайти відповідь (1 ≤ x[i] ≤ n, 1 ≤ y[i] ≤ m).
Вихідні дані
Для кожного запитання виведіть відповідь в окремому рядку. Якщо неможливо знайти пару клітинок, що задовольняють усім умовам, виведіть -1. Інакше виведіть чотири числа r[1], c[1], r[2], c[2] — координати двох вибраних клітинок. Якщо існує кілька оптимальних відповідей, виведіть будь-яку з них.