# Problem: Probe

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

## Probe

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:

• 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.
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.

### Input

The first line of input will contain six integers (separated by spaces), R, C, rp, cp, rf and cf.

• 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 rpth row and cpth column.
• The fissure will form in a different square in the rfth row and cfth column.
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.

### Output

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:
• LAVA if the square is covered in lava.
• WATER if the square is covered in water.
• MOUNTAINS if the square is covered in mountains.
You know for a fact that every square will eventually be covered by one of the above.

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

### Explanation

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.

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.

• For Subtask 1 (20 marks), rp = 1, cp = 1, rf = R and cf = 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