Trộn hai dãy không giảm thành một dãy không giảm


Submit solution

Points: 1
Time limit: 2.0s
Python 3 3.0s
Memory limit: 977M

Author:
Problem type

Cho hai dãy số nguyên đã được sắp không giảm dần a_1 \le a_2 \le a_3 \le ... \le a_nb_1 \le b_2 \le b_3 \le ... \le b_m. Bạn hãy lập trình đọc vào hai dãy và trộn lại thành một dãy không giảm

Input

  • Dòng đầu chứa số nguyên dương n là số phần tử của dãy thứ nhất (0 <
n \le 10^6)
  • Dòng tiếp theo chứa n số nguyên có được sắp không giảm có giá trị tuyệt đối không vượt quá 10^9
  • Dòng tiếp theo chứa số nguyên dương m là số phần tử của dãy thứ hai (0 < m \le 10^6)
  • Dòng cuối cùng chứa m số nguyên có được sắp không giảm có giá trị tuyệt đối không vượt quá 10^9

Output

Một dãy có n + m phần tử được sắp không giảm là kết quả trộn của hai dãy trên mỗi phần tử cách nhau một khoảng trống

Example

Input

5    
-3 0 2 5 9    
4
1 2 3 4

Output

-3 0 1 2 2 3 4 5 9
tichpx

Comments