Do trúng tuyển vào lớp 10 chuyên Tin học với số điểm cao, Minh được bố mẹ cho đi chơi Cồn Nổi. Tại đây, Minh nhặt được một số vỏ ốc có màu trắng và một số vỏ ốc có màu xám. Khi về nhà, Minh quyết định xâu những vỏ ốc này thành các chuỗi vòng để tặng bạn. Biết rằng số vỏ ốc màu trắng là m, số vỏ ốc màu xám là n và Minh dùng tất cả số vỏ ốc mà mình đã nhặt được để xâu các chuỗi vòng.

Yêu cầu:

Hãy giúp Minh chia các vỏ ốc này thành nhiều chuỗi nhất sao cho tất cả các chuỗi vòng này có số vỏ ốc mỗi màu đều bằng nhau.

Dữ liệu:

Gồm hai số nguyên không âm m và n cách nhau một khoảng trắng ~(0 \le m,n \le 10^{18})~ , lần lượt là số lượng vỏ ốc màu trắng và vỏ ốc màu xám.

Kết quả:

Ghi một số nguyên là số lượng chuỗi nhiều nhất có thể.

Ví dụ:

Giải thích:

Có 2 cách để xâu các chuỗi:

• Cách 1: Chỉ xâu 1 chuỗi có 10 vỏ ốc màu trắng và 6 vỏ ốc màu xám;
• Cách 2: Xâu thành 2 chuỗi, mỗi chuỗi đều có 5 vỏ ốc màu trắng và 3 vỏ ốc màu xám; Chọn cách 2 vì số lượng chuỗi nhiều hơn.

Ràng buộc:

• Có 20% số test tương ứng 20% số điểm với ~0 \le m,n\lt 10^3~
• Có 40% số test tương ứng 40% số điểm với ~10^3 \le m,n\lt 10^9~
• Có 40% số test tương ứng 40% số điểm với ~10^9 \le m,n\le 10^{18}~

Để làm quen với bài tập lập trình về kí tự, thầy giáo giao cho các bạn làm bài tập sau: Cho một dãy kí tự là các chữ cái Latinh in hoa. Hãy in ra các kí tự có số lần xuất hiện không nhỏ hơn k trong dãy trên theo thứ tự từ điển.

Yêu cầu:

Hãy lập trình giải bài toán trên.

Dữ liệu:

• Dòng đầu chứa hai số nguyên dương n và k cách nhau một khoảng trắng, trong đó n là số lượng kí tự của dãy và k là số lần xuất hiện cần phải đếm. ~(1 \le k\le10^6)~
• Dòng thứ 2 chứa n kí tự là chữ cái Latinh in hoa viết liền nhau.

Kết quả:

Một dãy các kí tự có số lần xuất hiện không nhỏ hơn k và được sắp xếp theo thứ tự từ điển. Trường hợp không có kí tự nào thỏa mãn thì ghi một số 0.

Ví dụ:

Giải thích:

Ràng buộc:

• 20% số điểm với ~(1 \le k \le n \lt 10^2)~
• 40% số điểm với ~(10^2 \le k \le n \lt 10^4)~
• 40% số điểm với ~(10^4 \le k \le n \le 10^6)~

Dự đoán đến thế kỉ XXII, người ta sẽ chế tạo được một tàu vũ trụ đặc biệt để đưa người, hàng hóa, thiết bị từ Trái Đất lên Sao Hỏa. Để đảm bảo an toàn, trong lần thử nghiệm, người ta lập trình cho con tàu chuyển động tự động mỗi giây đi được k (m) theo đường thẳng và bố trí một tàu giám sát đi cùng để chụp ảnh (mỗi giây chụp 01 ảnh). Tàu giám sát sẽ chuyển động với tốc độ thay đổi để có thể chụp ảnh con tàu thử nghiệm ở nhiều vị trí khác nhau (gần, xa, từ phía trước và từ phía sau) để gửi về Trái Đất. Ảnh chụp được là rõ nét nếu như khoảng cách giữa hai tàu không vượt quá p (m).

Yêu cầu:

Hãy tính trong thời gian chuyển động, tàu giám sát chụp được bao nhiêu ảnh rõ nét của tàu thử nghiệm. Biết rằng cả hai con tàu xuất phát cùng thời điểm và ở hai bệ phóng gần nhau.

Dữ liệu:

• Dòng đầu chứa 3 số nguyên dương n, k, p với n là thời gian di chuyển của các tàu, k là quãng đường đi được trong 1 giây của con tàu thử nghiệm và p là khoảng cách tối đa cho ảnh rõ nét của máy ảnh.~(5 \le n \le 10^6 ; 1\le k, p \le 10^3)~ ;
• Dòng tiếp theo là n số nguyên dương a1, a2, …an, trong đó ai là quãng đường mà tàu giám sát đi được trong giây thứ i. ~(1\le i \lt n, 1\le a_i \le 10^3)~ ; (Các số trên cùng một dòng cách nhau một khoảng trắng).

Kết quả:

Ghi một số duy nhất là số lượng ảnh rõ nét chụp được.

Ví dụ:

Giải thích:

Ràng buộc:

• 20% số điểm với ~(5 \le n \lt 10^2)~
• 40% số điểm với ~(10^2 \le n \lt 10^4)~
• 40% số điểm với ~(10^4 \le n \le 10^6)~

Một kho hàng lớn chứa nhiều kiện hàng có khối lượng khác nhau. Để chuyển hết hàng trong kho đến bến cảng người ta dùng các xe tải có sức chở bằng nhau. Xếp xong hàng vào xe tải này rồi mới tiếp tục xếp hàng vào xe tải khác. Do phải đi qua một tuyến đường đang sửa chữa nên cần phải bố trí xe tải có sức chở nhỏ nhất có thể để vận chuyển hàng.

Yêu cầu:

Cho biết thứ tự và khối lượng các kiện hàng được lấy ra từ kho. Tính xe tải có sức chở nhỏ nhất là bao nhiêu để khi xếp hàng, tất cả các xe tải đều được xếp vừa đủ sức chở mà không phải chia nhỏ các kiện hàng.

Dữ liệu:

• Dòng thứ nhất chứa 1 số nguyên dương n là số lượng kiện hàng của kho; ~(5 \le n \le 10^6)~
• Dòng thứ 2 chứa n số nguyên dương a1, a2,..an (mỗi số cách nhau một khoảng trắng), trong đó ai là khối lượng của kiện hàng thứ i. ~(1 \le i \le n; 1 \le a_i \le 10^{18})~

Kết quả:

Ghi một số nguyên duy nhất là sức chở của xe tải được bố trí.

Ví dụ:

Giải thích:

Ràng buộc:

• 20% số điểm với ~(5 \le n \lt 10^2 ; 1 \le a_i \lt 10^9)~
• 40% số điểm với ~(10^2 \le n \lt 10^4 ; 1 \le a_i \lt 10^9)~
• 20% số điểm với ~(10^4 \le n \lt 10^6 ; 1 \le a_i \lt 10^9)~
• 20% số điểm với ~(10^4 \le n \lt 10^6 ; 10^9 \le a_i \lt 10^{18})~