410535: GYM104036 5 Линейный футбол

Близнецам Петру и Павлу родители подарили на день рождения настольный футбол, но не простой, а линейный.

В этом варианте игры все фигурки игроков расположены в одну линию на равном расстоянии друг от друга. Всего есть $$$n$$$ игроков. Для определенности пронумеруем их позиции числами от $$$1$$$ до $$$n$$$ слева направо. Ворота находятся в позициях $$$0$$$ и $$$n + 1$$$. Каждый игрок имеет свою силу удара, и может при ударе по мячу перебросить его на фиксированное количество позиций другому игроку. Силу удара игрока на позиции $$$i$$$ обозначим через $$$a_i$$$, что означает, что после удара этого игрока мяч переместится на $$$a_i$$$ позиций. Если $$$a_i$$$ положительное, то мяч переместится вправо, в сторону увеличения номеров, а если $$$a_i$$$ отрицательное, то мяч переместится влево, в сторону уменьшения. Если после удара мяч попадает в позицию меньшую либо равную $$$0$$$, то засчитывается гол в левые ворота, а если в позицию большую либо равную $$$n + 1$$$, то в правые. Если после удара мяч попадает к другому игроку, то тот наносит следующий удар со своей силой, и игра продолжается.

Близнецы решили сыграть $$$n$$$ игр, в $$$i$$$-й из которых первый удар нанесёт игрок номер $$$i$$$. Для каждой игры выведите, в какие ворота будет забит мяч в этой игре (L, если в левые, R, если в правые, U, если гол никто не забьёт).

Первая строка входных данных содержит целое число $$$n$$$ ($$$1 \leqslant n \leqslant 10^5$$$) — количество игроков. Далее в следующих $$$n$$$ строках указаны силы и направления ударов игроков. В $$$i + 1$$$ строке указана сила игрока $$$a_i$$$, находящегося в позиции $$$i$$$. После удара этого игрока мяч окажется в позиции $$$i + a_i$$$. ($$$-10^5 \leqslant a_i \leqslant 10^5$$$ для любого $$$i$$$ от $$$1$$$ до $$$n$$$).

Выведите $$$n$$$ символов, обозначающих результаты игр, в одну строку без пробелов. Если пронумеровать эти символы от $$$1$$$ до $$$n$$$, то в $$$i$$$-й позиции этой строки должен находиться символ L для мяча, забитого в левые ворота, R для мяча, забитого в правые ворота, и U для случая, когда игра не закончилась взятием ворот (при начале этой игры c удара $$$i$$$-го игрока).

Решения, правильно работающие для случаев, в которых количество игроков не превосходит 100, получат не менее 44 баллов.

Решения, правильно работающие для случаев, в которых все игроки, кроме самого правого ударяют вправо, получат не менее 12 баллов.

Решения, правильно работающие для случаев, в которых левая половина игроков ударяет вправо, а правая половина игроков ударяет влево, причём количество игроков, перебрасывающих мяч на противоположную половину поля не превосходит 10, получат не менее 12 баллов.

Решения, правильно работающие для случаев, в которых каждая игра заканчивается взятием ворот, получат не менее 12 баллов.

10
-5
2
0
5
5
-1
6
-1
-1
-5

LRURUURRRU

В примере первый игрок сразу забивает в левые ворота. Второй игрок передаёт четвёртому, четвёртый — девятому, девятый — восьмому, восьмой — седьмому, а седьмой забивает в правые ворота. Третий игрок играет сам с собой. Пятый и десятый перекидывают мяч друг другу. Шестой передает пятому и далее снова играют пятый и десятый.