Bác Kim có một khu vườn hình chữ nhật có kích thước hai chiều ~a~ và ~b~ (đơn vị: mét). Bác muốn lấy ra từ khu vườn ban đầu một mảnh vườn hình vuông có diện tích lớn nhất để trồng nhãn.

Yêu cầu

Hãy giúp bác Kim tính diện tích của mảnh vườn hình vuông được lấy ra. Trường hợp mảnh vườn của bác Kim đã vuông thì in ra số ~1~.

Dữ liệu đầu vào

Gồm một dòng duy nhất chứa hai số nguyên dương ~a~ và ~b~ ~(1 \le a, b \le 10^9)~ phân biệt với nhau bởi một dấu cách.

Dữ liệu đầu ra

Ghi ra một số nguyên dương là kết quả của bài toán.

Ràng buộc dữ liệu

• Subtask 1 (70% số điểm): ~1 \le a, b \le 10^6~;
• Subtask 2 (30% số điểm): Không có ràng buộc gì thêm.

Ví dụ

Ví dụ 1

INPUT

6 4

OUTPUT

16

Ví dụ 2

INPUT

20 20

OUTPUT

1

Ví dụ 3

INPUT

12 18

OUTPUT

144

Lê Quý Đôn (danh nhân văn hóa, quê huyện Hưng Hà, tỉnh Thái Bình hay thuộc xã Lê Quý Đôn, tỉnh Hưng Yên) là một nhà bác học có kiến thức uyên bác. Ông đã để lại một kho tàng tri thức đồ sộ về văn chương, lịch sử, văn hóa, ... Cuộc đời và sự nghiệp của ông là tấm gương về học tập cho bao thế hệ. Trong một lần ngoại khóa tìm hiểu về Lê Quý Đôn, được truyền cảm hứng, một bạn học sinh đã nghĩ ra một bài toán thú vị như sau:

"Số chính phương là một số nguyên dương có giá trị bằng tích của hai số nguyên bằng nhau. Cho hai số nguyên dương ~L~ và ~R~. Hãy đếm số lượng các số chính phương trong đoạn ~[L; R]~"

Yêu cầu

Hãy giúp bạn học sinh giải bài toán nói trên.

Dữ liệu đầu vào

Gồm một dòng duy nhất chứa hai số nguyên dương ~L~ và ~R~ ~(0 < L \le R \le 10^{18})~ phân biệt với nhau bởi một dấu cách.

Dữ liệu đầu ra

Ghi ra một số nguyên duy nhất là kết quả của bài toán.

Ràng buộc dữ liệu

• Subtask 1 (70% số điểm): ~0 < L \le R \le 10^6~;
• Subtask 2 (30% số điểm): Không có ràng buộc gì thêm.

Ví dụ

Ví dụ 1

INPUT

1 10

OUTPUT

3

Giải thích: Từ ~1~ đến ~10~ có ~3~ số chính phương là ~1; 4; 9~.

Ví dụ 2

INPUT

20 80

OUTPUT

4

Giải thích: Từ ~20~ đến ~80~ có ~4~ số chính phương là ~25; 36; 49; 64~.

Ví dụ 3

INPUT

26 30

OUTPUT

0

Giải thích: Từ ~26~ đến ~30~ không có số chính phương nào.

Văn Miếu Xích Đằng (tọa lạc tại phường Sơn Nam, tỉnh Hưng Yên) được mệnh danh là biểu tượng của nền văn hiến và tinh thần hiếu học Hưng Yên. Nơi đây hiện còn lưu giữ 9 tấm bia đá quý giá ghi danh 161 vị đại khoa của trấn Sơn Nam xưa.

Trong quá trình tu bổ và nghiên cứu văn bia, các nhà khảo cổ phát hiện một bản văn bia cổ có chứa một dòng kí tự ~S~ bí ẩn, bao gồm các kí tự chữ cái Latin và các kí tự chữ số.

Theo quan niệm của người xưa, "Con số may mắn" giúp sĩ tử đỗ đạt là một số nguyên dương đối xứng lớn nhất có trong dòng kí tự đó.

Yêu cầu

Gồm một dòng duy nhất chứa xâu ~S~ (độ dài xâu ~S~ không quá ~10^5~ kí tự).

Dữ liệu đầu ra

Ghi ra số đối xứng lớn nhất tìm được. Nếu không có, ghi ~-1~.

Ràng buộc dữ liệu

• Subtask 1 (50% số điểm): Độ dài xâu ~S~ không quá ~255~ kí tự, số tạo được trong xâu có không quá ~18~ chữ số;
• Subtask 2 (30% số điểm): Độ dài xâu ~S~ không quá ~10^5~ kí tự, số tạo được trong xâu có không quá ~18~ chữ số;
• Subtask 3 (20% số điểm): Độ dài xâu ~S~ không quá ~10^5~ kí tự, số tạo được trong xâu có thể rất lớn.

Ví dụ

Ví dụ 1

INPUT

sonnam13331hungyen0990

OUTPUT

13331

Giải thích: Các số có trong xâu là ~13331~ và ~990~. Trong đó ~13331~ là số đối xứng còn ~990~ không là số đối xứng, nên kết quả là ~13331~.

Ví dụ 2

INPUT

van5bia009009asonam

OUTPUT

9009

Giải thích: Các số có trong xâu là ~5~ và ~9009~. Trong đó ~5~ và ~9009~ đều là số đối xứng. Số ~9009~ là số đối xứng lớn nhất nên kết quả là ~9009~.

Ví dụ 3

INPUT

lequydonhunghasonnam

OUTPUT

-1

Giải thích: Không có số đối xứng nào trong xâu nên kết quả là ~-1~.

Cồn Vành (thuộc huyện Tiền Hải, tỉnh Thái Bình cũ nay thuộc xã Hưng Phú, tỉnh Hưng Yên) là khu vực cửa sông ven biển với hệ sinh thái rừng ngập mặn phong phú và những hàng phi lao chắn cát trải dài. Rừng cây phi lao không những là nơi chắn gió, chắn cát mà còn cung cấp gỗ giúp người dân dựng nhà, làm vật dụng.

Qua nghiên cứu của các kỹ sư lâm nghiệp, các cây phi lao lớn rất đều, mỗi ngày chiều cao của mọi cây đều tăng thêm đúng ~1~ cm. Để phục vụ công việc của mình, ban quản lý cần một lượng gỗ với tổng chiều dài ít nhất là ~m~ (cm) được khai thác từ khu rừng nói trên.

Quy tắc khai thác như sau:

• Chỉ được cắt khi cây có chiều cao lớn hơn ~c~ (cm) để đảm bảo mỹ quan và phần gốc còn lại vẫn đủ sức chắn gió, chắn cát.
• Để bảo tồn mật độ rừng, chỉ được phép khai thác tối đa ~k~ cây.

Yêu cầu

Trong một khu rừng có ~n~ cây phi lao, cây thứ ~i~ có độ cao ~a_i~. Hãy tính xem sau ít nhất bao nhiêu ngày (tính từ ngày ~0~) thì ban quản lý có thể khai thác để thu được lượng gỗ không nhỏ hơn ~m~ (cm) theo quy tắc trên?

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng 1: Bốn số nguyên dương ~n, m, k, c~ ~(1 \le k \le n \le 10^5; 0 \le m \le 10^{18}; 1 \le c \le 10^{18})~, giữa các số có một dấu cách;
• Dòng 2: ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~ là chiều cao (cm) ban đầu của các cây trong khu rừng ~(1 \le a_i \le 10^{12})~.

Dữ liệu đầu ra

Ghi ra một số nguyên là số ngày ít nhất cần thiết. Nếu ngày ~0~ đã có thể khai thác đủ lượng gỗ ~m~ thì in ra ~0~.

Ràng buộc dữ liệu

• Subtask 1 (40% số điểm): ~1 \le m, c \le 10^4~ và ~1 \le k \le 100~;
• Subtask 2 (30% số điểm): ~1 \le m \le 10^8~ và ~1 \le k \le 10^4~;
• Subtask 3 (30% số điểm): Không có ràng buộc gì thêm.

Ví dụ

Ví dụ 1

INPUT

3 5 2 4
10 4 1

OUTPUT

0

Giải thích: Được chọn tối đa ~2~ cây cho gỗ nhiều nhất. Ngày ~0~: Hai cây cao nhất có chiều cao là ~10~ và ~4~. Lượng gỗ thu được lần lượt là ~(10-4) + (4-4) = 6~, tổng bằng ~6 > 5~ nên đáp án là ~0~.

Ví dụ 2

INPUT

6 25 3 10
9 9 20 15 1 8

OUTPUT

4

Giải thích: Được chọn tối đa ~3~ cây cao nhất để khai thác là ~20, 15~ và ~9~. Ngày ~0~: Lượng gỗ thu được là ~(20-10) + (15-10) + 0 = 15~ ~(15 < 25)~ nên chưa đủ gỗ. Với số ngày là ~4~, tổng gỗ là ~(24 - 10) + (19 - 10) + (13 - 10) = 26 > 25~ nên đủ lượng gỗ và đáp án là ~4~.

Vào thế kỷ XVII, Phố Hiến (Hưng Yên) là thương cảng sầm uất bậc nhất Đàng Ngoài, nơi tàu thuyền từ Nhật Bản, Hà Lan, Anh, Pháp, ... tấp nập vào ra buôn bán.

Để quản lý hàng vạn kiện hàng tơ lụa và gốm sứ xuất khẩu, người ta đánh mã số cho các lô hàng. Các thương nhân ở đây đặc biệt ưa thích những kiện hàng có mã số đặc biệt gọi là "Mã số Tam Tài". Theo quan niệm của các thương nhân lúc bấy giờ, mã số đó là số may mắn vì nó tượng trưng cho "Thiên - Địa - Nhân".

Một mã số kiện hàng được coi là "Mã số Tam Tài" nếu giá trị của nó là tích của đúng ~3~ số nguyên tố khác nhau. Ví dụ: ~30 = 2 \times 3 \times 5~, do đó ~30~ là "Mã số Tam Tài". ~50~ không phải là "Mã số Tam Tài" vì ~50 = 2 \times 5 \times 5~ (thừa số ~5~ xuất hiện ~2~ lần). ~24 = 2 \times 2 \times 2 \times 3~ nên ~24~ cũng không phải.

Yêu cầu

Cho hai số nguyên dương ~L~ và ~R~. Hãy đếm xem trong đoạn ~[L, R]~ có bao nhiêu số là "Mã số Tam Tài" và xác định "Mã số Tam Tài" đầu tiên có trong đoạn ~[L, R]~.

Dữ liệu đầu vào

Gồm một dòng duy nhất chứa hai số nguyên dương ~L~ và ~R~ ~(1 \le L \le R \le 10^{14}~ và ~R - L \le 2 \times 10^6)~, giữa hai số có một dấu cách.

Dữ liệu đầu ra

Ghi ra hai số tương ứng là số lượng "Mã số Tam Tài" trong đoạn ~[L, R]~ và "Mã số Tam Tài" đầu tiên có trong đoạn ~[L, R]~. Nếu không có số nào thì số lượng là ~0~.

Ràng buộc dữ liệu

• Subtask 1 (30% số điểm): ~1 \le L \le R \le 10^4~;
• Subtask 2 (25% số điểm): ~R \le 10^{12}~, nhưng ~R - L \le 1000~;
• Subtask 3 (30% số điểm): ~R \le 10^{12}~ và ~R - L \le 10^6~;
• Subtask 4 (15% số điểm): ~R \le 10^{14}~ và ~R - L \le 2 \times 10^6~.

Ví dụ

Ví dụ 1

INPUT

20 52

OUTPUT

2 30

Giải thích: Các "Mã số Tam Tài" trong đoạn ~[20; 52]~ là ~30 = 2 \times 3 \times 5~ và ~42 = 2 \times 3 \times 7~. "Mã số Tam Tài" đầu tiên trong đoạn là ~30~. Do đó, kết quả là ~2\ 30~.

Ví dụ 2

INPUT

1 105

OUTPUT

7 30

Giải thích: Các "Mã số Tam Tài" trong đoạn ~[1; 105]~ là ~30 = 2 \times 3 \times 5~, ~42 = 2 \times 3 \times 7~, ~66 = 2 \times 3 \times 11~, ~70 = 2 \times 5 \times 7~, ~78 = 2 \times 3 \times 13~, ~102 = 2 \times 3 \times 17~, ~105 = 3 \times 5 \times 7~. "Mã số Tam Tài" đầu tiên trong đoạn là ~30~. Do đó, kết quả là ~7\ 30~.

Ví dụ 3

INPUT

1 20

OUTPUT

0

Giải thích: Không có Mã số Tam Tài trong đoạn ~[1; 20]~. Do đó, kết quả là ~0~.