题目描述

Some computer games are extremely fun and this problem may be about one of these.

You are given a sequence of one dimensional blocks, each of length that is a power of two. The goal of the game is to merge all the blocks into one big block. The blocks are presented one by one, and for each one you have to decide whether to stick it immediately to the left or immediately to the right of the previous blocks.

Every time two blocks of the same size are adjacent, they merge into one block that is twice as long as each of them. Note that, as long as possible, the resulting blocks immediately merge with adjacent ones. For example, if the current sequence of blocks is $2, 4, 16$, then sticking $2$ on the left side leads to $8, 16$, while sticking it on the right side gives $2, 4, 16, 2$. Note that at any moment there is at most one mergeable pair of blocks.

You have lost the game (again!) and you are wondering whether there was any way to win at all. Analyze the sequence to find out.

输入格式

The first line of input contains the number of test cases $T$. The descriptions of the test cases follow:

Each test case consists of two lines. The first one contains a positive integer $n \leq 1 000$ – the length of the sequence. The next line contains a sequence of $n$ block lengths, each a power of two. The sum of all the lengths does not exceed $2^{13}$.

输出格式

For each test case, output one line containing the word $\texttt{no}$ if winning the game is not possible. Otherwise, output a word consisting of $n$ letters $\texttt{l}$ and $\texttt{r}$, denoting whether the corresponding block should be stuck to the left or to the right. Note that for the first block it does not matter.

题目大意

题目描述

你有一个双端队列，同时给定一个长度为 $n$ 的序列 $a$ ，满足序列中的元素为 2 的非负整数幂

从前到后遍历整个序列，每次对于 $a_i$ 可以选择将它放入双端队列的队头或者队尾，如果队列中存在相邻两个元素大小相同，那么它们将合并为一个新的元素，元素大小为先前两个元素之和

求是否存在一个合法的方案使得队列最后只剩下一个元素，若存在，输出方案，不存在输出 $no$

多组数据

读入格式

首先读入一个 $t$ 表示数据组数

对于每一组数据第一行读入一个 $n$ 表示序列长度，下一行读入 $n$ 个元素，$a_1$ 到 $a_n$

输出格式

若存在合法方案输出一个字符串，其中第 $i$ 个字符若为 $l$ 表示放入队头，$r$ 表示放入队尾,其中第一个元素 $l,r$ 任意

若不存在合法方案，输出 no

3
9
2 8 4 1 1 4 4 4 4
5
2 16 4 8 2
3
2 2 2

rrrlllrrr
no
no