Tuy là 1 cô gái nhưng Annie lại đam mê với môn học đánh bài, vì đang là sinh viên ngành CNTT nên cô nghĩ ra 1 trò chơi.

Cô có N lá bài được đánh số là ~a_{1},a_{2}....a_{n}~ và ~N~ lá bài đã được sắp xếp sẵn và cô cho thêm 1 quân bài ~ x~

Yêu cầu của Annie là làm sao để đưa quân bài ~x~ vào bộ bài để dãy sau khi được thêm vẫn là dãy tăng dần.

Input

• Dòng 1 chứa 1 số nguyên duy nhất ~N~ là số lượng quân bài ~(1, \le N \le 10000)~.
• Dòng thứ 2 chứa ~N~ số nguyên ~a_i~ ~(1 \le a_{i} \le 10000)~ là số ghi trên lá bài
• Dòng thứ 3 chứa số nguyên là ~x~ ~(0 \le x\le 10000)~ là lá bài được thêm

Output

In ra màn hình mảng sau khi đã được thêm phần tử ~x~

Sample

Input #1

5
1 2 3 8 9
5

Output #1

1 2 3 5 8 9 

Problem source: CLB Lập Trình PTIT