Cheap but Similar

Mind the memory limit.

In 2077, a machine called the Sandevistan was developed. It connects to the nervous system and speeds up movement. Mineral X is essential to build it, but Mineral X is extremely expensive. One day, a way to build the same device with much cheaper Mineral Y was discovered, and many companies rushed to mine Mineral Y.

A vein containing Mineral Y is a straight line stretching left to right. The vein consists of $N$ cells. The $i$-th cell from the left contains $A_i$ units of mineral. The first cell ($i=1$) has already been developed into a passage and contains no mineral, so $A_1=0$.

Mining requires equipment. One piece of equipment can mine all minerals in a consecutive segment of 1 to 3 cells that starts immediately to its right. The equipment must be installed in the cell immediately to the left of the mined segment. For safety reasons, minerals in a cell containing equipment cannot be mined, and equipment cannot be installed on a cell mined by another piece of equipment.

Let the total amount of mineral be $S=\sum_{i=1}^{N} A_i$. Determine whether it is possible to mine at least $0.75S$ minerals. If it is possible, output how to place the equipment and which cells to mine.

This image visualizes the first sample.

The first line contains the number of test cases $T$. $(1 \le T \le 100\,000)$

For each test case, the first line contains the length $N$ of the vein. $(1 \le N \le 20\,772\,077)$

The second line contains $A_1,A_2,\dots,A_N$, the mineral amounts in the cells, separated by spaces. $(0 \le A_i \le 100, A_1=0)$

The sum of $N$ over all test cases does not exceed $20\,772\,077$.

For each test case, if there is no way to mine at least $0.75S$ minerals, print NO on the first line.

If there is a way, print YES on the first line. On the second line, print a string of length $N$ consisting only of the characters 0, 1, 2, and 3.

If the $i$-th cell is not mined, the $i$-th character must be 0. If the $i$-th cell is mined by equipment whose mined segment has length $k$, the $i$-th character must be $k$.

This was a hidden problem of SNUPC 2024. Look at the lower-right corner of the contest poster.