Problem A
The Last Laugh

The self-proclaimed “super duper party pony” and amusement factory owner Cheese Sandwich has lost his laugh, and it’s up to his longtime pal Pinkie Pie to get it back.

Figure 1: Illustration by Kyle Coate.

By now, Pinkie Pie has pulled out all the stops to get her “partier” in crime to laugh, all to no avail. As a last resort, she has decided to whip out her secret weapon: the game of chicken, involving Cheese Sandwich’s childhood toy, Boneless the rubber chicken!

To make things funnier, the game will involve four of them. Here’s how the game is played:

1. Four chickens are laid out in a row, at different integer positions $X_1$, $X_2$, $X_3$ and $X_4$. This row can be viewed as a number line where zero is the center, smaller numbers are farther to the left and larger numbers are farther to the right; at any point in the game, chickens can be placed only on integer coordinates on this line, and no two chickens can ever simultaneously occupy the same position.

2. Players alternate turns. During a player’s turn, he or she first needs to remove either the leftmost or rightmost chicken in the row. This chicken must then be placed between the leftmost and the rightmost of the remaining chickens. This player is now called chicken; if the other player was already called chicken, the other player is no longer called chicken.

3. The game is over when no more valid moves can be played. (If at least one valid move exists, a move must be made.) The player who is called chicken at this point is the loser, and the other player is the winner.

Pinkie Pie’s game plan is thus: she will ham up her skills in this game, saying that she has won every game she has played since she was a filly, and then purposely lose to Cheese Sandwich, who has never played this game in his life. This unexpected turn of events is sure to evoke laughter from even the most agelastic of ponies!

Here is the problem. Pinkie Pie is so good that she does not know how to lose. You need to tell her what moves to make such that she definitely loses. Obviously, she still needs to play the game properly—“losing” by not following the rules is not exactly convincing.

Interaction

First, your program should read four integers $X_1$, $X_2$, $X_3$ and $X_4$ ($-200\, 000 \leq X_ i \leq 200\, 000$; $X_ i < X_{i+1}$ for all positive integers $i < 4$), the positions of the four chickens on a single line from standard input.

Then, your program writes a single line containing a single integer $1$ or $2$ to the standard output, denoting whether Pinkie Pie should go first or second, respectively.

Then, we repeat the following process:

• If it is Pinkie Pie’s turn:

  • Your program writes a single line to the standard output in either format:

    • $\texttt{D}$, meaning that there are no more moves to be made. Your program should terminate immediately after this.

    • $\texttt{M}\: x\: y$ ($-200\, 000 \leq x, y \leq 200\, 000$), meaning that Pinkie should move the chicken at position $x$ to position $y$.

• If it is Cheese Sandwich’s turn:

  • Your program should read from the standard input either:

    • $\texttt{D}$, meaning that there are no more moves to be made. Your program should terminate immediately after this.

    • $\texttt{M}\: x\: y$ ($-200\, 000 \leq x, y \leq 200\, 000$), meaning that Cheese moved the chicken at position $x$ to position $y$.

After making a move or declaring that no more moves can be made, do not forget to output end of line and flush the output. To do this, use:

• fflush(stdout) or cout.flush() in C++;

• System.out.flush() in Java;

• stdout.flush() in Python;

• see documentation for other languages.

It is guaranteed that at least one valid move can be made at the beginning.

The input will be such that, regardless of how the game is played, it will end within $400\, 000$ turns.

You can assume that the moves Cheese Sandwich makes are always valid, and he will declare the game over if and only if there are no more moves to be made. Likewise, all of Pinkie Pie’s moves must be valid, and Pinkie Pie must lose the game for your solution to be correct.

Sample interaction