あなたは壮大で進化する交響曲を指揮しています。アンサンブルは演奏者たちで構成され、各演奏者は特定の高調波周波数（非負整数で表される）を演奏します。最初、舞台は完全に空です。$n$ ステップの順次動作を経て、アレンジを変更するためのアクションがちょうど1つ行われます。各ステップ $i = 1, 2, \dots, n$ に対して、以下の操作が実行されます。
- 操作が
+(入場) の場合：新しい演奏者がアンサンブルに加わります。あなたはその演奏者が演奏する正確な周波数 $b_i$ を決定しなければなりません。 - 操作が
-(退場) の場合：演奏者が舞台を去ります。あなたは現在演奏中の演奏者の周波数 $b_i$ を選び、その周波数を演奏する演奏者のうち正確に1人を演奏停止にしなければなりません。
各ステップにおいて、演奏は「ファントムノート」によって支えられています。交響曲の独特な音響特性のため、ファントムノートは舞台上の誰も実際に演奏することはありません。代わりに、その音高は常に 現在の演奏に欠けている最小の周波数 によって決定されます。ファントムノートの音高は数学的には mex (最小排除値) として定義されます。$S$ を、現在アンサンブルが演奏している周波数の多重集合とします。最小排除値 $\operatorname{mex}(S)$ は、$x \notin S$ を満たす最小の非負整数 $x$ です。
$i$ 番目のアクションの後、ファントムノートが正確に $a_i$ で共鳴することが要求されます。
あなたの課題は、必要なファントムノートの進行を各ステップで完全に調整するような、選択された周波数 $b_1, b_2, \dots, b_n$ の有効な列が存在するかどうかを判定し、存在する場合はそのような列を1つ構築することです。
入力
この問題には複数のテストケースが含まれます。入力の最初の行には単一の整数 $t$ ($1 \le t \le 3 \cdot 10^5$) が含まれ、テストケースの数を表します。
各テストケースについて、各演奏は以下の3行で記述されます。
- 最初の行には単一の整数 $n$ ($1 \le n \le 5000$) が含まれ、演奏における連続するステップの総数を表します。
- 2行目には長さ $n$ の文字列 $op$ が含まれ、文字は
+と-のみで構成されます。文字 $op_i$ は $i$ 番目のアクションの性質を示します。+は演奏者の入場を、-は演奏者の退場を意味します。 - 3行目には $n$ 個の整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le n$) が含まれ、$i$ 番目のアクション後のファントムノートの要求される正確な音高を表します。
すべての演奏における $n^2$ の合計が $5000^2$ を超えないことが厳密に保証されます。
出力
各演奏について、以下のように結果を出力してください。
要求されたファントムノートの進行を調整することが不可能な場合は、単語 NO を含む1行を出力してください。
そうでない場合は、2行を出力してください。
- 最初の行には単語
YESを含めなければなりません。 - 2行目には $n$ 個の非負整数 $b_1, b_2, \dots, b_n$ が含まれ、対応する各ステップで入場または退場する演奏者が演奏する具体的な周波数を表します。
各周波数 $b_i$ は、問題文に記述された音響制約と操作規則を完全に満たさなければなりません。標準的な符号付き64ビット整数で表現可能な任意の有効な非負整数を出力することが許可されます。
条件を満たす周波数の列が複数存在する場合、そのうちの任意の1つを出力して構いません。
入出力例
入力例 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には4つのテストケースがあります。
- 1つ目のテストケースでは、$1$ を挿入すると mex (ファントムノート) は $0$ のままになり、次に $0$ を挿入すると mex は $2$ になります。
- 2つ目のテストケースでは、$2,0,1$ を挿入すると mex の列は $0,1,3$ になります。
- 3つ目のテストケースでは、最初の操作後の mex $1$ により $0$ の挿入が強制されます。それを消去した後、さらに1回の挿入では mex $2$ にできないため、答えは
NOです。 - 4つ目のテストケースでは、出力された値により多重集合が変化し、mex の列は $0,2,0,0,0,1$ になります。