401458: GYM100460 D Make It Through Your Way

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

D. Make It Through Your Waytime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Desmond and Thorwald decided to sneak into Enia and surprisingly attack Deimos. But Deimos is a powerful magician, and it's not easy to walk around the country with hostile intentions towards him while remaining undetected. Deimos has eyes and ears everywhere... But Desmond is still a half-elf, so a cover of night or forest will provide the heroes a suitable protection and hide them from the enemy gaze.

The terrain between our heroes and the entrance of the tunnel leading to Enia can be divided into equal squares, thereby obtaining a rectangular grid of size n × m. Some cells are occupied by the forest. Each night and day travellers can move from one cell to another at most v times. All moves during a daytime must be performed from a forest cell to another forest cell. During a nighttime the heroes can move regardless of the terrain.

The heroes started their way at sundown and want to reach the tunnel entrance. Can this goal be achieved?

Input

The first line contains three integers separated by the spaces: n, m and v (1 ≤ n, m, v ≤ 1000) — the sizes of the terrain map and the heroes' speed. The second line contains 4 integers separated by the spaces: x0, y0, x1 and y1 (1 ≤ x0, x1 ≤ n, 1 ≤ y0, y1 ≤ m) — the coordinates of the cell where the heroes start and the coordinates of the tunnel entrance, correspondingly. The first coordinate denotes the number of row on the map, and the second coordinate denotes the number of column.

Next n lines contain m symbols '.' or 'F' each. 'F' means the corresponding cell is occupied by forest, and '.' means there is no forest in this cell.

Output

In the only line output «Hello, Deimos!» (without quotes) if the heroes can reach the tunnel entrance while remaining undetected. Otherwise, output in the only line «Dire victory» (without quotes).

ExamplesInput
2 6 3
1 1 1 6
F....F
FF..FF
Output
Hello, Deimos!
Input
2 6 2
2 1 2 6
FF..FF
F....F
Output
Dire victory

加入题单

上一题 下一题 算法标签: