Có N người được đánh số từ 1 đến N đứng thành một vòng tròn. Bắt đầu từ người số 1, người ta đếm theo chiều kim đồng hồ, cứ đếm đến người thứ K thì loại người đó ra khỏi vòng tròn. Quá trình lặp lại bắt đầu đếm từ người kế tiếp người vừa bị loại, cho đến khi chỉ còn đúng 1 người sống sót. Hãy tìm mã số của người sống sót cuối cùng.

Input: Hai số nguyên N, K (1 <= N <= 10^5, 1 <= K <= 10^5).

Output: Mã số của người cuối cùng.

Ví dụ:

Input:

5 2

Output:

3

(Giải thích: Loại 2, loại 4, loại 1, loại 5. Người còn lại là số 3).

Một con phố được biểu diễn bằng một tia số. Trên con phố có N ngôi nhà nằm ở các tọa độ X_i. Công ty muốn xây dựng K trạm phát sóng Wifi. Bạn có thể đặt trạm ở bất kỳ tọa độ nào (kể cả số thập phân). Hãy tìm bán kính phủ sóng R nhỏ nhất sao cho tất cả N ngôi nhà đều được phủ sóng bởi ít nhất 1 trạm. Trạm có bán kính R đặt tại vị trí P sẽ phủ sóng được đoạn [P - R, P + R].

Input:

Dòng 1: N, K (1 <= K <= N <= 10^5).

Dòng 2: N số nguyên Xi (0 <= Xi <= 10^9).

Output: Bán kính R nhỏ nhất (nhân kết quả với 10 và in ra phần nguyên để tránh sai số thập phân. Ví dụ R=2.5 thì in 25).

Ví dụ:

Input:

3 2
1 5 10

Output:

20

(Giải thích: Đặt trạm tại 3 (phủ 1 và 5, bán kính 2). Đặt trạm tại 10 (bán kính 0). Bán kính lớn nhất phải dùng là 2. Nhân 10 in ra 20).

Bài kiểm tra thể lực gồm N hạng mục, hạng mục thứ i nếu hoàn thành sẽ mang lại Vi điểm, nhưng sẽ làm tiêu hao Wi phần trăm thể lực. Thể lực ban đầu của bạn là 100%. Bạn hãy chọn ra các hạng mục để thực hiện sao cho tổng phần trăm thể lực tiêu hao không vượt quá 100%, và tổng điểm thu được là lớn nhất. Mỗi hạng mục chỉ được thực hiện tối đa 1 lần.

Input:

Dòng 1: N (1 <= N <= 100).

N dòng tiếp theo: Mỗi dòng 2 số nguyên Wi, Vi (1 <= Wi <= 100, 1 <= Vi <= 10^4).

Output: Tổng điểm lớn nhất.

Ví dụ:

Input:

3
40 50
50 60
70 80

Output:

110

(Giải thích: Chọn hạng mục 1 và 2. Thể lực tiêu hao: 90%. Điểm: 50 + 60 = 110).

Một ngày nọ, Vasya quyết định xem xét kết quả trận chung kết Giải vô địch bóng đá Berland 1910. Thật không may, anh ta đã không tìm thấy điểm tổng thể của trận đấu; tuy nhiên, anh ta đã nắm giữ một mô tả sâu sắc về quá trình của trận đấu. Trên tổng thể có n dòng trong mô tả đó mỗi dòng mô tả một đội ghi bàn. Giúp Vasya, tìm hiểu tên của đội đã giành chiến thắng trong trận chung kết. Nó được đảm bảo rằng trận đấu đã không kết thúc hòa.

Đầu vào:

• Dòng đầu tiên chứa một số nguyên n (1<=n<=100) - số lượng dòng trong mô tả.
• Sau đó theo n dòng - cho mỗi bàn thắng tên của các đội đã ghi nó. Tên là các dòng không trống bao gồm các chữ cái Latinh viết hoa có độ dài không vượt quá 10 ký hiệu. Nó được đảm bảo rằng trận đấu không kết thúc bằng hòa và mô tả không chứa nhiều hơn hai đội khác nhau.

Đầu ra: In tên của đội chiến thắng. Chúng tôi nhắc nhở bạn rằng trong bóng đá, đội nào ghi được nhiều bàn thắng hơn được coi là người chiến thắng.

Input 01:

1
ABC

Output 01:

ABC

Input 02:

5
A
ABA
ABA
A
A

Output 02:

A