You are going to construct a new factory in your city. Since you have major electric needs, having the factory placed close to a power plant is important. You want to build a prioritized list of possible locations.
The area in which the factory needs to be located can be represented as a rectangular grid of $N$ rows and $M$ columns of cells. Some of those cells contain a power plant. The new factory occupies exactly one cell, and can be placed in any empty cell (i.e., any cell that does not contain a power plant).
Numbering rows from $1$ to $N$ and columns from $1$ to $M$, the location of a cell can be described by two integers. Cell $(i, j)$ is the cell in row $i$ and column $j$. The distance between cell $(i_0, j_0)$ and cell $(i_1, j_1)$ is $max(|i_0 - i_1|, |j_0 - j_1|)$ where $|x|$ represents the absolute value of $x$. The electric priority of a location is its minimum distance to a power plant.
With this in mind, you will number all possible locations with consecutive integers starting from $1$. You will do it in ascending order of electric priority. Among locations with the same electric priority, you will number them in ascending order of their row numbers. Among locations with the same electric priority and row number, you will list them in ascending order of column numbers.
In the following picture you can see a $4 \times 7$ grid. Black cells are the cells in which there is a power plant. Dark gray cells have an electric priority of $1$, light gray cells an electric priority of $2$ and white cells an electric priority of $3$. The number inside each cell is the number assigned by you to the location.
You will receive several queries about the prioritized list built. In each query you will be given a number representing a position in the prioritized list and you have to calculate which location was assigned the given position.