Road game with a sheet of paper
Limits: 2 sec., 256 MiB
This statement was translated automatically from Ukrainian.
The road to the mountains is long, so Zenyk and Marichka decided to play another game. Fortunately, they have a grid paper of size \(n\) by \(m\) cells and markers of different colors.
Rules of the new game are as follows:
Players take turns. Zenyk moves first.
In one turn, a player can draw exactly one vertical or horizontal straight line. Each line goes strictly along the grid lines of the sheet, but cannot go along the edge of the sheet.
Each player draws lines with their own unique color.
On their turn, a player receives a number of points equal to the number of new rectangles that can be formed using the lines of their color and the borders of the sheet.
A player cannot draw their line on top of an already drawn line.
The game ends when a player cannot make a move. That is, exactly \((n-1) + (m-1)\) moves can be made on an \(n\) by \(m\) sheet.
The winner is the one who scores more points.
Can you predict how the game will end if both players play optimally?
Input
The single line contains two integers \(n\) and \(m\) — the dimensions of the sheet.
Output
If Zenyk wins, output Zenyk, if Marichka wins —
Marichka. In case of a draw, output Draw.
Constraints
\(1 \le n,m \le 10^{9}\).
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| 2 3 | Zenyk |
| Input (stdin) | Output (stdout) |
|---|---|
| 1 1 | Draw |
| Input (stdin) | Output (stdout) |
|---|---|
| 4 6 | Zenyk |
Notes
In the first example, players can draw 3 lines. Let us show a possible course of events in the game. On his turn, Zenyk can draw a horizontal line, getting 2 points. Marichka will have 2 moves, both of which bring 2 points each. After that, regardless of Marichka’s actions, Zenyk will draw a vertical line getting 6 points and win the game.
In the second example, neither player can make a move, so the game will end in a draw.
Submit a solution
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|