Cho một bảng A gồm ~N \times N~ số nguyên (~1 < N \le 500~), các dòng được đánh số từ trên xuống dưới bắt đầu từ 1, các cột được đánh số từ trái qua phải cũng bắt đầu từ 1. Mỗi phần tử trong bảng có giá trị tuyệt đối không vượt quá ~3 \times 10^4~. Bảng B được tạo ra từ bảng A theo quy tắc sắp xếp lại các phần tử trong A theo thứ tự không giảm, lần lượt ghi vào bảng B theo từng hàng.

Yêu cầu: Hãy viết chương trình tạo ra bảng B tương ứng với bảng A đã cho.

Input

• Dòng đầu tiên chứa số ~N~;
• ~N~ dòng tiếp theo, mỗi dòng chứa ~N~ số nguyên lần lượt là các phần tử trên dòng thứ ~i~ (~i=1 \dots N~) của bảng A.

Output

• Ghi ra bảng B tìm được (các số trên cùng một dòng cách nhau một khoảng trắng).

Mai và Lan cùng nhau chơi trò chơi tìm mật mã. Mật mã cần tìm được ẩn giấu trong các thông điệp. Mỗi thông điệp là một xâu ký tự gồm các chữ cái tiếng Anh từ A đến Z. Quy luật để tìm ra mật mã đó là: ghép lần lượt các ký tự được xuất hiện với số lần nhiều nhất (bằng nhau) thì ký tự được chọn là ký tự đầu tiên theo thứ tự từ điển.

Yêu cầu: Em hãy giúp bạn Mai và Lan tìm ra mật mã nhanh nhất.

Input

• Dòng đầu tiên chứa số nguyên dương ~N~ là số lượng thông điệp (~N < 100~);
• Dòng thứ ~i~ trong ~N~ dòng tiếp theo, mỗi dòng là một thông điệp thứ ~i~ (với ~i = 1 \dots N~) có độ dài không quá ~255~ ký tự.

Output

• Ghi ra một xâu ký tự là mật mã tìm được.

Sample Input 1

4
ACADDD
BCCC
BAAADBFF
CBBFGFC

Sample Output 1

DCAB

Mai chuẩn bị tham gia kỳ thi Tin học trẻ của tỉnh. Trong quá trình ôn tập Mai gặp phải một bài toán khó nhưng chưa có cách giải quyết. Em hãy giúp Mai giải bài toán sau:

Cho ~N~ đoạn thẳng trên trục số với các điểm đầu ~x_i~ và độ dài ~d_i~ là những số nguyên (~-10000 < x_i < 10000~; ~1 \le d_i \le 10^3~; ~i=1 \dots N~).

Yêu cầu: Tính tổng chiều dài phần được bao phủ trên trục số bởi các đoạn thẳng đã cho.

Input

• Dòng đầu tiên chứa số nguyên dương ~N~ (~1 < N \le 1000~);
• ~N~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~x_i~ và ~d_i~ cho biết điểm đầu và chiều dài của đoạn thứ ~i~ (~i=1 \dots N~), hai số cách nhau một khoảng trắng.

Output

• Ghi ra số ~T~ là tổng chiều dài phần được bao phủ trên trục số bởi các đoạn thẳng đã cho.

Trang trại nhà ông John trồng ~N~ cây xanh dọc theo hàng rào, để làm bóng mát cho đàn gia súc trú ẩn vào mùa nắng. Hàng cây được đánh số theo thứ tự từ 1 đến ~N~ và có giá trị lần lượt là ~A_1, A_2, \dots, A_N~. Sau một thời gian dài các cây phát triển tán của chúng đan xen vào nhau. Ông lo sợ cứ để như vậy dễ phát sinh sâu bệnh cho gia súc, hơn nữa vào mùa mưa bão có thể gãy cành, ngã đổ. Sau thời gian suy nghĩ, ông quyết định cắt bỏ một số cây. Các cây giữ lại thỏa mãn các điều kiện sau:

• Cây thứ ~M~ phải được giữ lại;
• Cây bên phải có giá trị lớn hơn hoặc bằng cây bên trái;
• Số lượng cây giữ lại nhiều nhất có thể.

Yêu cầu: Hãy giúp ông John thực hiện điều đó.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~N~ và ~M~ (~0 < M \le N \le 10^6~);
• Dòng thứ hai chứa ~N~ số nguyên dương ~A_1, A_2, \dots, A_N~ (~0 < A_i \le 10^9~; ~i=1 \dots N~).

Output

• Ghi ra một số nguyên dương duy nhất là số lượng cây giữ lại nhiều nhất thỏa mãn các điều kiện trên.