PEG Judge - WC15 #3 - LexCorp Infiltration

Woburn Challenge 2015-16 Round 3 - Junior Division

Problem 4: LexCorp Infiltration

While the dust settles in the battle between the dark knight and the last son of Krypton, the two have suddenly come to recognize the true mastermind behind it all. After General Zod's invasion on Earth, LexCorp was contracted by the U.S. government to carefully reverse-engineer leftover Kryptonian technology. As it turns out, the battle between the heroes had simply been Lex Luthor's test in his greater conspiracy to craft a powerful biotechnological weapon against Superman. At that point, it became clear to both that the world is in much graver danger than ever before. Luthor's international masquerade as a humanitarian has attracted the attention of Princess Diana of Themyscira, also known as Wonder Woman. After joining forces with Superman and Batman, the trio obtain intel of Luthor's dangerous bio-weapon project – Doomsday.

But it's too late. To destroy the reputation of Superman, Doomsday has already been deployed by Luthor and is wreaking havoc and causing wanton destruction upon Metropolis. Doomsday was originally a deadly monster born from the depths of ancient Krypton. As Luthor has reanimated the abominable legend from his own laboratories on Earth, Doomsday is actually being puppeted from the very control rooms in LexCorp Tower. To stop this vicious foe, Wonder Woman will have to infiltrate LexCorp Tower and use Batman's knockout gas to shut down these control rooms one at a time.

Using his X-ray vision, Superman has helped devise a map of the control floor of LexCorp Tower. He knows that the floor can be represented as a rectangular grid of R rows and C columns (1 ≤ R, C ≤ 1000). The rows are numbered 1..R from north to south, while the columns are numbered 1..C from west to east. The j-th cell in the i-th row can be referred to as cell (i, j). Each cell (i, j) is either part of a control room or a wall, which is indicated by the value of character M_i,j on the map (with "." indicating it is part of a control room and "#" indicating it is a wall). At least one cell will be part of a control room.

The control floor will obviously consist of some number control rooms (at least one), where each control room on the map consists of a consecutive region of "." characters. More formally, every "." cell is part of exactly one control room, and if a pair of "." cells are adjacent to one another, then they must be part of the same control room. Two cells (i₁, j₁) and (i₂, j₂) are adjacent if and only if |i₁ - i₂| + |j₁ - j₂| = 1 (in other words, if they share a side). The size of a control room is the number of "." cells that are part of it.

Releasing knockout gas in a given room will knock out of all its controlpersons, permanently preventing the room from conveying a particular type of vital information to Doomsday's operations. Since Doomsday is already terrorizing Metropolis at a substantial rate, the order in which Wonder Woman infiltrates the rooms is vital in minimizing damage done to the city. Since it's likely that larger control rooms convey more important information, assigning ranks to rooms based on their size may help Wonder Woman workout her plan. At any time during the mission, the rank of control room r is an integer equal to the number of active control rooms whose sizes are strictly larger than control room r's size.

All that said, N (1 ≤ N ≤ 3000) events will take place in the mission, one after another. Each event i concerns a "." cell (A_i, B_i) (1 ≤ A_i ≤ R, 1 ≤ B_i ≤ C), and can be of one of 2 types, indicated by the value T_i (1 ≤ T_i ≤ 2):

Wonder Woman assesses the situation of the control room that cell (A_i, B_i) is part of.
Wonder Woman travels to cell (A_i, B_i) and gasses the entire control room containing that cell.

To make her mission smooth, she has asked you to help her write a program to keep track of her progress. Right before each event i takes place, your program should determine the current rank of the control room containing cell (A_i, B_i) and output it. However, if that cell belongs to a control room that she has already gassed (in one of the first i − 1 events), you should instead output -1 to remind her. When a control room is gassed, it ceases to convey signals to Doomsday, meaning that the ranks of other control rooms may change. On the other hand, gassing an already gassed room has no effect. Superman's reputation is dwindling with every moment of Metropolis's destruction, so you'd better code fast!

In test cases worth 20/40 of the points, there will be no type-2 events.

Input Format

The first line of input will contain three space-separated integers R, C, and N.
The next R lines will each contain C characters M_i,1, M_i,2, …, M_i,C, for i = 1..R.
The next N lines will each contain three space-separated integers T_i, A_i, and B_i, for i = 1..N.

Output Format

Output N lines with a single integer per line. Line i should contain the rank of the control room of the cell targeted by the i-th event (or -1 if the room has already been previously gassed), for i = 1..N.

Sample Input

5 6 5
..#.#.
..####
.#..##
#..##.
..###.
1 1 4
1 3 4
2 1 2
2 3 1
1 1 4

Sample Output

Explanation

If we label each control room cell with the rank of its control room, the map initially looks as follows:

11#3#3
11####
1#00##
#00##2
00###2

There are 5 control rooms. The largest one (the one that includes the south-west cell) has size 6, so its rank is 0. The two size-1 rooms near the top right of the map both have rank 3.

The 3rd event causes the north-west control room to be gassed, leaving the map looking as follows: