{"raw_statement":[{"iden":"statement","content":"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.\n\nThe 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.\n\nThe heroes started their way at sundown and want to reach the tunnel entrance. Can this goal be achieved?\n\nThe 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.\n\nNext 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.\n\nIn 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).\n\n"},{"iden":"input","content":"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."},{"iden":"output","content":"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)."},{"iden":"examples","content":"Input2 6 31 1 1 6F....FFF..FFOutputHello, Deimos!Input2 6 22 1 2 6FF..FFF....FOutputDire victory"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, m, v \\in \\mathbb{Z}^+ $ denote the dimensions of the grid and the maximum number of moves per day/night.  \nLet $ (x_0, y_0), (x_1, y_1) \\in \\{1, \\dots, n\\} \\times \\{1, \\dots, m\\} $ be the starting and target coordinates.  \nLet $ G = (V, E) $ be a grid graph of size $ n \\times m $, where each cell $ (i, j) $ is a vertex.  \nDefine a binary grid $ F \\in \\{0,1\\}^{n \\times m} $:  \n- $ F[i][j] = 1 $ if cell $ (i,j) $ is forest,  \n- $ F[i][j] = 0 $ otherwise.  \n\n**Constraints**  \n1. $ 1 \\leq n, m, v \\leq 1000 $  \n2. $ 1 \\leq x_0, x_1 \\leq n $, $ 1 \\leq y_0, y_1 \\leq m $  \n3. Movement is allowed between adjacent cells (up/down/left/right).  \n4. **Daytime moves** (even-numbered moves: 2nd, 4th, ...) must be between forest cells: $ F[i][j] = 1 \\land F[i'][j'] = 1 $.  \n5. **Nighttime moves** (odd-numbered moves: 1st, 3rd, ...) have no terrain restriction.  \n6. Exactly $ v $ moves are allowed per full day-night cycle (i.e., per two phases).  \n7. The journey begins at sundown (first move is nighttime).  \n\n**Objective**  \nDetermine if there exists a path from $ (x_0, y_0) $ to $ (x_1, y_1) $ such that:  \n- The sequence of moves alternates between nighttime (any terrain) and daytime (forest-to-forest),  \n- Each phase (day or night) contains at most $ v $ moves,  \n- The entire path is composed of consecutive phases starting with nighttime.  \n\nOutput \"Hello, Deimos!\" if such a path exists; otherwise, output \"Dire victory\".","simple_statement":"Heroes start at night. They can move up to v steps per day/night.  \nBy day: can only move between forest cells.  \nBy night: can move anywhere.  \nCan they reach the tunnel without being detected?","has_page_source":false}