Animal Cage Identification

The suburban zoo once implemented an advanced automated management system to care for its animals. However, due to an oversight about the \(2000\) problem, the system encountered bugs at the turn of the century. One consequence was that some cages opened automatically and the animals escaped. Fortunately, the zoo was already closed so no animal actually left the premises. Sheriff Still and his team later recaptured all animals and rounded them up in the zoo square. With the system completely crashed, the records of which cage each animal originally came from were lost.

The only information available are sporadic observations in the following format:

At minute \(t\), animal \(i\) was seen at position \((x,y)\).

The zoo terrain is described by an \(n \times n\) grid. Each cell is either a building or a plain. Cages can only be located on plain cells and animals can only move on plain cells. Different cages may even be placed in the same cell; however, each cage holds exactly one animal and different animals come from different cages. Moreover, different animals have different maximum speeds. For example, a tiger can run through \(5\) cells per minute while a cat can only run through \(2\) cells per minute.

For each observation, if an animal with a speed of \(v\) was seen at time \(t\) at a position, then its cage must be located on a plain cell such that the shortest path (using four-directional moves on plain cells and avoiding buildings) from the cage to the observed position is at most \(v \times t\). If there are multiple cells satisfying the condition for an animal, choose the one with the smallest row number; if still ambiguous, choose the one with the smallest column number.

Your task is to determine the original cage position for each animal given all observations.

inputFormat

The input is given as follows:

1. An integer \(n\) denoting the size of the grid.
2. Next \(n\) lines, each containing a string of length \(n\). Each character is either . (plain) or # (building).
3. An integer \(k\) representing the number of animals.
4. A line with \(k\) integers, where the \(i^{th}\) integer \(v_i\) represents the speed (in cells per minute) of animal \(i\) (1-indexed).
5. An integer \(m\) representing the number of observations.
6. Next \(m\) lines, each containing four integers: t i x y, meaning that at minute \(t\), animal \(i\) was seen at the cell in row \(x\) and column \(y\) (0-indexed).

It is guaranteed that all observations are valid (i.e. they occur on plain cells) and a solution exists for each animal.

outputFormat

Output \(k\) lines. The \(i^{th}\) line should contain two integers representing the row and column (0-indexed) of the cage for animal \(i\). If there are multiple valid positions, output the one with the smallest row number, and if there is still a tie, the one with the smallest column number.

sample

3
...
.#.
...
2
5 2
3
1 1 0 0
2 2 2 2
3 1 2 0

0 0
0 0