Phần mềm phân tích văn bản nhận được một chuỗi S chứa các từ tiếng Anh phân tách nhau bởi dấu cách. Hệ thống bỏ qua sự khác biệt giữa chữ hoa và chữ thường (ví dụ "Apple" và "apple" được coi là cùng một từ). Bạn hãy tìm từ xuất hiện nhiều lần nhất trong chuỗi S. Nếu có nhiều từ cùng có tần suất lớn nhất, in ra từ có thứ tự từ điển nhỏ nhất. (In kết quả bằng chữ in thường).

Input: Một chuỗi S (độ dài <= 10^5, chứa các chữ cái và dấu cách).

Output: Từ xuất hiện nhiều nhất bằng chữ in thường.

Ví dụ:

Input:

To be or not to be

Output:

be

Cho một xâu S chỉ gồm chữ cái in thường và một số nguyên K. Hãy tìm xâu con liên tiếp dài nhất của S sao cho xâu con này chứa đúng K loại ký tự khác nhau.

Input:

Dòng 1: Xâu S (Độ dài <= 10^5).

Dòng 2: Số nguyên K (1 <= K <= 26).

Output: Độ dài của xâu con liên tiếp lớn nhất thỏa mãn. Nếu không tồn tại xâu con nào có đúng K loại ký tự, in ra -1.

Ví dụ:

Input:

eceba
2

Output:

3

(Giải thích: Xâu con "ece" có độ dài 3 và chứa đúng 2 ký tự khác nhau là 'e' và 'c').

Trong phòng thi có 2 máy in. Máy in A cần X giây để in ra một trang giấy, máy in B cần Y giây để in ra một trang giấy. Các thầy cô cần in gấp N trang đề thi. Cả hai máy có thể hoạt động cùng lúc để tối ưu thời gian. Hãy tính xem mất ít nhất bao nhiêu giây để in xong N trang đề thi.

Input: 3 số nguyên N, X, Y (1 <= N <= 10^9, 1 <= X, Y <= 1000).

Output: Thời gian ít nhất tính bằng giây.

Ví dụ:

Input:

5 2 3

Output:

6

(Giải thích: Trong 6 giây, máy A in được 3 trang, máy B in được 2 trang. Tổng là 5 trang).

Để vượt qua cánh cửa ma thuật, bạn cần trả đúng một lượng vàng là S. Bạn đang có N loại đồng xu, loại thứ i có giá trị Vi và bạn có chính xác Ci đồng xu loại đó. Bạn có bao nhiêu cách để lấy ra các đồng xu sao cho tổng giá trị của chúng đúng bằng S? Hai cách lấy được coi là khác nhau nếu số lượng đồng xu của ít nhất một loại là khác nhau. In kết quả lấy dư cho 10^9+7.

Input:

Dòng 1: N, S (1 <= N <= 100, 1 <= S <= 10^4).

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

Output: Số cách tạo ra tổng S modulo 10^9+7.

Ví dụ:

Input:

2 5
1 3
2 2

Output:

2

(Giải thích: Cần tổng = 5. Cách 1: dùng 3 xu loại 1 (tổng 3) và 1 xu loại 2 (tổng 2). Cách 2: dùng 1 xu loại 1 (tổng 1) và 2 xu loại 2 (tổng 4)).

Có N chiếc xe ô tô bị hỏng đang dừng trên các điểm đánh số trên đường cao tốc. Chiếc thứ i dừng ở mốc km thứ P_i. Đội cứu hộ cần gom tất cả các xe về cùng một mốc km bất kỳ. Lệ phí cứu hộ rất đặc biệt: Nếu kéo xe di chuyển đi 2 km (ví dụ từ mốc 1 đến mốc 3), chi phí là 0 đồng. Nếu kéo xe di chuyển đúng 1 km (từ 1 đến 2), chi phí là 1 đồng. Hãy tìm chi phí nhỏ nhất để gom N xe về chung một mốc.

Dữ liệu vào:

Dòng 1: Số N (1 <= N <= 10^5).

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

Kết quả ra: Chi phí nhỏ nhất.

Ví dụ:

Input:

3
1 2 3

Output:

1