Robot#1493
The Mars rover "Perseverance" roams freely across the Martian surface, transmitting details of its journey back to Earth.
"Perseverance" uses a coordinate system where the origin matches its starting position, and the axis points to the direction it faced upon landing.
The rover moves as follows: after landing, it travels forward by an integer number of centimeters between and 10^6, then turns degrees either left or right, then moves forward again by an integer between and 10^6, and again turns degrees either left or right, and so on. After completing the last segment (which is also between and 10^6 centimeters long), it stops and transmits the route description back to Earth.
The Control Center received the following message from "Perseverance": "I made moves. I report n-1 turns: sequence of turns. As a result, I am at coordinates (, ). I like it here. End of communication."
At this point, the creators realized they had forgotten to program the rover to report the lengths of its moves!
They are interested in any possible route that "Perseverance" could have taken according to the given data. Help them.
The first line contains three integers , , (-100000 \le x, y \le 100000; 1 \le n \le 100000) — the final coordinates of "Perseverance" and the number of moves it made.
The second line is a string of length n-1 consisting of characters "L" and "R", representing the sequence of turns made by the rover. The symbol "L" means a degree turn to the left, and "R" means a degree turn to the right.
If the information is contradictory and the rover could not have moved in such a way, output "Impossible".
Otherwise, output integers between and 10^6 — the lengths of each movement in centimeters so that, following the given turns, "Perseverance" finishes at point (, ). The numbers should be separated by spaces and/or newlines.
Example 1