Problem Description

L Game is a two-player board game played on a $4 \times 4$ square board.

There are two types of pieces:

• L-shaped piece: size $4$, one for each player;
• neutral piece: size $1$, two in total, neutral.

At any time, each cell on the board can have at most one piece on it.

The players take turns. One legal move is: first move your own L-shaped piece to a legal position different from its current position, then move at most one neutral piece.

If a player cannot make a legal move, that player loses.

Let the player operating the grid-marked L-shaped piece be A, and the player operating the hatched one be B.

If the position is one of the three positions above and A moves first, then A can, and can only, move their own L-shaped piece to one of the other two positions. After that, A may move one of the neutral pieces to an empty cell, or choose not to move a neutral piece. Therefore, A has a total of $2 \times (6 + 6 + 1)$ possible moves.

If the position is the one below and A moves first, then A loses because they cannot move their L-shaped piece, and B wins.

A "winning move" means: a move such that after the first player makes it, the first player has a forced win strategy. A "losing position" means: no matter what the first player does, the second player has a forced win strategy. A "draw position" means: the first player has no winning move and it is not a losing position.

Although the board is small, L Game has more than $18 \thinspace 000$ possible positions; and at the same time, the first player may have up to $195$ possible moves, but among them there is only one winning move.

Given a position, find one winning move, or determine that the position is a losing position or a draw position. If there are multiple winning moves, output any one of them.

Input Format

Four lines, each with four characters, describing the board.

• # indicates the first player's piece position;
• * indicates the second player's piece position;
• x indicates the neutral piece position;
• . indicates an empty cell.

Output Format

• If there is a winning move, output the position after the move, in the same format as the input. Note that # still denotes the player who was first before the move, and * similarly.

• Otherwise, output the string No winning move on the first line.

  • If it is a draw position, output the string Draw on the second line;
  • If it is a losing position, output the string Losing on the second line.

Note: although the Special Judge ignores trailing newlines at the end of lines and the final newline at the end of the output, please do not output more than $64$ characters in total, otherwise you will be judged as Wrong Answer.

.*** 
#*.x 
###. 
x... 

.*** 
x*#x 
###. 
.... 

...x 
###. 
#*** 
x..* 

No winning move 
Draw 

.### 
x#*x 
***. 
.... 

No winning move 
Losing 

Hint

Constraints

It is guaranteed that the given position is legal.

Hint

BalticOI 2002 Day2 B.

You can score on testdata without winning moves if and only if you have passed at least half of the testdata with winning moves. (Note: the original statement says "at least one", but here we use the wording from the original editorial, i.e. "half".)

Due to the configuration of the custom scoring script parameters, evaluation statuses other than AC, WA, TLE, and MLE are not shown for now. If you get any other evaluation status, you will get UKE.

Subtask #0 is the samples; Subtask #1 is the full data.

Translated by ChatGPT 5