410657: GYM104069 I Irritating Carlinhos

Thiago is a very naughty boy. He spends all day playing pranks around the department of computing. On the other hand, Carlinhos feels that he must assume his professor role and teach Thiago a lesson. Fearing the punishment, Thiago runs away at the slightest mention of Carlinhos's name. On the other hand, as Carlinhos is one of the greatest marathon runners in Brazil, he doesn't mind running after him. At some point, Thiago will get tired of running away, and justice will be done.

In this problem, we will consider that Thiago and Carlinhos are 2D points in the plane with coordinates $$$(t_x, t_y)$$$ and $$$(c_x, c_y)$$$, respectively. A sequence of movements can be represented by a string containing the letters U (Up), D (Down), R (Right), and L (Left) consisting of the follwing movements:

• U: $$$(x, y) \to (x, y + 1);$$$
• D: $$$(x, y) \to (x, y - 1);$$$
• R: $$$(x, y) \to (x + 1, y);$$$
• L: $$$(x, y) \to (x - 1, y).$$$

Given Thiago and Carlinhos initial positions (both distinct) and their sequence of movements (of equal length), determine if Thiago will be punished by Carlinhos. Carlinhos manages to punish Thiago if, at any moment, they share the same position. The movements occur alternatively, but since Thiago is always vigilant, he moves first.

The first line contains four integers separated by spaces $$$t_x, t_y, c_x, c_y (-10^5 \leq t_x, t_y, c_x, c_y \leq 10^5)$$$ the initial coordinates in the axis $$$x$$$ and $$$y$$$ of Thiago and Carlinhos, respectively. It's guaranteed that the coordinates are different.

The next two lines contains one string each $$$s, t (1 \leq |s| = |t| \leq 2 \cdot 10^5)$$$, consisting only of U, D, L, and R, the movements of Thiago and Carlinhos, respectively.

Print the string "Rodou!" (without quotes) if Thiago was caught by Carlinhos or "Quase!" (without quotes) otherwise.

0 1 0 0
UU
UU

Quase!

2 0 0 0
L
R

Rodou!

2 2 0 0
DLDL
RURU

Rodou!

Notice that in the first test case, the following moves sequence occurs:

• Thiago: $$$(0, 1) \to (0, 2)$$$
• Carlinhos: $$$(0, 0) \to (0, 1)$$$
• Thiago: $$$(0, 2) \to (0, 3)$$$
• Carlinhos: $$$(0, 1) \to (0, 2)$$$

Therefore, they never share in the same position.

In the second test case, the following moves sequence occurs:

• Thiago: $$$(2, 0) \to (1, 0)$$$
• Carlinhos: $$$(0, 0) \to (1, 0)$$$

Therefore, Thiago was caught in the last move.