G. Nonogram
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Alice has picked up a new logic puzzle called a nonogram. A nonogram is played on a board consisting of $$$n$$$ cells arranged in a row. You are given a sequence $$$b_1, b_2, \dots, b_k$$$. You must color each cell black ('1') or white ('0') such that the contiguous blocks of black cells have lengths exactly $$$b_1, b_2, \dots, b_k$$$.

For example, if $$$n = 6$$$ and the clue sequence is $$$[3, 1]$$$, the board must contain a block of $$$3$$$ black cells, followed by at least one white cell, followed by a block of one black cell. There can be any number of white cells before the first block, after the last block, or between blocks (as long as there is at least one). So valid solutions are 011101, 111001 or 111010.

Alice has become a master at solving nonograms and now finds them boring. To make things more interesting, her friend Bob introduces an additional constraint. He colors some of the cells white ('0'), and leaves the rest empty ('?'). Alice must solve the nonogram while ensuring every cell Bob colored remains white.

Help Alice figure out if it is possible to find a solution to the puzzle consistent with Bob's constraints. In other words, you need to determine if you can color each '?' cell black or white so that the contiguous blocks of black cells have lengths exactly $$$b_1, b_2, \dots, b_k$$$.

In addition, if it is solvable, then for each cell, you must find whether it is definitely black ('1'), definitely white ('0'), or can be either ('?').

Input

The first line contains an integer $$$T\ (1 \leq T \leq 10^5)$$$ — the number of test cases.

Each case is described by three lines. The first line contains two integers $$$n\ (1 \leq n \leq 10^6)$$$ and $$$k\ (0 \leq k \leq n)$$$ — the length of the strip and the number of blocks. The second line contains a string of length $$$n$$$, consisting of characters '0' and '?' — which describes Bob's constraint. The third line contains $$$k$$$ integers $$$b_1,b_2,\cdots,b_k\ (1 \leq b_i \leq n\ and\ \sum_{i=1}^k b_i \leq n-k+1)$$$ — the lengths of the contiguous black blocks.

It is guaranteed that the sum of $$$n$$$ over all cases does not exceed $$$2 \times 10^6$$$.

Output

For each test case,

  • If no valid solution exists, print No.
  • Otherwise, print Yes on the first line, followed by a string of length $$$n$$$ on the second line where the $$$i$$$-th character is
    • '1' if the $$$i$$$-th cell is black in every valid solution.
    • '0' if the $$$i$$$-th cell is white in every valid solution.
    • '?' if the $$$i$$$-th cell is black in some solutions, but white in others.
Example
Input
5
5 2
??00?
2 1
5 1
???0?
2
5 1
??0??
3
4 0
??0?

6 2
??????
3 1
Output
Yes
11001
Yes
?1?00
No
Yes
0000
Yes
?11???
Note

In the first case, the only solution consistent with Bob's constraints is 11001.

In the second case, there are two valid solutions 01100 and 11000. The first and the third character can be either '0' or '1' depending on the solution, so, they are marked as '?'. The second character is '1' in both solutions, whereas the last two characters are always '0'. Therefore, the resulting output is ?1?00.

In the third case, there is no way to color $$$3$$$ consecutive cells black without touching the third cell. Thus the puzzle has no valid solution.