Battle simulation

You are building a battle simulation game where two factions fight on a 2D grid map of size $H \times W$. Each cell can be written as a coordinate pair $(y, x)$. Cells in the first row are $(0, 0), (0, 1), \cdots, (0, W-1)$ from left to right, and cells in the second row are $(1, 0), (1, 1), \cdots, (1, W-1)$. Every cell up to the last row is written in the same way. The cells directly above, below, left, and right of a cell are called adjacent to that cell.

The map is made of various terrains, and each terrain has a fixed roughness value. Several units are placed on the map without overlapping, and each unit belongs to one of the two factions. As long as it stays on the map, a unit can move up, down, left, or right to an adjacent cell. Each move costs stamina equal to the roughness of the cell entered. Some terrains are too rough to enter at all. Two units from different factions that are adjacent to each other are in combat.

All units ate a hearty combat ration before heading out, so their stamina is unlimited. However, each unit has a limit on the total stamina it can spend in a single dash, and this limit is called the unit's movement power. A dash is a tactical move in which a unit in combat rushes to a nearby target cell in one go, passing through one or more cells. A dash is possible only if no other unit is on the target cell. While dashing, a unit may pass through allied units. If it meets a unit of the opposing faction and becomes adjacent to it, combat starts and the unit must stop there. However, if the selected unit was already in combat, it can dash out of combat.

A bot picks random units and issues dash commands to test the game for bugs. The bot sometimes issues dash commands that cannot be carried out. A command is impossible if the target cell holds another unit, if the target cell is impassable terrain, or if no path to the target exists within the unit's movement power. If the game has no bugs, these commands must be ignored.

Now it is time to check for bugs. Given the bot's commands in time order, write a program that prints each unit's coordinates after all commands are processed in order.

The first line has three space-separated integers $N$, $H$, and $W$, the number of terrain types, the map height, and the map width. ($1 \leq N \leq 9$, $2 \leq H,W \leq 500$)

The next $H$ lines each contain $W$ integers giving the terrain number of each cell from left to right. Each number is between $1$ and $N$, inclusive.

The next line contains $N$ integers $r_1, r_2, \cdots, r_N$ ($-1 \leq r_i \leq 4$, $r_i \neq 0$). If $r_i$ is $-1$, terrain $i$ is too rough to enter. Otherwise, $r_i$ is the roughness of terrain $i$.

The next line contains the number of units $M$. ($1 \leq M \leq H \times W / 4$)

The next $M$ lines describe units 1 through $M$ in order. Each line has four integers $m$, $t$, $a$, $b$: the movement power, the faction, and the $y$ and $x$ coordinates of the unit's cell. ($1 \leq m \leq 20$, $0 \leq t \leq 1$, $0 \leq a < H$, $0 \leq b < W$)

Each cell holds at most one unit, and no unit is placed on a cell whose terrain cannot be entered.

The next line contains the number of dash commands $K$. ($1 \leq K \leq 10\ 000$)

The next $K$ lines each contain three integers $u$, $a$, $b$, meaning that unit $u$ dashes to $(a, b)$. ($1 \leq u \leq M$, $0 \leq a < H$, $0 \leq b < W$)

Print $M$ lines. After all dash commands are processed, line $i$ contains the coordinates $a_i$ and $b_i$ of unit $i$, separated by a space.

The first dash cannot be carried out. Ignoring combat, a unit could reach $(2, 3)$ and then $(1, 3)$ along $(2, 0) \to (2, 1) \to (2, 2) \to (2, 3) \to (1, 3)$. However, the enemy unit at $(3, 3)$ starts combat at $(2, 3)$, so $(1, 3)$ cannot be reached. No detour avoids combat either, so the command is ignored.

The second dash targets a cell with impassable terrain, so it is ignored.

The third dash is possible. The path $(2, 0) \to (3, 0) \to (4, 0) \to (4, 1) \to (4, 2) \to (4, 3)$ costs $7$ stamina, which does not exceed the unit's movement power.

After all commands, unit 1 is at $(4, 3)$ because of the last command, and unit 2 stays at its initial position.