VK Cup 2016 - Qualification Round 1
D
Running with Obstacles
Codeforces
1600
原题
← C→
翻译中…

A sportsman starts from point $*x*_{*start*} = 0$ and runs to point with coordinate $*x*_{*finish*} = *m*$ (on a straight line). Also, the sportsman can jump — to jump, he should first take a run of length of not less than $*s*$ meters (in this case for these $*s*$ meters his path should have no obstacles), and after that he can jump over a length of not more than $*d*$ meters. Running and jumping is permitted only in the direction from left to right. He can start andfinish a jump only at the points with integer coordinates in which there are no obstacles. To overcome some obstacle, it is necessary to land at a point which is strictly to the right of this obstacle.

翻译中…

On the way of an athlete are $*n*$ obstacles at coordinates $*x*_{1}, *x*_{2}, ..., *x*_{*n*}$. He cannot go over the obstacles, he can only jump over them. Your task is to determine whether the athlete will be able to get to the finish point.

翻译中…

Input

翻译中…

The first line of the input containsd four integers $*n*$, $*m*$, $*s*$ and $*d*$ ($1 ≤ *n* ≤ 200 000$, $2 ≤ *m* ≤ 10^{9}$, $1 ≤ *s*, *d* ≤ 10^{9}$) — the number of obstacles on the runner's way, the coordinate of the finishing point, the length of running before the jump and the maximum length of the jump, correspondingly.

翻译中…

The second line contains a sequence of $*n*$ integers $*a*_{1}, *a*_{2}, ..., *a*_{*n*}$ ($1 ≤ *a*_{*i*} ≤ *m* - 1$) — the coordinates of the obstacles. It is guaranteed that the starting and finishing point have no obstacles, also no point can have more than one obstacle, The coordinates of the obstacles are given in an arbitrary order.

翻译中…

Output

翻译中…

If the runner cannot reach the finishing point, print in the first line of the output "IMPOSSIBLE" (without the quotes).

翻译中…

If the athlete can get from start to finish, print any way to do this in the following format:

翻译中…
  • print a line of form "RUN X>" (where "X" should be a positive integer), if the athlete should run for "X" more meters;
  • print a line of form "JUMP Y" (where "Y" should be a positive integer), if the sportsman starts a jump and should remain in air for "Y" more meters.
翻译中…

All commands "RUN" and "JUMP" should strictly alternate, starting with "RUN", besides, they should be printed chronologically. It is not allowed to jump over the finishing point but it is allowed to land there after a jump. The athlete should stop as soon as he reaches finish.

翻译中…

样例

Input #1
3 10 1 3
3 4 7
Output #1
RUN 2
JUMP 3
RUN 1
JUMP 2
RUN 2
InputCopy OutputCopy
Input #2
2 9 2 3
6 4
Output #2
IMPOSSIBLE
InputCopy OutputCopy
题目信息
题号
637D
时间限制
2 s
内存限制
256 MB
标签
*special
数据结构
动态规划
贪心

题面与样例版权归 Codeforces 及出题人所有;中文翻译由 AI 生成(CI 管线),如有出入请以原文为准。