Walk Alone is an expert in strings, but he gets bored with traditional algorithms like Manacher, so he wants to do it in reverse. The problem he raised is as follows:

There's a hidden string $$$S$$$ only consisting character 'a' and 'b'. You are given $$$n$$$–the length of the string. Then the string $$$S$$$ is transformed as follows:

• First, add two character $$$\&|$$$ to the beginning of the string.
• Second, for every character in the original string, add a character $$$|$$$ to the right of it.

For example, string $$$abaaa$$$ is transformed into $$$\&|a|b|a|a|a|$$$, and string $$$aaaaa$$$ is transformed into $$$\&|a|a|a|a|a|$$$. After this operation, the length of the string $$$S$$$ has become $$$2n+2$$$. Let the transformed string be $$$T$$$.

He then will give you a sequence $$$\{a_n\}$$$ of length $$$2n+2$$$, the $$$i$$$-th of which denotes the maximal length of palindrome centered at the $$$i$$$-th character. Formally, $$$a_i=j$$$ where $$$j=\max\{x|x \in \mathbb{N}^*, \forall y \le x, T_{i-y+1}=T_{i+y-1}\}$$$. For example, the original string $$$abaaa$$$ can generate the final sequence $$$\{1,1,2,1,4,1,2,3,4,3,2,1\}$$$. Note that every character in the string is compared through ASCII code, so character $$$\&$$$ cannot be in pair with any other character.

Your work is to restore the string $$$S$$$ using sequence $$$\{a_n\}$$$.