Santa's New Sled

1000ms

262144K

Description:

Santa is delivering presents and has one last stop tonight at the coordinates $$$(x, y)$$$ - we are representing the world as a 2D plane for simplicity. He takes a quick break at the coordinates $$$(0,0)$$$ where he decides to update the steering software on his sled. Unfortunately, the update has messed up the steering software and Santa finds out that the sled will only follow the directions in the order specified by a string $$$s$$$ which consists of the characters U, L, D, and R.

The character U means to go up so from position $$$(a, b)$$$ go to $$$(a, b + 1)$$$.
The character L means to go left so from position $$$(a, b)$$$ go to $$$(a - 1, b)$$$.
The character D means to go down so from position $$$(a, b)$$$ go to $$$(a, b - 1)$$$.
The character R means to go right so from position $$$(a, b)$$$ go to $$$(a + 1, b)$$$.

Given that the sled will perform these operations from $$$s$$$ left to right and repeat that an infinite number of times, figure out if Santa will ever end up reaching his destination at $$$(x, y)$$$.

Input:

The first line of input contains two space-separated integers $$$x$$$ and $$$y$$$ representing the coordinates that Santa is trying to get to ($$$-10^{18} \leq x, y \leq 10^{18}$$$).

The second and last line of input contains a string $$$s$$$ ($$$1 \leq |s| \leq 10^{5}$$$) representing the series of directions that Santa's sled will go ($$$s$$$ will only contain the characters U, L, D, and R).

Output:

Output Yes if the sled will ever reach the coordinates $$$(x, y)$$$ and No otherwise.

Sample Input:

2 2
UR

Sample Output:

Yes

Sample Input:

1 2
RU

Sample Output:

No

Sample Input:

-1 1000000000000000000
LRRLU

Sample Output:

Yes

Note:

In example 1, after going through UR once, Santa is at (1,1) and then going through that again gets Santa at (2,2) which is the goal.

Info

Provider CodeForces Gym

Origin UTPC Contest 10-29-21 Div. 2 (Beginner)

Code GYM103380G