#P8658. LOL Game Strategy
LOL Game Strategy
LOL Game Strategy
In this game, two players take turns to fill a row of n blank cells with one of the letters L
or O
. The rules are as follows:
- On a player's turn, they may choose any empty cell and fill it with either
L
orO
. - The game ends immediately when, after a move, there exists a contiguous triple of cells that form the string LOL. Formally, if there exists an index i (1 ≤ i ≤ n-2) such that the cells satisfy $$s_i = L,\; s_{i+1} = O,\; s_{i+2} = L,$$ then the player who just moved wins.
- If all cells are filled and no such triple appears, the game is a draw.
Observing his previous losses, Xiao Ming wonders if there is a winning strategy. It turns out that if n is at least 3, the first player can always force a win, while if n is less than 3, it is impossible for either player to form the string LOL, resulting in a draw.
Your task is to help Xiao Ming determine the outcome of the game, assuming both players play optimally. Output Win
if the first player can force a win, and Draw
otherwise.
inputFormat
The input consists of a single integer n (1 ≤ n ≤ 109), representing the number of cells drawn in a row.
outputFormat
Output a single word: Win
if the first player can force a win under optimal play (this is the case when n ≥ 3), or Draw
if no win is possible (when n < 3).
sample
1
Draw