After his leave from DMOJ, Wesley is very angry and demands you to construct an array of length
consisting of positive integers such that each element
satisfies the following requirements:
- There are
elements before index
that are strictly smaller than
- There are
elements after index
that are strictly smaller than
- There are
elements before index
that are strictly greater than
- There are
elements after index
that are strictly greater than
Luckily, Wesley is a kind person and will allow for your array to violate at most of the requirements above. In particular, you can pick an index
and modify exactly one of
,
,
and
. In exchange however, he requests that your array is the lexicographically least one (it must be the lexicographically least array that violates at most
requirement).
Note: We say that array is lexicographically less than array
if
and at the smallest index
where
and
differ,
.
Constraints
Subtask 1 [12%]
Subtask 2 [23%]
Subtask 3 [43%]
Subtask 4 [22%]
No additional constraints.
Input Specification
The first line contains a single integer .
The next line contains integers
.
The next line contains integers
.
The next line contains integers
.
The next line contains integers
.
Output Specification
If no such array exists, output -1
.
Otherwise, output the elements of the lexicographically least array on a single line.
Sample Input
5
0 0 2 2 1
1 0 2 1 0
0 1 0 1 2
2 1 0 0 0
Sample Output
2 1 4 3 2
Explanation for Sample
The array above satisfies all the requirements except for . It can be shown that this is the lexicographically least array that violates at most one requirement.
Comments
I'm still here...
hi still here
wac7 when