Sắp xếp cơ bản

Trong một vương quốc toán học, nhà vua tổ chức một cuộc thi để tìm ra những phân số "quyền lực" nhất. Mỗi phân số thứ \(i\) được đại diện bởi một cặp số nguyên dương \((x_i, y_i)\), trong đó \(x_i\) là tử số và \(y_i\) là mẫu số.

Nhiệm vụ của bạn là giúp nhà vua sắp xếp danh sách \(n\) phân số này theo thứ tự giảm dần về giá trị. Trong trường hợp có hai hoặc nhiều phân số có giá trị bằng nhau, phân số nào có tổng tử số và mẫu số (\(x_i + y_i\)) lớn hơn sẽ được ưu tiên đứng trước.

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) (\(n \leq 10^5\)).
• \(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(x_i\) và \(y_i\) (\(x_i, y_i \leq 10^9\)) lần lượt là tử số và mẫu số của phân số thứ \(i\).

Output

• In ra \(n\) dòng, mỗi dòng gồm hai số \(x_i\) và \(y_i\) của các phân số sau khi đã được sắp xếp theo quy tắc trên.

Constraints

• Subtask \(1\) (\(40\%\) số điểm): \(n \leq 10^3\) và \(x_i, y_i \leq 10^3\).
• Subtask \(2\) (\(60\%\) số điểm): Không có ràng buộc gì thêm.

Example

4
1 2
2 4
3 4
1 3

3 4
2 4
1 2
1 3

Trong một vương quốc nọ, các con số đang chuẩn bị tham gia một buổi dạ tiệc hoàng gia. Để buổi tiệc diễn ra trang trọng, Đức vua ban lệnh sắp xếp các con số theo một quy tắc đặc biệt:

• Các con số lẻ (những vị khách danh dự) phải được đứng trước các con số chẵn (những người phục vụ).
• Trong nhóm các số lẻ, các con số phải được sắp xếp theo thứ tự tăng dần.
• Trong nhóm các số chẵn, các con số phải được sắp xếp theo thứ tự giảm dần.

Cho một dãy gồm \(n\) số nguyên \(a_i\), bạn hãy giúp Đức vua sắp xếp lại dãy số này theo đúng quy tắc trên.

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) (\(1 \le n \le 10^5\)).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^6\)).

Output

• In ra dãy số sau khi đã được sắp xếp theo yêu cầu của Đức vua. Các số cách nhau bởi một khoảng trắng.

Example

6
1 4 3 2 5 6

1 3 5 6 4 2

Constraints

• Subtask \(1\) (\(40\%\) số điểm): \(n \le 10^3\).
• Subtask \(2\) (\(60\%\) số điểm): Không có ràng buộc gì thêm.

Trong một vương quốc nọ, nhà vua sở hữu một bộ sưu tập các viên ngọc quý, mỗi viên ngọc được khắc một mã số nguyên. Để chuẩn bị cho lễ hội hoàng gia, nhà vua muốn người quản kho sắp xếp lại các viên ngọc này theo một quy tắc đặc biệt:

1. Những viên ngọc có tần suất xuất hiện nhiều hơn (số lượng nhiều hơn) sẽ được ưu tiên xếp trước.
2. Nếu có nhiều loại ngọc có cùng tần suất xuất hiện, loại ngọc nào có mã số lớn hơn sẽ được ưu tiên xếp trước.

Bạn hãy giúp người quản kho thực hiện nhiệm vụ này.

Input

• Dòng đầu tiên chứa một số nguyên dương \(n\) (\(1 \le n \le 10^5\)) là số lượng viên ngọc.
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(|a_i| \le 10^9\)) là mã số của các viên ngọc.

Output

• In ra một dòng duy nhất chứa \(n\) số nguyên là mã số của các viên ngọc sau khi đã được sắp xếp theo yêu cầu của nhà vua.

Example

7
1 3 2 2 1 3 4

3 3 2 2 1 1 4

5
5 5 1 2 2

5 5 2 2 1

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(n \le 10^3, |a_i| \le 10^3\).
• Subtask \(2\) (\(60\%\) số điểm): Không có ràng buộc gì thêm.

Cho \(n\) số nguyên dương \(a_1,a_2,...,a_n\), mỗi số không vượt quá \(10^7\). Từ các số này người ta có thể tạo ra một số nguyên mới bằng cách ghép tất cả các số đã cho, tức là viết liên tiếp các số đã cho với nhau. Ví dụ với dãy số \([123,124,56,90]\) ta có thể tạo ra các số mới sau: \(1231245690,1241235690,...\). Trong các số trên, số lớn nhất có thể tạo ra được là \(9056124123\).

Yêu cầu: Cho \(n\) và các số \(a_1,a_2,...,a_n\). Hãy xác định số lớn nhất có thể tạo được theo cách trên.

Input

• Dòng 1: \(n\) \((1 \le n \le 100)\)
• Dòng 2: \(a_1,a_2,...,a_n\) \((1 \le a_i \le 10^5)\)

Output

• Đáp án

Example

4
557 92 19 47

925574719

4
1 1 1 1

1111

Vào một buổi sáng, anh Bo sắp một đàn bò gồm \(n\) con bò để vắt sữa. Anh dự kiến là vào sáng hôm đó, con bò thứ \(i\) có khả năng sẽ vắt được \(a_i\) lít sữa. Tuy nhiên đàn bò của anh có đặc tính là cứ mỗi lần vắt sữa một con, những con còn lại trông thấy sợ quá nên sẽ bị giảm sản lượng mỗi con \(1\) lít sữa.

Nếu vắt sữa con bò thứ nhất, \(n-1\) con còn lại bị giảm sản lượng. Sau đó vắt sữa con bò thứ hai thì \(n-2\) con còn lại bị giảm sản lượng... Bạn hãy giúp anh Bo tính xem thứ tự vắt sữa bò như thế nào để số lượng sữa vắt được là nhiều nhất nhé.

Lưu ý: Sản lượng sữa của một con bò không thể xuống dưới mức \(0\).

Input

• Dòng thứ nhất là số nguyên \(n\) (\(1 \le n \le 10^5\)) là số lượng con bò.
• Dòng thứ hai gồm \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^9\)) là sản lượng sữa ban đầu của các con bò.

Output

• Một số nguyên duy nhất xác định số lít sữa nhiều nhất mà anh Bo có thể vắt được.

Example

4
4 4 4 4

10

4
2 1 4 3

6