406737: GYM102512 F Opposition

This is an interactive problem. You have to use a flush operation right after printing each line. For example, in C++ you should use the function fflush(stdout), in Java — System.out.flush(), in Pascal — flush(output) and in Python — sys.stdout.flush().

Nibutani and Dekomori are fighting with each other again. This time, their battle is about filling blanks in a string.

A string $$$S$$$ is written on the blackboard, where each character is either L, O, V, E or ?. Nibutani and Dekomori takes turn replacing one of the question marks in the string with one of the letters L, O, V or E. Nibutani plays first. The game ends when all question marks are replaced.

Nibutani wants to maximize the number of substrings that is equal to LOVE while Dekomori wants to minimize the number of such substrings. A substring is defined as a string obtained by removing several (possibly zero) characters from the beginning and the end of the original string.

You, as our main protagonist Yuuta, are tired of their endless battles. Thus, you want to write a program that will help them play the game optimally. Can you perform this task?

The first line of input contains the initial string $$$S$$$ ($$$1 \le |S| \le 200000$$$). The next line contains a single integer $$$T$$$ ($$$1 \le T \le 2$$$), where $$$T = 1$$$ means that you are playing as Nibutani while $$$T = 2$$$ means that you are playing as Dekomori.

Whenever it is your turn, you should output an integer $$$p$$$ ($$$1 \le p \le |s|$$$) and a character $$$c$$$ ($$$c \in \{L, O, V, E\}$$$), separated with a space. This denotes that you will place the character $$$c$$$ at position $$$p$$$. The character at position $$$p$$$ must be a question mark before you replace it.

Whenever it is the other player's turn, you should read an integer and a character (given in the same format as your output), denoting the other player's move.

Your program should terminate when all question marks are replaced.

Remember to flush the output after outputting every line.

Your solution will be accepted if the result of the game is at least as good as the result when both sides play optimally.

Subtask 1 (40 points): $$$|S| \le 3000$$$

Subtask 2 (30 points): $$$T = 1$$$

Subtask 3 (30 points): $$$T = 2$$$

L?VEE?O??

1

6 L

8 L

2 O

9 E

Initially, the string is L?VEE?O??. You play as Nibutani.

After your first move, the string is LOVEE?O??.

After Dekomori's first move, the string is LOVEELO??.

After your second move, the string is LOVEELO?E.

After Dekomori's second move, the string is LOVEELOLE.

After the game, the number of substrings LOVE in the string is $$$1$$$. It can be proven that this is the best possible result with optimal play from both sides.