Move or Block!

Time limit1sMemory limit1024 MB

Summary

Given a line of N cells with walls and one piece, find the winner when players alternate moving the piece or placing a wall, with Mingyu first.

Level: Medium6 of 10
Topics: Game theory, Math
Solved: No attempts yet

Problem

The game "Move or Block!" is a two-player board game played on a straight board of $N$ cells. Each cell is either empty or has a wall. One piece is placed on an empty cell to start the game, and the two players take turns.

On their turn, a player loses if every cell adjacent to the piece has a wall. Otherwise, they choose one of the following actions, play it once, and pass the turn.

Move the piece to one of the adjacent empty cells.
Choose an empty cell and build a wall on it.

Mingyu and Yunsu play this game. Given the initial board, print the winner when both players play optimally. Mingyu moves first.

Input

The first line contains the board size $N$ .

The second line contains a string of length $N$ that describes the initial board. The string consists only of the characters ., X, and O. They mean an empty cell, a cell with a wall, and the cell with the piece, respectively.

Output

If Mingyu wins, print mingyu. If Yunsu wins, print yunsu. If the game never ends, print draw.

Constraints

$2 \le N \le 1\,000\,000$
$N$ is an integer.
There is exactly one piece on the board.
The input never has a piece whose adjacent cells all have walls.

Examples2

Example 1
Input
```
3
.O.
```
Expected output
```
yunsu
```
Example 2
Input
```
3
O.X
```
Expected output
```
mingyu
```