Want to try solving this problem? You can submit your code online if you log in or register.

Earth is the only known planet to harbour life. There are many planets out there that have some of the things needed for life. Let me introduce you to one in particular, Kepler-442b.

Discovered early last year, it is the most Earth-like planet we know about. Although a little bigger than Earth, the conditions are almost perfect for life. Almost. It's missing liquid water.

The Australian Institute for Observing the Cosmos has just sent out a massive probe full of water to crash into the planet. The water will spill out on impact to plant the metaphorical seeds of life, but the shock of the impact will also cause a fissure to form elsewhere, which will spill lava.

Scientists have selected a small, empty desert for the probe which can be represented by a grid of squares with R rows and C columns. They happen to know exactly which square the probe will crash in and also the square where the fissure will form.

The square where the probe crashes is instantly covered in water, while the square where the fissure forms is instantly covered in lava. As time passes, the water and lava spread out over the desert in a simple way. Each minute:

- Any empty square that shares a side with a square covered in water will also become covered in water.
- Any empty square that shares a side with a square covered in lava will also become covered in lava.
- Any empty square that shares a side with both a square covered in lava and one covered in water will form into rocky mountains (probably made of obsidian), over which neither water nor lava will flow.

You have been tasked with helping the scientists figure out what the desert will look like after the water and lava finish flowing. You will be asked Q questions, for each of which you must answer whether a given square will be covered in water, lava or mountains.

The first line of input will contain six integers (separated by spaces), R, C, r_{p}, c_{p}, r_{f} and c_{f}.

- R and C denote the number of rows and columns in the grid respectively. Rows are labelled from 1 to R (from top to bottom) and columns are labelled from 1 to C (from left to right).
- The probe will crash in the square in the r
_{p}th row and c_{p}th column. - The fissure will form in a different square in the r
_{f}th row and c_{f}th column.

`LAVA`if the square is covered in lava.`WATER`if the square is covered in water.`MOUNTAINS`if the square is covered in mountains.

4 7 2 5 3 2 3 1 1 1 3 3 6

LAVA MOUNTAINS WATER

2 3 1 1 1 2 2 1 1 2 2

WATER LAVA

For all subtasks, 1 ≤ R, C, Q ≤ 100000, 1 ≤ r_{p}, r_{f}, r_{i} ≤ R and 1 ≤ c_{p}, c_{f}, c_{i} ≤ C.
Additionally, the fissure will always form in a different square to the probe's landing spot.

- For Subtask 1 (20 marks), r
_{p}= 1, c_{p}= 1, r_{f}= R and c_{f}= C. That is, if your program correctly solves the problem when the probe is always in the top-left corner and the fissure is always in the bottom-right corner, you will receive 20 marks. - For Subtask 2 (15 marks), R = 1.
- For Subtask 3 (25 marks), R, C ≤ 50.
- For Subtask 4 (20 marks), R, C ≤ 1000.
- For Subtask 5 (20 marks), there are no further constraints.

Privacy
statement

© Australian Mathematics Trust 2001-2019

Page generated: 24 May 2019, 4:02am AEST