Stone Game

Time limit1sMemory limit1024 MB

Summary

Given a 1 by N board of black, white, and empty cells, decide whether the first player (black) wins, loses, or the game is a draw under optimal play.

Level: Medium7 of 10
Topics: Game theory, Greedy, Implementation
Solved: No attempts yet

Problem

A $1 \times N$ board has an even number of cells holding black and white stones, placed alternately in equal numbers.

The game is played with these rules.

The first player and the second player take turns. The first player plays black and the second player plays white.
On a turn, a player picks one of their own stones and moves it left or right any number of cells. Passing is not allowed, so the stone must move. A stone cannot jump over another stone or move onto a cell that already holds a stone.
A player who cannot move a stone on their turn loses.

With both players playing optimally, determine who wins. If the game is still undecided after $10^{100}$ turns, it is a draw.

Input

The first line contains a string $S$ describing the board state. $(2 \le \vert S\vert \le 5\,000)$

$S$ consists only of B, W, and .. B is a black stone, W is a white stone, and . is an empty cell. At least one black stone and one white stone are guaranteed to exist.

Output

Print Win if the first player wins, or Lose if the first player loses. If the game is still undecided after $10^{100}$ turns, print Draw.

Examples2

Example 1
Input
```
W.BWB
```
Expected output
```
Win
```
Example 2
Input
```
BWBW..
```
Expected output
```
Lose
```