Uzhlyandian Wars
In the distant Uzhlyandian Empire, the 155th tournament of the strategic game "Uzhlyandian Wars" is underway! Emperor Alexander I is assembling a team to ensure his country shines at this prestigious event. The team is primarily composed of military personnel, as gamers are rare in Uzhlyandia.
The tournament's opening ceremony has strict rules: all team members must enter the contest hall in non-decreasing order of their height. However, there's a challenge: the soldiers are divided into 2 equally sized units, each already sorted by height. With only a few minutes before the competition starts, the Emperor needs your help to quickly determine the order in which the participants should enter, ensuring the success of this historic tournament!
Input
The first line of the input contains a single natural number n (1 ≤ n ≤ 10^5) – the size of each unit.The next line contains n natural numbers A[i] (1 ≤ A[i] ≤ 10^9) – the heights of the soldiers in the first unit, sorted in non-decreasing order.The following line contains n natural numbers B[i] (1 ≤ B[i] ≤ 10^9) – the heights of the soldiers in the second unit, sorted in non-decreasing order.
Output
Output 2n numbers – the heights of all soldiers from both units, sorted in non-decreasing order.