← 返回题目列表

Codeforces · 1476/F

F. 灯笼

中文机器翻译题面 查看原题

一排有 $$$n$$$ 灯笼。灯笼 $$$i$$$ 放置在位置 $$$i$$$,功率等于 $$$p_i$$$。

每个灯笼都可以被引导照亮左侧的一些灯笼或右侧的一些灯笼。如果第 $$$i$$$ 个灯笼向左转动,它会照亮 $$$j \in [i - p_i, i - 1]$$$ 中的所有 $$$j$$$ 灯笼。类似地,如果它向右转动,它会照亮所有这样的灯笼 $$$j$$$ $$$j \in [i + 1, i + p_i]$$$。

您的目标是为每个灯笼选择一个方向,以便每个灯笼至少被另一个灯笼照亮,否则报告这是不可能的。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10000$$$) — 测试用例的数量。

每个测试用例由两行组成。第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$) — 灯笼的数量。

第二行包含 $$$n$$$ 整数 $$$p_1, p_2, \dots, p_n$$$ ($$$0 \le p_i \le n$$$) — 第 $$$i$$$ 个灯笼的功率。

所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$。

输出

对于每个测试用例,打印答案如下:

如果可以引导所有灯笼,使每个灯笼都被照亮,请在第一行打印 YES,并在第二行打印一串 $$$n$$$ 字符 L 和/或 R(如果第 $$$i$$$ 个灯笼向左转动,则第 $$$i$$$ 个字符为 L,否则该字符为 R)。如果有多个答案,您可以打印其中任何一个。

如果没有答案,只需为该测试用例打印“否”。

示例

输入 #1

4
8
0 0 3 1 1 1 1 2
2
1 1
2
2 2
2
0 1

输出 #1

YES
RRLLLLRL
YES
RL
YES
RL
NO