Prepare for SAM

Sử dụng đệ quy để cài đặt phương pháp Sắp xếp chèn (Insertion Sort) nhằm sắp xếp một dãy cho trước.

Lưu ý rằng hệ thống chỉ có thể kiểm tra tính đúng/sai của kết quả sắp xếp chứ không thể kiểm tra tính chính xác của phương pháp. Do vậy, người làm bài cần phải "fair play", thực hiện đúng phương pháp được yêu cầu. Mặt khác, người giám sát có thể xem lại mã của những lời giải đúng (Accepted) để kiểm tra xem người làm có tuân thủ đúng yêu cầu về mặt phương pháp hay không.

Input

Dòng 1: số nguyên n - kích thước của dãy
Dòng 2: dãy S1 gồm n số nguyên
Dòng 3: dãy S2 gồm n số nguyên

Output

Dòng 1: Dãy S1 được sắp xếp tăng dần
Dòng 2: Dãy S2 được sắp xếp giảm dần 

Example

Input:
10
23 2 44 7 37 15 37 48 9 0 
24 29 13 38 34 7 11 18 41 16 

Output:
0 2 7 9 15 23 37 37 44 48 
41 38 34 29 24 18 16 13 11 7