It is well-known that Anya likes peanuts.
As the head of the city planning department, you have been tasked with planning the construction of a line of peanut shops. The shops will have stocks of peanuts in some order.
Her father however, who you know as Loid Forger, is not a man known for his patience with Anya, and as such will only go to two peanut shops that are side-by-side.
This is fine by Anya as long as she can buy at least peanuts, no matter which two adjacent shops they visit. If the two shops do not have enough stock, she will be quite distraught.
It turns out that of all plans that satisfy Anya's requirement, the lexicographically smallest one is the cheapest. You have been tasked to find the cheapest arrangement to make Anya happy, or sadly report that none exist.
Subtask 1 [20%]
Subtask 2 [30%]
Subtask 3 [50%]
No additional constraints.
The first line will contain space-separated integers and .
The second line will contain space-separated integers, the list of shop stocks.
Output the lexicographically smallest array of stocks as specified by the problem. If there is no such array, output
You will receive 50% of the points for a case if your program outputs an array that satisfies Anya but that is not the cheapest.
Sample Input 1
4 8 2 6 10 1
Sample Output 1
1 10 2 6
Explanation for Sample 1
The adjacent sums are
11 12 8, which are all at least . It can be proven that this is the lexicographically smallest such arrangement.
Sample Input 2
4 9 2 6 10 1
Sample Output 2
Explanation for Sample 2
It can be proven that no arrangement will make Anya happy.