AIOC Banner

Problem: Probe

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


Time Limit: 1 second
Memory Limit: 1 GB
Input File: probein.txt
Output File: probeout.txt

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:

Lava and water never flow outside the desert.

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, rp, cp, rf and cf.

The second line will contain a single integer Q, the number of questions that will be asked. Q lines follow, the ith of which contains two integers ri and ci.


You should output Q lines. The ith line should contain a single word describing the state of the square in the rith row and cith column: You know for a fact that every square will eventually be covered by one of the above.

Sample Input 1

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

Sample Output 1


Sample Input 2

2 3 1 1 1 2
1 1
2 2

Sample Output 2



The two diagrams above show the state of the desert after the water and lava have finished flowing. The fissure and the probe have been marked on the map for clarity. Dark grey squares are covered in lava while light grey squares are covered in water. The striped squares are mountains.

Subtasks & Constraints

For all subtasks, 1 ≤ R, C, Q ≤ 100000, 1 ≤ rp, rf, ri ≤ R and 1 ≤ cp, cf, ci ≤ C. Additionally, the fissure will always form in a different square to the probe's landing spot.


Privacy statement
© Australian Mathematics Trust 2001-2023

Page generated:  3 June 2023,  2:41pm AEST