Apple Sharing

Call the empty string a stable state. For a nonempty string, scan its characters from left to right while maintaining a height $h$, initially $0$.

When reading L, increase $h$ by $1$. When reading R, decrease $h$ by $1$. Reading M does not change $h$.

Call the string stable if all of the following conditions hold.

• After every prefix, $h$ is nonnegative.
• Whenever an M is read, $h$ is positive.
• After the whole string is read, $h=0$.

The stable states are exactly the losing positions for the player whose turn it is.

First, consider a move from a stable state. Suppose the player chooses position $i$ marked L or M and takes the chosen apple together with everything to its left. The remaining string is $S_{i+1}\cdots S_N$. For this suffix to be stable, the height after position $$ in the original string must be . This is impossible: if , that height is positive, and if , stability also requires that height to be positive.

The case where the player chooses a position marked R or M and takes everything to its right is symmetric. For the remaining prefix to be stable, the height immediately before the chosen position would have to be $0$. An R at height $0$ would make the height negative, while an M at height $0$ is forbidden by the definition of stability.

Now consider a state that is not stable. Scan from the left and find the first position that violates one of the local stability conditions. If such a position exists, its mark is R or M at height $0$. The prefix before that position is stable. By choosing this apple and taking it together with everything to its right, the player leaves exactly that stable prefix.

Otherwise all local conditions hold, but the final height is positive. Read the string from right to left while swapping the roles of L and R, and apply the same argument. The total height has the opposite sign, so a first local violation must exist. In the original string, that position is marked L or M; taking it together with everything to its left leaves a stable suffix.

Therefore every move from a stable state goes to a non-stable state, while every non-stable state has a move to a stable state. Since the empty string is losing for the player to move, induction shows that stable states are exactly the losing states.

For each test case, scan the string once and check the three conditions above. If the state is stable, Lulu, the first player, loses, so print Terra. Otherwise print Lulu.

The time complexity is $O(N)$ and the extra space complexity is $O(1)$ per test case. Over the whole input, the running time is $O(\sum N)$.

Solution written by GPT5.6