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 đầu vào

Gồm một dòng chứa ~4~ số nguyên ~a,\ b,\ c,\ d~ ~(0 < a, b, c, d \le 10^5)~.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là kết quả tìm được.

Ví dụ

Ví dụ 1

INPUT

7 3 4 6

OUTPUT

18

Ví dụ 2

INPUT

5 5 5 5

OUTPUT

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 đầu vào

Gồm hai dòng:

• 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 \le~ độ 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ố.

Dữ liệu đầu ra

Gồm một dòng duy nhất chứa kết quả cần tìm.

Ràng buộc dữ liệu

• Có 40% số điểm có độ dài xâu ~ST \le 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.

Ví dụ

Ví dụ 1

INPUT

AmN69pQ3e6
2

OUTPUT

96

Ví dụ 2

INPUT

Fish36colo99
3

OUTPUT

699

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 \le i \le j \le 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 đầu vào

Gồm hai dòng:

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

Dữ liệu đầu ra

Gồm kết quả theo yêu cầu bài toán.

Ràng buộc dữ liệu

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

Ví dụ

Ví dụ 1

INPUT

8
1 0 0 1 1 0 0 0

OUTPUT

6

Bội số chung nhỏ nhất của hai 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 \le 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 đầu vào

Gồm hai dòng:

• Dòng đầu ghi số nguyên dương ~T~ ~(T \le 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 \le a \le b \le 10^6)~.

Dữ liệu đầu ra

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~.

Ràng buộc dữ liệu

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

Ví dụ

Ví dụ 1

INPUT

2
3 4
7 7

OUTPUT

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ố số thỏa mãn: ~(1, 7)~; ~(7, 1)~; ~(7, 7)~.