D. MEX мультимножеств
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив $$$a_1, a_2, \ldots, a_n$$$. Существуют $$$3$$$ изначально пустых мультимножества $$$A, B, C$$$, и для каждого индекса $$$i$$$ ($$$1 \leq i \leq n$$$) вы можете положить $$$a_i$$$ ровно в одно из $$$A$$$, $$$B$$$ или $$$C$$$.

Определите, возможно ли распределить элементы по мультимножествам так, чтобы $$$\operatorname{MEX}(A) + \operatorname{MEX}(B) + \operatorname{MEX}(C) \geq 2 \cdot \max(\operatorname{MEX}(A), \operatorname{MEX}(B), \operatorname{MEX}(C))$$$$$$^{\text{∗}}$$$. Если да, выведите одно из таких распределений.

$$$^{\text{∗}}$$$$$$\operatorname{MEX}(D)$$$ определяется как наименьшее неотрицательное целое число, которого нет в множестве $$$D$$$. Например, $$$\operatorname{MEX}([1, 2, 0, 5]) = 3$$$, а $$$\operatorname{MEX}([1, 2, 4, 9]) = 0$$$. $$$\operatorname{MEX}$$$ пустого множества равен $$$0$$$.

Входные данные

Первая строка каждого набора входных данных содержит $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит $$$n$$$ ($$$3 \leq n \leq 2 \cdot 10^5$$$) — длину массива $$$a$$$.

Вторая строка каждого набора входных данных содержит $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 10^9$$$) — массив $$$a$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

Выходные данные

Если существует корректное распределение элементов по мультимножествам, выведите $$$\texttt{YES}$$$. Иначе выведите $$$\texttt{NO}$$$.

Если ответ $$$\texttt{YES}$$$, выведите на новой строке строку $$$s$$$ длины $$$n$$$ такую, что $$$s_i = \texttt{A}$$$, если $$$i$$$-й элемент был помещён в мультимножество $$$A$$$, $$$s_i = \texttt{B}$$$, если $$$i$$$-й элемент был помещён в мультимножество $$$B$$$, и $$$s_i = \texttt{C}$$$, если $$$i$$$-й элемент был помещён в мультимножество $$$C$$$.

Вы можете выводить ответ в любом регистре (верхнем или нижнем). Например, строки $$$\texttt{YES}$$$, $$$\texttt{yes}$$$, $$$\texttt{yEs}$$$ и $$$\texttt{Yes}$$$ будут распознаны как положительные ответы, а строки $$$\texttt{NO}$$$, $$$\texttt{no}$$$, $$$\texttt{No}$$$ будут распознаны как отрицательные ответы. Кроме того, строки $$$\texttt{AABCAAA}$$$, $$$\texttt{aabcaaa}$$$ и $$$\texttt{aaBcaaa}$$$ будут распознаны как один и тот же ответ.

Если возможных ответов несколько, выведите любой.

Пример
Входные данные
5
6
1 0 0 1 2 1
4
0 0 0 0
3
0 2 2
4
6 7 6 7
5
0 0 0 1 2
Выходные данные
YES
ABABCA
YES
ABAC
NO
YES
AAAB
YES
ABCAB
Примечание

В первом наборе входных данных можно взять $$$A = \{0, 1, 1\}$$$, $$$B = \{0, 1\}$$$, $$$C = \{2\}$$$, то есть $$$\operatorname{MEX}(A) + \operatorname{MEX}(B) + \operatorname{MEX}(C) = 4$$$, а $$$2 \cdot \max(\operatorname{MEX}(A), \operatorname{MEX}(B), \operatorname{MEX}(C)) = 2 \cdot \max(2, 2, 0) = 4$$$.

В третьем наборе входных данных можно показать, что корректных распределений не существует.