Biết Nam đang ôn tập để tham gia kỳ thi học sinh giỏi cấp tỉnh môn Tin học. Bố đã đố bạn ấy lập trình để giải bài toán có nội dung như sau: Cho 4 thanh sắt có độ dài lần lượt là a, b, c, d. Bố muốn Nam tạo một khung hình chữ nhật từ 4 thanh sắt đó (phải sử dụng cả 4 thanh), những đoạn dư của các thanh sắt (nếu có) sẽ bị cắt bỏ. Hãy tìm diện tích lớn nhất của khung sắt được tạo thành.

Yêu cầu: Em hãy giúp bạn Nam giải bài toán trên.

Dữ liệu vào: Đọc từ tệp CAU1.INP gồm một dòng chứa 4 số nguyên a, b, c, d (0 < a, b, c, d ≤ 105).

Kết quả: Ghi ra tệp CAU1.OUT một số nguyên duy nhất là kết quả tìm được.

Ví dụ:

CAU1.INP    
    7 3 4 6
    5 5 5 5 
CAU1.OUT
    18
    25

Việt và Nam cùng nhau ôn luyện về chủ đề xâu kí tự. Để buổi học trở nên thú vị hơn, mỗi bạn sẽ lần lượt đưa ra một bài toán dành cho bạn của mình. Bài toán của Việt dành cho Nam như sau: Cho một xâu ST bao gồm các kí tự chữ cái tiếng Anh (thường và hoa) và các kí tự số. Hãy thực hiện xóa đi các kí tự trong xâu ST để được một xâu mới ST1 chỉ còn K kí tự đều là kí tự số và khi giữ nguyên trật tự như ban đầu thì xâu ST1 tạo thành một số lớn nhất.

Yêu cầu: Em hãy giúp Nam tìm ra xâu ST1 theo đúng yêu cầu.

Dữ liệu vào: Đọc từ tệp CAU2.INP có cấu trúc như sau:

• Dòng 1: Chứa một xâu ST (độ dài không quá 10^5).
• Dòng 2: Chứa số nguyên dương K (K ≤ độ dài xâu ST). Biết rằng trong xâu ST luôn đảm bảo có ít nhất K kí tự số.

  Kết quả: Ghi ra tệp CAU2.OUT gồm một dòng duy nhất chứa kết quả cần tìm.

Ví dụ:

CAU2.INP
    AmN69pQ3e6
    2
CAU2.OUT
96

CAU2.INP
   Fish36colo99
   3
CAU2.OUT
    699

Ràng buộc:

• Có 40% số điểm có độ dài xâu ST ≤ 18 và xâu chỉ có kí tự số;
• Có 60% số điểm còn lại không có ràng buộc gì thêm.

Có n chiếc hộp được đánh số theo thứ tự từ 1 đến n và xếp chúng theo một hàng ngang. Mỗi chiếc hộp có một trong hai giá trị 0 hoặc 1. Thực hiện một lần thay đổi giá trị của tất cả các hộp từ vị trí i, j (1 ≤ i ≤ j ≤ n) theo quy tắc 'Những hộp có giá trị bằng 1 sẽ được thay đổi bằng 0 và ngược lại', để sau khi thay đổi thì trong n chiếc hộp nhận được số chiếc hộp có giá trị bằng 1 là nhiều nhất.

Yêu cầu: Đếm số hộp có giá trị bằng 1 nhiều nhất sau khi thay đổi như trên.

Dữ liệu vào: Đọc từ tệp CAU3.INP có cấu trúc như sau:

• Dòng 1: Chứa số nguyên dương n (0 < n ≤ 10^6).
• Dòng 2: Chứa giá trị ban đầu của n chiếc hộp.

  Kết quả: Ghi ra tệp CAU3.OUT kết quả theo yêu cầu bài toán.

Ví dụ:

CAU3.INP    
    8
    1 0 0 1 1 0 0 0 
CAU3.OUT
    6

Ràng buộc:

• Có 30% số điểm của bài có 1 ≤ n ≤ 500;
• Có 30% số điểm tiếp theo của bài có 500 < n ≤ 8000;
• Có 40% số điểm còn lại của bài có 8000 < n ≤ 10^6.

Bội số chung nhỏ nhất của 2 số nguyên dương x và y là số nguyên dương nhỏ nhất chia hết cho cả x và y, kí hiệu LCM(x,y). Cho hai số nguyên dương a và b (a ≤ b).

Yêu cầu: Hãy đếm số cặp số nguyên dương x, y sao cho LCM(x, y) bằng tích các số nguyên liên tiếp từ a đến b (trường hợp a bằng b thì tích này bằng a).

Dữ liệu vào: Đọc từ tệp CAU4.INP có cấu trúc như sau:

• Dòng đầu ghi số nguyên dương T (T ≤ 10) là số test.
• T dòng tiếp theo, mỗi dòng là một test chứa hai số nguyên dương a, b (1 ≤ a ≤ b ≤ 10^6).

  Kết quả: Ghi ra tệp CAU4.OUT gồm T dòng, mỗi dòng là phần dư của kết quả tìm được khi chia cho 10^9 + 7.

Ví dụ:

CAU4.INP
    2
    3 4
    7 7 
CAU4.OUT
    15
    3   
Giải thích
    - Test 1 có 15 cặp số thỏa mãn: (1,12); (2,12); (3, 4);
    (3,12); (4,3); (4,6); (4,12); (6,4); (6,12); (12,1); (12,2); (12,3); (12,4); (12,6); (12,12)
    - Test 2 có 3 cặp số thỏa mãn: (1, 7); (7, 1); (7, 7).

Ràng buộc:

• Có 40% số điểm của bài có a,b ≤ 10;
• Có 30% số điểm tiếp theo của bài có a,b ≤ 100;
• Có 30% số điểm còn lại của bài không có ràng buộc gì thêm.