You have a sorted list of numbers in increasing order from
to
. This list has
elements. Some numbers may appear multiple times, so you have recorded the number of occurrences of each number in this list,
. However, you messed up when assigning the indices, so
is actually the number of occurrences of
, for some unknown permutation
of
. You recall that
for some
and
. Find a permutation
that satisfies this. If no such permutation
exists, output
-1
.
You will be rewarded even if you can only determine the existence of such a . Outputting any permutation of
if there exists a permutation and
-1
otherwise for every test case of a subtask will earn you half of the subtask's points, assuming you do not already receive the full points (if one of the permutations outputted is wrong, but there does exist a permutation).
Constraints
Subtask 1 [10%]
Subtask 2 [20%]
Subtask 3 [20%]
Subtask 4 [10%]
Subtask 5 [40%]
Input Specification
The first line will contain four space-separated integers ,
,
, and
.
The next line will contain space-separated integers
.
Output Specification
If there exists a permutation, output space-separated integers
. There may be many valid permutations. Any one of them will be accepted.
If there does not exist a permutation, output -1
.
Sample Input 1
3 10 5 1
4 5 1
Sample Output 1
2 1 3
Explanation for Sample 1
There are six possible lists :
1 1 1 1 2 2 2 2 2 3
1 1 1 1 2 3 3 3 3 3
1 1 1 1 1 2 2 2 2 3
1 1 1 1 1 2 3 3 3 3
1 2 2 2 2 3 3 3 3 3
1 2 2 2 2 2 3 3 3 3
The third list satisfies . The corresponding
which gives this list is
.
Sample Input 2
6 9 4 4
2 2 2 1 1 1
Sample Output 2
4 5 6 1 2 3
Sample Input 3
6 9 3 4
2 2 2 1 1 1
Sample Output 3
-1
Comments