Worst Case Scenario

The disease is spreading fast, and the government has asked for a map of the infected regions. They want to see what certain regions would look like in the worst case after a series of events. The government tracks four stages of infection.

• Stage A: the infection has not reached this zone yet. An infection event can still push such a zone to a higher stage.
• Stage B: this zone is in the early stages of infection. Individual citizens are reported behaving erratically, quarantines are starting, and the municipal authorities still have things under control.
• Stage C: this zone is dealing with mobs of zombies in a few areas. Quarantines happen on the scale of towns and small cities. The infection stays inside the zone but is growing out of control.
• Stage D: this zone has lost control of its borders. The infection reaching the neighboring zones is only a matter of time.

An infection event is anything that pushes a zone toward a higher stage of infection, usually a quarantine breach, a virus mutation, or biological terrorism. When an infection event occurs in a zone, the worst case is that the zone advances one stage. A zone in stage D cannot advance any further, so in the worst case every additional infection event it experiences causes an outbreak. When an outbreak occurs, all neighboring zones experience one additional infection event. Outbreaks chain into each other, but while a single infection event is being processed, each zone breaks out at most once.

Zones marked with the character X are impassable and unpopulated, so they never become infected and never change stage. Two zones are adjacent when one sits directly above, below, to the left, or to the right of the other on the grid. The infection never spreads diagonally during an outbreak.

You are given a grid of zones with their starting stages and a sequence of infection events with the coordinates of the zones where they occur. Process each infection event fully before calculating the result of the next one.

The first line contains the number of test cases $N$ ($1 \le N \le 50$). Each test case begins with a line giving the width $W$ ($1 \le W \le 100$) and the height $H$ ($1 \le H \le 100$) of the grid, followed by the grid itself on $H$ lines of $W$ characters each. Each zone is marked by the stage it is currently in, or by the character X if the zone is impassable.

The line after the grid gives the number of infection events $I$ ($0 \le I \le 1000$). Then follow $I$ lines, each with two integers $x$ and $y$. Such a line is an infection event in the zone at column $x$ (the leftmost column is $x = 0$) and row $y$ (the top row is $y = 0$).

For each test case, print the final grid for the worst case: $H$ lines of $W$ characters. Print nothing between test cases.