Description

The zoo located in the suburbs adopted then-advanced automated management facilities to manage the animals. However, because the system did not consider the $2000$ year problem, the staff became very worried. Although many preventive measures were taken, the system still developed some bugs around the turn of the century, and some cage doors opened automatically, letting the animals inside escape.

Fortunately, the zoo had already been closed, so animals will not leave the zoo. Sheriff Still received the alarm and led a team of officers to the scene. By then the animals had already gotten out of their cages, so the officers spent a lot of time bringing the situation under control, and all animals were sent to the plaza of the zoo. However, there was a tricky problem: since the system had completely crashed, it was impossible to know from which cage each animal had escaped. The officers remembered some of the animals’ movements, all in the following form:

At minute $t$, a certain animal was seen at a certain position.

Still hopes to use these scattered pieces of information to determine from which cage each animal escaped.

Task

Based on the given information, write a program to determine the location of each animal’s cage.

The zoo’s terrain is described by an $n\times n$ grid. A cell can be either a building or open ground. Cage locations can only be on open ground, and animals only move on open ground. Each animal runs at a different speed. For example, a tiger can run $5$ cells per minute, while a cat can only run $2$ cells per minute, etc. The following is an example (the shaded cells are buildings):

Each cage holds exactly one animal, and different cages hold different animals. Different cages may be in the same cell.

Input Format

The first line contains a natural number $n$, the side length of the grid.

The next $n$ lines form an $n\times n$ character matrix describing the zoo’s terrain. Here . denotes open ground, and * denotes a building.

The next line contains a natural number $p$, the number of cages (which is also the number of animals).

The next $p$ lines each contain two natural numbers $R,C$, indicating that a cage is at row $R$, column $C$ of the grid.

The next $p$ lines each contain an integer $V_i$, in order giving the speed (cells/minute) of animal $i$. Each animal is identified by its index.

The next line contains a natural number $r$, the number of pieces of information provided by the officers.

The next $r$ lines each contain four natural numbers $t,x, y, j$, meaning that at minute $t$, animal $j$ was seen at position $(x, y)$ on the grid.

Refer to the sample for the specific format.

Output Format

Output any feasible solution.

Print $p$ lines, each with three integers $i,x,y$, meaning that animal $i$ was originally at cell $(x,y)$.

5
.....
.***.
.....
.***.
.....
2
1 3
5 2
1
2
2
5 3 1 2
4 5 5 1

1 5 2
2 1 3

Hint

$1\leq n,p\leq 100$，$x,y\leq n$。

Note: For certain testdata there may be multiple solutions; output any one of them.

Translated by ChatGPT 5