Cho bốn số thực ~A, B, C, D~. Hỏi tích của bốn số đó là số dương, số âm hay số ~0~.

Dữ liệu nhập vào từ file TBS.INP:

Gồm bốn dòng, mỗi dòng gồm một số thực lần lượt là bốn số ~A, B, C, D~ ~(-10^{18} ≤ A, B, C, D ≤ 10^{18})~.

Kết quả ghi ra file TBS.OUT:

Một số nguyên duy nhất là:

• ~1~ nếu tích bốn số là số dương~;~
• ~-1~ nếu tích bốn số là số âm~;~
• ~0~ nếu tích bốn số là số ~0.~

Ví dụ

Input

20.21
-1.2
-2.3
1.0

Output

1

Input

5.0
-8.9
0.0
123.456

Output

0

Cho một robot được lập trình di chuyển trên một hàng ngang gồm các ô vuông. Mỗi ô được đặt tên bằng các kí tự theo thứ tự từ ~'𝐴'~ đến ~'𝑍'~ và được lặp lại vô hạn. Ban đầu robot xuất phát ở ô thứ ~1~ có tên là ~'𝐴'~ và nhảy đến các ô tiếp theo quy luật: lần ~1~ nhảy ~1~ ô, lần ~2~ nhảy ~2~ ô, lần ~3~ nhảy ~3~ ô, ~…~, lần ~𝑁~ nhảy ~𝑁~ ô. Vậy sau ~𝑁~ lần nhảy thì robot đang ở ô nào?

Dữ liệu nhập vào từ file văn bản DKT.INP:

Gồm một số nguyên dương ~N~ là số lần nhảy của robot ~(N \le 10^9)~.

Kết quả ghi ra file văn bản DKT.OUT:

Một kí tự duy nhất là tên của ô sau ~N~ lần robot nhảy.

Ràng buộc

• Có ~60\%~ số test ứng với ~60\%~ số điểm của bài thoả mãn: ~𝑁 ≤ 10^3;~
• ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thoả mãn: ~𝑁 ≤ 10^6;~
• ~20\%~ số test còn lại ứng với 20% số điểm của bài không có ràng buộc gì thêm.

Ví dụ

Input

1

Output

B

Giải thích: Sau ~1~ lần nhảy, robot ở ô thứ ~2~, có tên là kí tự ~B~.

Input

4

Output

K

Giải thích: Sau ~4~ lần nhảy, robot ở ô thứ ~11~, có tên là kí tự ~K~.

Input

7

Output

C

Giải thích: Sau ~7~ lần nhảy, robot ở ô thứ ~29~, có tên là kí tự ~C~.

Trên trục số ~Ox~, cho ~𝑁~ đoạn thẳng, mỗi đoạn thẳng được xác định bởi hai điểm đầu và cuối là hai số nguyên. Một điểm ~𝑀~ được gọi là nằm trong đoạn thẳng ~𝐴𝐵~ nếu ~𝐴 ≤ 𝑀 ≤ 𝐵~.

Yêu cầu: Đếm xem có bao nhiêu điểm có toạ độ nguyên nằm trong đúng ~𝐾~ đoạn thẳng.

Dữ liệu nhập vào từ file văn bản DC.INP:

• Dòng đầu tiên gồm hai số nguyên ~𝑁~ và ~𝐾~ ~(1 ≤ 𝐾 ≤ 𝑁 ≤ 10^5);~
• ~𝑁~ dòng sau, mỗi dòng gồm hai số nguyên ~𝑎, 𝑏~ mô tả hai điểm đầu và cuối của đoạn thẳng ~(1 ≤ 𝑎 ≤ 𝑏 ≤ 10^{18})~.

Kết quả ghi ra file văn bản DC.OUT:

Một số nguyên duy nhất là số lượng điểm có toạ độ nguyên nằm trong đúng ~𝐾~ đoạn thẳng.

Ràng buộc

• Có ~50\%~ số test ứng với ~50\%~ số điểm của bài thoả mãn: ~𝑎, 𝑏 ≤ 10^3;~
• ~30\%~ số test khác ứng với ~30\%~ số điểm của bài thoả mãn: ~𝐾 = 𝑁;~
• ~20\%~ số test còn lại ứng với ~20\%~ số điểm của bài không có ràng buộc gì thêm.

Ví dụ

Input

3 2
1 5
2 8
3 7

Output

3

Giải thích: Toạ độ của ~3~ điểm nằm trong đúng ~2~ đoạn thẳng là: ~2, 6, 7~.

• Điểm có toạ độ ~2~ nằm trong ~2~ đoạn thẳng: đầu tiên và thứ hai.
• Điểm có toạ độ ~6, 7~ nằm trong ~2~ đoạn thẳng: thứ hai và thứ ba.

Input

3 1
1 5
2 8
3 7

Output

2   

Giải thích: Toạ độ của ~2~ điểm nằm trong đúng ~1~ đoạn thẳng là: ~1, 8~.

• Điểm có toạ độ ~1~ chỉ nằm trong đoạn thẳng đầu tiên.
• Điểm có toạ độ ~8~ chỉ nằm trong đoạn thẳng thứ ba.

Input

3 3
1 5
2 8
3 7

Output

3

Giải thích: Toạ độ của ~3~ điểm nằm trong cả ~3~ đoạn thẳng là: ~3,4,5~.

Số chính phương đặc biệt là số chính phương được tạo bởi một số nguyên tố. Ví dụ ~4 = 2 \times 2; \ 9 = 3 \times 3; \ 36 = 6 \times 6~ nên ~4~ và ~9~ là số chính phương đặc biệt còn ~36~ thì không phải là số chính phương đặc biệt.

Yêu cầu: Cho ~2~ số nguyên dương ~a, b~. Hãy đếm xem trong đoạn ~[a..b]~ có bao nhiêu số chính phương đặc biệt?

Dữ liệu vào từ tệp văn bản CP.INP:

Gồm hai số nguyên dương ~a, b \ (2 \le a \le b \le 10^{12})~.

Kết quả ghi ra tệp văn bản CP.OUT:

Gồm một dòng chứa một số duy nhất là kết quả của bài toán.

Ràng buộc

• Có ~80\%~ số test ứng với ~80\%~ số điểm của bài thoả mãn ~2 \le a \le b \le 10^6;~
• ~20\%~ số test còn lại ứng với ~20\%~ số điểm của bài không có ràng buộc gì thêm.

Ví dụ

Input

2 10

Output

2

Cho một bảng ô vuông gồm ~n~ hàng và ~n~ cột. Các hàng được đánh số từ ~1~ đến ~n~, các cột được đánh số từ ~1~ đến ~n~. Ô ở hàng thứ ~i~ và cột thứ ~j~ có giá trị là ~i \times j~ ~(1 \le i \le n, \ 1 \le j \le n)~.

Yêu cầu: Cho một số nguyên dương ~x~. Hãy đếm số lượng ô trong bảng có giá trị bằng ~x~.

Dữ liệu vào từ tệp văn bản BS.INP:

Gồm hai số nguyên ~n~ và ~x~ ~(1 \le n \le 10^6, \ 1 \le x \le 10^{12})~ là kích thước của bảng và số nguyên ta cần tìm trong bảng.

Kết quả ghi ra tệp văn bản BS.OUT:

Số nguyên duy nhất là số lượng ô trong bảng có giá trị bằng ~x~.

Ràng buộc

• Có ~70\%~ số test ứng với ~70\%~ số điểm của bài thoả mãn ~0 \lt n \le 10^3, \ 1 \le x \le 10^6;~
• ~30\%~ số test còn lại ứng với ~30\%~ số điểm của bài không có ràng buộc gì thêm.

Ví dụ

Input

6 5

Output

2

Input

6 12

Output

4

Input

5 13

Output

0

Giải thích

Nhờ hoàn thành tốt công việc, An và Bình được công ty thưởng ~N~ tờ tiền. Tờ tiền thứ ~i~ có mệnh giá ~a_i~. Hai bạn muốn chia đôi số tiền thành hai phần bằng nhau bằng cách chia cho mỗi người một số tờ tiền. Vì thế hai bạn quyết định sẽ chọn ra những tờ tiền để tổng số tiền hai bạn nhận được bằng nhau và lớn nhất, phần còn lại (nếu có) sẽ đem đi đầu tư.

Yêu cầu: Hãy giúp hai bạn tính tổng số tiền lớn nhất mà mỗi người nhận được trước khi đầu tư.

Dữ liệu vào từ tệp văn bản CT.INP:

• Dòng đầu tiên chứa số nguyên dương ~N \ (N \le 500);~
• Dòng thứ hai bao gồm ~N~ số nguyên dương ~a_1, a_2, ..., a_N~ là mệnh giá của những tờ tiền. Tổng giá trị những tờ tiền sẽ không vượt quá ~10^5~.

Kết quả ghi ra tệp văn bản CT.OUT:

Gồm một dòng duy nhất là số tiền lớn nhất mà mỗi người nhận được.

Ràng buộc

• Có ~40\%~ số test ứng với ~40\%~ số điểm của bài thoả mãn ~N \le 3;~
• ~30\%~ số test tiếp theo ứng với ~30\%~ số điểm của bài thoả mãn ~N \le 12;~
• ~30\%~ số test còn lại ứng với ~30\%~ số điểm của bài không có ràng buộc gì thêm.

Ví dụ

Input

5
1 2 4 5 2

Output

7

Giải thích:

• An có thể chọn những tờ tiền có mệnh giá ~1, 2, 4~.
• Bình chọn những tờ tiền còn lại có mệnh giá ~5, 2~.
• Mỗi người sẽ nhận được tổng số tiền là ~7~. Vì số tiền mỗi người nhận đã bằng nhau và đã chia hết số tiền nên họ sẽ không đầu tư.

Input

5
9 8 4 5 13

Output

17

Giải thích:

• An sẽ chọn những tờ tiền có mệnh giá ~9, 8~.
• Bình sẽ chọn những tờ tiền có mệnh giá ~4, 13~.
• Mỗi người sẽ nhận được tổng số tiền là ~17~. Tờ tiền còn lại có mệnh giá ~5~ sẽ đem đi đầu tư.

Trong phòng thí nghiệm chỉ có đúng ba loại cốc có dung tích là ~5 \ (ml)~, ~3 \ (ml)~ và ~2 \ (ml)~. Hỏi cần ít nhất bao nhiêu lần đong nước để lấy được đúng ~N \ (ml)~.

Dữ liệu vào từ file văn bản DONGNUOC.INP:

Một số nguyên dương duy nhất ~N~ ~(2 \le N \le 10^{18})~ là số nước cần đong.

Kết quả ghi ra file văn bản DONGNUOC.OUT:

Một số nguyên dương duy nhất là số lượng lần đong ít nhất thoả mãn yêu cầu đề bài.

Ví dụ

Input

12

Output

3

Giải thích

Đong hai lần bằng cốc ~5 \ (ml)~ và một lần bằng cốc ~2 \ (ml)~.

Input

6

Output

2

Giải thích

Đong hai lần bằng cốc ~3 \ (ml)~.

Cho một dãy số gồm ~N~ số nguyên dương ~a_1, a_2, ..., a_N~ có giá trị không vượt quá ~10^6~. Tìm dãy con liên tiếp ngắn nhất có chứa ít nhất hai số nguyên tố.

Dữ liệu vào từ file văn bản DAYCON.INP:

• Dòng đầu tiên gồm một số nguyên dương ~N \ (N \le 10^6)~ là số lượng phần tử của dãy số;
• Dòng thứ hai gồm ~N~ số nguyên dương ~a_1, a_2, ..., a_N~ lần lượt mô tả các phần tử của dãy số.

Kết quả ghi ra file văn bản DAYCON.OUT:

Một số nguyên duy nhất là số lượng phần tử của dãy con thoả mãn đề bài. Trường hợp không tồn tại dãy con thoả mãn, in ra ~-1~.

Ví dụ

Input

10
3 4 8 4 5 6 1 7 4 6

Output

4

Giải thích

Chọn dãy con từ vị trí thứ ~5~ đến vị trí thứ ~8~: ~5, 6, 1, 7~.

Ràng buộc

• Có ~50\%~ số test ứng với ~50\%~ số điểm của bài thoả mãn: ~N \le 10^3; \ a_i \le 10^3~;
• ~30\%~ số test khác ứng với ~30\%~ số điểm của bài thoả mãn: ~N \le 10^6; \ a_i \le 10^3~;
• ~20\%~ số test còn lại ứng với ~20\%~ số điểm của bài không có ràng buộc gì thêm.

Bản đồ thành phố X có dạng lưới ô vuông ~M~ hàng ~N~ cột, các hàng được đánh số từ ~1~ tới ~M~, các cột được đánh số từ ~1~ tới ~N~. Mỗi ô vuông trên bản đồ có thể là khu đất trống hoặc một khu dân cư hoặc một siêu thị.

Mỗi siêu thị chỉ có thể phục vụ các khu dân cư có khoảng cách so với nó không quá ~D~, nghĩa là nếu siêu thị nằm ở ô ~(x, y)~ thì nó có thể phục vụ được tất cả các khu dân cư nằm trong hình vuông có ô trái trên là ~(x - D, y - D)~, ô phải dưới là ~(x + D, y + D)~ (như Hình 1).

Một khu dân cư gọi là "chất lượng cao" nếu được ít nhất ~K~ siêu thị có thể phục vụ nó. Cho biết bản đồ của thành phố X, hãy đếm số lượng khu dân cư "chất lượng cao".

Dữ liệu vào từ file văn bản KHUDANCU.INP:

• Dòng đầu chứa bốn số nguyên ~M, N, D~ và ~K~ ~(1\le D \le \max(M, N); \ 1\le K\le M \times N)~;
• ~M~ dòng tiếp theo, mỗi dòng gồm ~N~ ký tự, mỗi ký tự biểu diễn một ô vuông bản đồ. Mỗi ký tự sẽ thuộc một trong ba loại sau:
  • . biểu diễn một khu đất trống;
  • P biểu diễn một khu dân cư;
  • M biểu diễn một siêu thị;

Dữ liệu đảm bảo tồn tại ít nhất một khu dân cư và ít nhất một siêu thị.

Kết quả ghi ra file văn bản KHUDANCU.OUT:

Ghi ra một số duy nhất là số khu dân cư "chất lượng cao".

Ví dụ

Input

5 5 1 2
P....
....P
..PM.
.M...
.....

Output

1

Giải thích

Bản đồ minh hoạ thành phố ~X~ như Hình 2.

Khu dân cư ở ô ~(1, 1)~ không được siêu thị nào phục vụ;

Khu dân cư ở ô ~(2, 5)~ được một siêu thị có thể phục vụ;

Khu dân cư ở ô ~(3, 3)~ được hai siêu thị có thể phục vụ;

Vậy có một khu dân cư "chất lượng cao".

Ràng buộc

• Có ~40\%~ số test ứng với ~40\%~ số điểm của bài thoả mãn: ~M = 1; \ N, D \le 10^3~;
• ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thoả mãn: ~M = 1; \ N \le 10^5~;
• ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thoả mãn: ~2 \le M, N \le 1000;~ số khu dân cư, số siêu thị không vượt quá ~1000~;
• ~20\%~ số test còn lại ứng với ~20\%~ số điểm của bài thoả mãn: ~2 \le M, N \le 1000~.