Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Restore Missing Values

By mazedrupok · Limits 1s, 512 MB

Consider an array of 'N' integers which is indexed from '1' to 'N'.
Exactly 'Q' queries numbered from '1' to 'Q' are applied on them in increasing order.
For the 'i'-th query, an arbitrary range [L, R] of the array is selected (1 <= L <= R <= N) and each value from index 'L' to index 'R' gets changed to 'i'. It is guaranteed that every index of the array is covered by at least one range.

You are given an array of 'N' integers where value of the array is from '0' to 'Q'.
Value '0' means the value is missing which can be restored to any integer from '1' to 'Q'.
Value 'i' (1 <= i <= Q) means 'i' was stored in the array while 'i'-th query was applied.
Your task is to check if the given array can be acquired after applying the 'Q' queries.

If it is possible to acquire the given array, restore the missing values of the array.
Array restoration may be possible with multiple solution. If multiple solutions are available, you have to restore the missing values such that the array is lexicographically minimum.

Input

The first line of input file contains an integer 'T' (1 <= T <= 60) denoting the test case of input.
Each test case consists of two lines.
First line contains two integers 'N' and 'Q' (1 <= N, Q <= 100000),
where 'N' is the size of the array and 'Q' is the number of queries.
Second line of each test case contains 'N' integers 'A1', 'A2', ... 'An' (0 <= Ai <= Q).

Output

Print 'YES' with the case number if array can be restored.
And then in the second line print the 'N' integers of the array.
Print 'NO' with the case number if array can't be restored.

Sample

InputOutput
4
5 3
2 0 1 3 3
3 4
0 0 0
4 5
5 5 5 5
4 3
2 1 0 2
Case 1: YES
2 1 1 3 3
Case 2: YES
1 1 4
Case 3: YES
5 5 5 5
Case 4: NO

Discussion

Statistics


58% Solution Ratio

ju_trojanEarliest, Jan '20

maruf089Fastest, 0.2s

MursaleenLightest, 2.9 MB

MursaleenShortest, 1214B

Submit

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.