It is year 2551. The Nostalgia for Infinity, captain John Brannigan’s ship, is cruising towards Resurgam, a planet considered a backwater on the edge of colonized human space. Some of the scientists aboard the ship will lead a team excavating the remains of the Amarantin, a long-dead, 900,000-year-old civilization that once existed on Resurgam. It is suspected that the entire Amarantin race achieved a much higher level of technological sophistication than was previously known. As the Nostalgia for Infinity approaches Cerberus, a planet near Resurgam, the ship’s defenses detect the presence of a highly hostile alien ship. Captain Brannigan is ready to fight and has stationed the ship behind a shield that seems to have been previously built by the Amarantin. Nostalgia for Infinity instruments depict space battle scenarios in 2D. In particular, the shield is depicted as a rectangular region with r rows and c columns. Each cell in a shield can be either active (represented by ‘#’) or disabled (represented by ‘.’). It is said that a shield is breached iff there is a connected sequence of disabled cells between the first and the last rows of the shield. Two cells are connected iff they are adjacent vertically or horizontally. For example, the figure below depicts two shields of r = 4 rows and c = 5 columns (numbers added for clarity: on top, they indicate the column number; on the right, they indicate the row number). The shield on the left is not breached, while the one on the right is breached. 12345 ##..# 1 ..### 2 #.#.. 3 ..##. 4 12345 ##..# 1 ...## 2 #.#.. 3 ..##. 4 If it is assumed that the first row of a shield is facing north, then the alien ship is located north of the first row and it fires in the south direction; also, the Nostalgia for Infinity is located south of the last row and it fires in the north direction. In this way, the shield is a barrier between the two enemy ships. The effect of a shot fired from a ship is to disable the first active cell it encounters in the shield, if any. Shots are indicated by the column on which they are fired and always follow a vertical path. For example, if the aliens shoot at either column 1, 2, 3, 4 the left shield depicted above would be breached. The right shield corresponds to the result of shooting column 3. You, as the ship’s new gunnery officer, have been assigned with the task of determining whether or not, during battle, the shield is breached. If so, captain Brannigan would also like to know when and who breached the shield first. Input The input consists of several test cases. The first line of a test case contains three blank-separated integers r, c, and s (1 ≤ r ≤ 1000, 1 ≤ c ≤ 1000, 0 ≤ s ≤ 10000) indicating, respectively, the number of rows and columns in the shield, and the number of shots during the battle. Each of the next r lines contain c characters ‘#’ or ‘.’. The next s lines contain each an integer a (1 ≤ |a| ≤ c) indicating a shot fired at column |a| of the shield: if a > 0 then it is an alien shot; otherwise it is Nostalgia for Infinity shot. Output For each test case, output exactly one line:
2/2 • If the shield was breached before any shot was fired, then output ‘0’. • If the shield was never breached during the battle, then output ‘X’. • If the shield was first breached by the Nostalgia for Infinity during the battle at shot k (counting from 1), then output the number −k. • If the shield was first breached by the aliens during the battle at shot k (counting from 1), then output the number k. Sample Input 222 .# .. 1 1 232 ##. .## 2 -2 232 ##. .## -2 2 211 #
-1 Sample Output 0 -2 2 X