Вы ведёте грандиозную, развивающуюся симфонию. Ансамбль состоит из музыкантов, каждый из которых играет определённую гармоническую частоту (представленную неотрицательным целым числом). Изначально сцена совершенно пуста. За $n$ последовательных шагов выполняется ровно одно действие, изменяющее состав. На каждом шаге $i = 1, 2, \dots, n$ выполняется операция:

• Если операция + (Вход): новый музыкант присоединяется к ансамблю. Вы должны сами решить, какую именно частоту $b_i$ он будет играть.
• Если операция - (Выход): музыкант покидает сцену. Вы должны выбрать частоту $b_i$ одного из текущих выступающих музыкантов и ровно одного из них заставить прекратить игру.

На каждом шаге исполнение привязано к «Фантомной ноте». Из-за уникальной акустики симфонии Фантомная нота никогда не звучит на сцене. Вместо этого её высота всегда определяется наименьшей частотой, которая в данный момент отсутствует в исполнении. Высота Фантомной ноты математически определяется как mex (минимальное пропущенное значение). Пусть $S$ — мультимножество неотрицательных целых чисел, представляющее набор частот, которые в данный момент играет ансамбль. Минимальное пропущенное значение, обозначаемое $\operatorname{mex}(S)$, — это наименьшее неотрицательное целое число $x$ такое, что $x \notin S$.

После $i$-го действия требуется, чтобы Фантомная нота звучала ровно на $a_i$.

Ваша задача — определить, существует ли последовательность выбранных частот $b_1, b_2, \dots, b_n$, которая идеально воспроизводит требуемый ряд Фантомной ноты на каждом шаге, и построить одну такую последовательность, если она существует.

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

Эта задача содержит несколько наборов входных данных. Первая строка ввода содержит одно целое число $t$ ($1 \le t \le 3 \cdot 10^5$) — количество наборов входных данных.

Для каждого набора входных данных каждое исполнение описывается тремя строками:

• Первая строка содержит одно целое число $n$ ($1 \le n \le 5000$) — общее количество последовательных шагов в исполнении.
• Вторая строка содержит строку $op$ длины $n$, состоящую исключительно из символов + и -. Символ $op_i$ определяет характер $i$-го действия: + означает вход музыканта, а - — выход музыканта.
• Третья строка содержит $n$ целых чисел $a_1, a_2, \dots, a_n$ ($0 \le a_i \le n$) — требуемую высоту Фантомной ноты после $i$-го действия.

Гарантируется, что сумма $n^2$ по всем исполнениям не превосходит $5000^2$.

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

Для каждого исполнения выведите результат следующим образом:

Если невозможно организовать требуемый ряд Фантомной ноты, выведите одну строку, содержащую слово NO.

В противном случае выведите две строки:

• Первая строка должна содержать слово YES;
• Вторая строка должна содержать $n$ неотрицательных целых чисел $b_1, b_2, \dots, b_n$, представляющих конкретную частоту, которую играет входящий или уходящий музыкант на соответствующем шаге.

Каждая частота $b_i$ должна в точности удовлетворять акустическим ограничениям и правилам операций, описанным в условии. Разрешается выводить любое допустимое неотрицательное целое число, представимое стандартным знаковым 64-битным целым.

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

Примеры

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

4
2
++
0 2
3
+++
0 1 3
3
+-+
1 0 2
6
++-+-+
0 2 0 0 0 1

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

YES
1 0
YES
2 0 1
NO
YES
1 0 0 7 1 0

Примечание

В первом примере четыре набора входных данных.

• В первом наборе вставка $1$ оставляет mex (Фантомную ноту) равным $0$, затем вставка $0$ делает mex равным $2$.
• Во втором наборе вставка $2,0,1$ даёт последовательность mex $0,1,3$.
• В третьем наборе mex $1$ после первой операции вынуждает вставить $0$; после его удаления ещё одна вставка не может сделать mex равным $2$, поэтому ответ NO.
• В четвёртом наборе выведенные значения приводят к эволюции мультимножества с последовательностью mex $0,2,0,0,0,1$.