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.


-----Examples-----
Input
3 10 1 3
3 4 7

Output
RUN 2
JUMP 3
RUN 1
JUMP 2
RUN 2

Input
2 9 2 3
6 4

Output
IMPOSSIBLE

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Data structures

Greedy algorithms


Solutions:
import sys
input = sys.stdin.readline

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def lcm(a, b):
	return a * b / gcd(a, b)

def main():
	(n, m, s, d) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	curr = 0
	f = 0
	ans = []
	obs = []
	obs.append([a[0], 0])
	j = 0
	for i in range(1, n):
		if a[i] - a[i - 1] - 2 < s:
			obs[j][1] += a[i] - a[i - 1]
		else:
			obs.append([a[i], 0])
			j += 1
	curr = 0
	obs.append([float('inf'), -1])
	i = 0
	while 1:
		if obs[i][1] == -1:
			break
		if obs[i][0] - 1 - curr >= s:
			ind = -1
			for j in range(i, len(obs) - 1):
				if obs[j][0] - (obs[i][0] - 1) + obs[j][1] + 1 <= d:
					ind = j
				else:
					break
			if ind < i:
				print('IMPOSSIBLE')
				return
			else:
				ans.append(['RUN', obs[i][0] - 1 - curr])
				ans.append(['JUMP', obs[ind][0] - (obs[i][0] - 1) + obs[ind][1] + 1])
				curr = obs[ind][0] + obs[ind][1] + 1
				i = ind + 1
		else:
			print('IMPOSSIBLE')
			return
	if m - curr:
		ans.append(['RUN', m - curr])
	for i in ans:
		print(*i)
	return
main()


(n, m, s, d) = [int(i) for i in input().split()]
A = [-1] + sorted([int(i) for i in input().split()]) + [m + 1]
ans_size = 2 * 10 ** 5
ans = [0 for i in range(4 * ans_size)]

def obstacle():
	run = -1
	jump = -1
	top = 0
	for i in range(1, n + 1):
		if s + 2 <= A[i] - A[i - 1]:
			if jump != -1:
				if A[i - 1] + 1 - jump <= d and top > 0 and (ans[top - 1][0] == 0) and (ans[top - 1][1] >= s):
					ans[top] = (1, A[i - 1] + 1 - jump)
					top += 1
				else:
					print('IMPOSSIBLE')
					return
			ans[top] = (0, A[i] - A[i - 1] - 2)
			top += 1
			jump = A[i] - 1
	if A[n] + 1 - jump <= d and top > 0 and (ans[top - 1][0] == 0) and (ans[top - 1][1] >= s):
		ans[top] = (1, A[n] + 1 - jump)
		top += 1
	else:
		print('IMPOSSIBLE')
		return
	if m != A[n] + 1:
		ans[top] = (0, m - A[n] - 1)
		top += 1
	for i in range(top):
		if ans[i][0]:
			print('JUMP', ans[i][1])
		else:
			print('RUN', ans[i][1])
obstacle()


(n, m, s, d) = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort()
points = [0, a[0] - 1]
if d == 1 or a[0] - 1 < s:
	print('IMPOSSIBLE')
	exit()
for i in range(0, n):
	if a[i] - a[i - 1] - 2 < s:
		if a[i] + 1 - points[-1] > d:
			print('IMPOSSIBLE')
			exit()
	else:
		points.append(a[i - 1] + 1)
		points.append(a[i] - 1)
points.append(a[-1] + 1)
for i in range(1, len(points)):
	if i % 2 == 1:
		print('RUN', points[i] - points[i - 1])
	else:
		print('JUMP', points[i] - points[i - 1])
if a[-1] + 1 != m:
	print('RUN', m - 1 - a[-1])


import itertools

class SolutionImpossible(Exception):
	pass
(blocks_cnt, finish, min_sprint, max_jump) = [int(x) for x in input().split()]

def read_blocks_coords():
	it = (int(x) for x in input().split())
	return (x for x in it if x < finish)

def _grouper(value):
	if _grouper._prev_value is not None:
		if value - _grouper._prev_value - 1 <= min_sprint:
			_current_key = _grouper._current_key
		else:
			_current_key = id(value)
	else:
		_current_key = id(_grouper)
	_grouper._prev_value = value
	_grouper._current_key = _current_key
	return _current_key
_grouper._prev_value = None
_grouper._current_key = None

def check_chunk(run_from, block=None):
	if block is None:
		return
	next_run_from = block[-1] + 1
	if next_run_from - block[0] >= max_jump:
		raise SolutionImpossible
	if abs(run_from - block[0]) <= min_sprint:
		raise SolutionImpossible

def solve_chunk(run_from, block=None):
	if block is not None:
		run_len = block[0] - run_from - 1
		jump_len = block[-1] - block[0] + 2
		print('RUN {run_len}\nJUMP {jump_len}'.format(run_len=run_len, jump_len=jump_len))
	else:
		run_len = finish - run_from
		if run_len > 0:
			print('RUN {run_len}'.format(run_len=run_len))

def main():
	blocks = (list(g) for (k, g) in itertools.groupby(sorted(read_blocks_coords()), key=_grouper))
	chunks = []
	run_from = 0
	while True:
		block = next(blocks, None)
		chunk = (run_from, block)
		check_chunk(*chunk)
		chunks.append(chunk)
		if block is None:
			break
		run_from = block[-1] + 1
	for chunk in chunks:
		solve_chunk(*chunk)
try:
	main()
except SolutionImpossible:
	print('IMPOSSIBLE')


imp = 'IMPOSSIBLE'
(n, m, s, d) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
too_short = [False] * n
if a[0] - 1 < s:
	too_short[0] = True
for i in range(1, n):
	if a[i] - a[i - 1] - 2 < s:
		too_short[i] = True
max_jump = [-1] * n
for i in range(n):
	jump = a[i] - 1 + d
	l = i - 1
	r = n
	while l + 1 < r:
		cur = (l + r) // 2
		if a[cur] < jump:
			l = cur
		else:
			r = cur
	if l > i - 1:
		max_jump[i] = l + 1
reachable = 0
jumps = []
for i in range(n):
	if reachable < i:
		break
	if not too_short[i]:
		if max_jump[i] > reachable:
			reachable = max_jump[i]
			jumps.append(i)
if reachable < n:
	print(imp)
else:
	jump_up = 0
	jump_down = 0
	for jump in jumps:
		if jump != 0:
			print('JUMP', a[jump - 1] + 1 - jump_up)
			jump_down = a[jump - 1] + 1
		print('RUN', a[jump] - 1 - jump_down)
		jump_up = a[jump] - 1
	jump = jumps[-1]
	print('JUMP', a[n - 1] + 1 - jump_up)
	jump_down = a[n - 1] + 1
	if m > jump_down:
		print('RUN', m - jump_down)


(n, m, s, d) = map(int, input().split())
beg = [float('-inf')]
end = [float('-inf')]
a = [int(i) for i in input().split()]
for x in sorted(a):
	if x - end[-1] > s + 1:
		beg.append(x)
		end.append(x)
	else:
		end[-1] = x
last = 0
R = []
J = []
for i in range(1, len(beg)):
	R.append(beg[i] - 1 - last)
	last = beg[i] - 1
	J.append(end[i] + 1 - last)
	last = end[i] + 1
ok = True
for x in J:
	if x > d:
		ok = False
for x in R:
	if x < s:
		ok = False
if ok:
	for i in range(len(R)):
		print('RUN', R[i])
		print('JUMP', J[i])
	if last < m:
		print('RUN', m - last)
else:
	print('IMPOSSIBLE')


(n, m, s, d) = map(int, input().split())
x = sorted(map(int, input().split())) + [m + s + 1]
cur = l = 0
ans = []
while l < m:
	r = min(x[cur] - 1, m)
	ans += ['RUN ' + str(r - l)]
	if r == m:
		break
	if r - l < s:
		ans = ['IMPOSSIBLE']
		break
	t = x[cur] + 1
	while x[cur + 1] - 1 - t < s:
		cur += 1
		t = x[cur] + 1
	if t - r > d:
		ans = ['IMPOSSIBLE']
		break
	ans += ['JUMP ' + str(t - r)]
	l = t
	cur += 1
print('\n'.join(ans))


(num_barriers, finish, min_run, max_jump) = tuple(map(int, input().split()))
barriers = list(map(int, input().split())) + [-1]
barriers.sort()
for i in range(len(barriers) - 1):
	if barriers[i + 1] - barriers[i] <= min_run + 1:
		barriers[i] = (0, barriers[i] + 1, barriers[i + 1] - 1)
	else:
		barriers[i] = (1, barriers[i] + 1, barriers[i + 1] - 1)
barriers[len(barriers) - 1] = (1, barriers[len(barriers) - 1] + 1, finish)
if not barriers:
	pass
elif not barriers[0][0]:
	print('IMPOSSIBLE')
else:
	commands = []
	pos = 0
	for (tpe, st, en) in barriers:
		if tpe:
			if pos != st and st - pos <= max_jump:
				commands.append('JUMP %s' % (st - pos))
			elif pos != st:
				print('IMPOSSIBLE')
				break
			if en - st:
				commands.append('RUN %s' % (en - st))
			pos = en
	else:
		print('\n'.join(commands))


(n, m, s, d) = map(int, input().split())
x = list(map(int, input().split())) + [m + s + 1]
x.sort()
cur = l = 0
ans = []
while l < m:
	r = min(x[cur] - 1, m)
	ans.append(('RUN', r - l))
	if r == m:
		break
	if r - l < s:
		print('IMPOSSIBLE')
		exit()
	t = x[cur] + 1
	while x[cur + 1] - 1 - t < s:
		cur += 1
		t = x[cur] + 1
	if t - r > d:
		print('IMPOSSIBLE')
		exit()
	ans.append(('JUMP', t - r))
	l = t
	cur += 1
for aa in ans:
	print(*aa)


from sys import exit
(n, m, s, d) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
if a[0] - 1 < s:
	print('IMPOSSIBLE')
	exit()
strategy = []
i = 0
stand_point = 0
while i < n:
	strategy.append(a[i] - stand_point - 1)
	stand_point = a[i] - 1
	j = i + 1
	if j != n:
		(a2, a1) = (a[j], a[i])
	while j < n:
		if a2 - a1 - 2 < s:
			if a2 - a[i] + 2 > d:
				print('IMPOSSIBLE')
				exit()
			j += 1
			if j != n:
				a1 = a2
				a2 = a[j]
			continue
		else:
			strategy.append(a1 - a[i] + 2)
			i = j
			stand_point = a[i - 1] + 1
			break
	else:
		if d >= a[-1] - stand_point + 1 and strategy[-1] >= s:
			strategy.append(a[-1] - stand_point + 1)
		else:
			print('IMPOSSIBLE')
			exit()
		i = j
		stand_point = a[i - 1] + 1
if m - stand_point != 0:
	strategy.append(m - stand_point)
turn_flag = True
for i in strategy:
	if turn_flag:
		print('RUN', i)
	else:
		print('JUMP', i)
	turn_flag = not turn_flag


(n, m, s, d) = map(int, input().split())
obstacles = [-1] + list(map(int, input().split())) + [m + 1]
obstacles.sort()
check = []
a = True
ans = []
pos = 0
for i in range(n + 1):
	if i != n and obstacles[i + 1] - obstacles[i] - 2 < s:
		if i == 0 or obstacles[i + 1] + 1 - pos > d:
			a = False
			break
	else:
		if obstacles[i] + 1 - pos > d:
			a = False
			break
		if i != 0:
			ans.append('JUMP ' + str(obstacles[i] + 1 - pos))
		if obstacles[i + 1] - obstacles[i] - 2 != 0:
			ans.append('RUN ' + str(obstacles[i + 1] - obstacles[i] - 2))
		pos = obstacles[i + 1] - 1
if a:
	for each in ans:
		print(each)
else:
	print('IMPOSSIBLE')


for _ in range(1):
	(n, m, s, jump) = map(int, input().split())
	arr = [0] + sorted(list(map(int, input().split())))
	if s >= arr[1]:
		print('IMPOSSIBLE')
		continue
	max_indx = arr[1] - 1
	flag = 0
	travel = [0]
	for i in range(1, n + 1):
		if arr[i] - arr[i - 1] - 2 >= s:
			max_indx = arr[i] - 1
		if arr[i] + 1 <= max_indx + jump:
			travel.append(max_indx)
			continue
		flag = -1
		break
	if flag == -1:
		print('IMPOSSIBLE')
		continue
	arr[0] = -1
	travel.append(1000000000)
	ans = []
	count = 0
	for i in range(1, n + 1):
		if travel[i] != travel[i - 1]:
			ans.append(['RUN', arr[i] - arr[i - 1] - 2])
		if travel[i] == travel[i + 1]:
			count += arr[i + 1] - arr[i]
		else:
			ans.append(['JUMP', count + 2])
			count = 0
	if m - arr[-1] > 1:
		ans.append(['RUN', m - arr[-1] - 1])
	for i in ans:
		print(i[0], i[1])


(n, m, s, d) = [int(x) for x in input().split()]
a_raw = sorted([int(x) for x in input().split()], reverse=True)
a = []

def process_obstacle(crd):
	if a:
		segment = a.pop()
		dist = crd - segment[1] - 2
		if dist < s or crd == segment[1] + 1:
			a.append((segment[0], crd))
			return
		else:
			a.append(segment)
	a.append((crd, crd))
while a_raw:
	process_obstacle(a_raw.pop())
a_raw = None
a = a[::-1]

def freakout():
	print('IMPOSSIBLE')
	exit(0)
x = 0
steps = []
while x != m:
	if a:
		(l, r) = a.pop()
		if l < x:
			continue
		if l > m:
			a.clear()
			continue
		(dist, length) = (l - x - 1, r - l + 2)
		if dist < s:
			freakout()
		if length > d:
			freakout()
		steps.append('RUN %d' % dist)
		steps.append('JUMP %d' % length)
		x += dist + length
	else:
		steps.append('RUN %d' % (m - x))
		x = m
print('\n'.join(steps))


(n, m, s, d) = map(int, input().split())
A = sorted(list(map(int, input().split())))
inv = []
prev = -1
for i in range(len(A)):
	if A[i] < m:
		inv.append((prev, A[i]))
		prev = A[i]
	else:
		inv.append((prev, m))
		break
if A[-1] < m:
	inv.append((A[-1], m))
output = [inv[-1]]
last = inv[-1]
for i in range(len(inv) - 2, -1, -1):
	(a, b) = (inv[i], last)
	if a[1] - a[0] >= s + 2 and b[0] - a[1] <= d - 2:
		last = inv[i]
		output.append(last)
output = output[::-1]
if m < A[0]:
	print('RUN ' + str(m))
elif last[0] != -1 or A[0] <= s:
	print('IMPOSSIBLE')
else:
	last = 0
	for i in range(1, len(output)):
		(a, b) = (output[i - 1], output[i])
		print('RUN ' + str(a[1] - a[0] - 2))
		print('JUMP ' + str(b[0] - a[1] + 2))
		last = b[0] + 1
	if last < m:
		print('RUN ' + str(m - last))


import sys

def solve():
	(n, m, s, d) = [int(x) for x in input().split()]
	obstacles = [int(x) for x in input().split()]
	obstacles.sort()
	if obstacles[0] <= s:
		return False
	pieces = [[obstacles[0], obstacles[0]]]
	for x in obstacles:
		if pieces[-1][1] + s + 2 > x:
			pieces[-1][1] = x
		else:
			if pieces[-1][1] - pieces[-1][0] + 2 > d:
				return False
			pieces.append([x, x])
	if pieces[-1][1] - pieces[-1][0] + 2 > d:
		return False
	pos = 0
	for piece in pieces:
		sys.stdout.write('RUN ' + str(piece[0] - pos - 1) + '\n')
		sys.stdout.write('JUMP ' + str(piece[1] - piece[0] + 2) + '\n')
		pos = piece[1] + 1
	if pos < m:
		sys.stdout.write('RUN ' + str(m - pos) + '\n')
	return True
if not solve():
	print('IMPOSSIBLE')


f = lambda : map(int, input().split())
(n, m, s, d) = f()
(p, x, z) = ([], -1, 1)
for y in sorted(f()) + [m + 1]:
	if y - x > s + 1 or y > m or x < 0:
		u = x - z + 2
		v = y - x - 2
		if u > d or (v < s and x < 0):
			p = ['IMPOSSIBLE']
			break
		if u:
			p += ['JUMP ' + str(u)]
		if v:
			p += ['RUN ' + str(v)]
		z = y
	x = y
print('\n'.join(p))


(n, m, s, d) = map(int, input().split())
a = sorted(list(map(int, input().split())))

def e():
	print('IMPOSSIBLE')
	exit()
if d == 1:
	e()
ans = list()
if a[0] - 1 < s:
	e()
ans.append(f'RUN {a[0] - 1}')
now = 2
for i in range(1, n):
	if a[i] - a[i - 1] - 2 < s:
		now += a[i] - a[i - 1]
		if now > d:
			e()
	else:
		ans.append(f'JUMP {now}')
		ans.append(f'RUN {a[i] - a[i - 1] - 2}')
		now = 2
ans.append(f'JUMP {now}')
if m - a[-1] - 1:
	ans.append(f'RUN {m - a[-1] - 1}')
print('\n'.join(ans))