IQ test for robots
Alex is preparing his robot for an IQ test. In the year 2116, IQ testing for robots involves the following scenario: The robot is presented with a rectangular grid consisting of n rows and m columns, where each cell is painted a specific color.
The examiner then assigns the robot a task to be performed q times. For each task, the examiner points to a particular cell in the grid, and the robot must select two other cells according to these rules:
The selected cells must not include the cell indicated by the examiner.
One selected cell must be in the same column as the indicated cell, and the other must be in the same row.
The colors of the two selected cells must differ.
The distance between the selected cells should be minimized. The distance between cells (
r[1],c[1]) and (r[2],c[2]) is calculated as |r[1]-r[2]| + |c[1]-c[2]|.
If it is impossible to select two cells that meet these criteria, the robot should report this as the answer.
Alex wants to program his robot to complete this task as efficiently as possible. Your task is to assist him in this endeavor.
Input
The first line contains two integers n and m, representing the number of rows and columns in the grid, respectively (2 ≤ n, m ≤ 500,000, n * m ≤ 10^6).
The next n lines each contain m lowercase Latin letters, describing the grid. The j-th character in the i-th row specifies the color of the cell at position (i, j). Identical letters indicate the same color, while different letters indicate different colors.
The following line contains the integer q, the number of questions posed by the examiner (1 ≤ q ≤ 200,000).
The next q lines each contain two integers x[i] and y[i], indicating the row and column of the cell for which a response is required (1 ≤ x[i] ≤ n, 1 ≤ y[i] ≤ m).
Output
For each question, output the answer on a separate line. If it is impossible to find a pair of cells that satisfy all the conditions, output -1. Otherwise, output four integers r[1], c[1], r[2], c[2], representing the two selected cells. If there are multiple optimal solutions, any one of them can be output.