Sau khi học về thuật toán sắp xếp, thầy giáo giao cho Tí bài tập sau: Em hãy nhập vào một dãy gồm \(n\) số tự nhiên có giá trị không quá \(10^{8}\), sắp xếp các số theo thứ tự tăng dần, nhưng số lẻ phải xếp trước số chẵn. Sau đó ghi ra số có nhiều ước nhất trong các số vừa nhập vào. Dù thông minh, nhưng vì ham chơi nên Tí không nhớ cách cài đặt thuật toán để giải đáp yêu cầu của thầy. Em hãy giúp Tí nhé!

Dữ liệu vào:

+ Dòng đầu tiên là số tự nhiên \(n\ (1 \leq n \leq 10^{4})\);

+ Dòng tiếp theo chứa \(n\) số tự nhiên là các số thầy giáo đưa ra.

Kết quả ra:

+ Dòng đầu là \(n\) số đã được sắp xếp tăng dần, số lẻ trước, số chẵn sau.

+ Dòng tiếp theo ghi số tự nhiên có nhiều ước nhất trong \(n\) số nhập vào.

Ví dụ 1:

Ví dụ 2: