Khu phố nhà Mai đã bị phong toả do phát sinh một số ca nhiễm Covid-19. Có ~N~ người thuộc diện phải cách ly y tế. Để theo dõi mức độ phòng chống dịch của địa phương, cán bộ y tế đã thực hiện điều tra toàn bộ khu phố và cho kết quả là chỉ có đúng ~a~ người trong số ~N~ người này biết cách thực hiện tốt việc cách ly, những người không biết thì chắc chắn là sẽ không cách ly tốt. Do sơ suất nên cán bộ y tế chỉ ghi được danh sách ~b~ người không thực hiện tốt cách ly, danh sách này có thể chưa đầy đủ nhưng cán bộ này đảm bảo rằng những người đã biết cách thực hiện mà không có tên trong danh sách là những người đã thực hiện tốt.

Yêu cầu: Xác định số lượng tối thiểu và tối đa người đã thực hiện tốt việc cách ly.

Input

Vào từ tệp văn bản BAI1.INP gồm 3 số nguyên ~N, a~ và ~b~ (~1 \le N \le 10^{18}; 0 \le a , b \le N~).

Output

Ghi ra tệp văn bản BAI1.OUT hai số nguyên là số lượng tối thiểu và số lượng tối đa người thực hiện tốt việc cách ly.

Scoring

Sample Input 1

3 2 1

Sample Output 1

1 2

Trong giờ thực hành Tin học đầu tiên, Bằng được thầy giáo khải giao cho bài tập là gõ lại một văn bản vào máy tính, văn bản gồm một hoặc nhiều từ, mỗi từ là một xâu kí tự gồm các chữ cái Tiếng Anh in thường, các từ cách nhau bởi đúng một dấu cách. Sau khi miệt mài gõ hết toàn bộ văn bản, Bằng nhận ra bàn phím của máy em sử dụng có một số phím bị kẹt, khi gõ vào phím kẹt thì kí tự tương ứng có thể xuất hiện nhiều hơn một lần, do đó văn bản em gõ vào có thể bị sai so với yêu cầu. Bằng đã đổi bàn phím mới không bị kẹt và làm lại bài tập. Lần này, văn bản gõ vào đã hoàn toàn khớp với yêu cầu. Dựa vào hai lần gõ này, để chuẩn bị cho những giờ học thuật toán sắp tới, thầy Khải yêu cầu Bằng kiểm tra xem ở lần gõ văn bản đầu tiên có bao nhiêu từ Bằng có thể đã gõ đúng, tức là hoặc là nó trùng khớp với từ tương ứng đã gõ lần thứ hai hoặc nó sai có thể là do một số phím bị kẹt.

Yêu cầu: Hãy đếm số từ như yêu cầu trên, biết rằng trong lần gõ văn bản đầu tiên phím dấu cách (space) không bị kẹt và Bằng đã không gõ sót hay thừa bất kì kí tự nào trong văn bản.

Input

Vào từ tệp văn bản BAI2.INP gồm hai dòng:

• Dòng đầu chứa một xâu kí tự chỉ bao gồm các chữ cái Tiếng Anh in thường và dấu cách thể hiện văn bản mà Bằng gõ lần đầu (độ dài xâu không quá ~10^6~).

• Dòng thứ hai chứa một xâu kí tự chỉ bao gồm các chữ cái Tiếng Anh in thường và dấu cách thể hiện văn bản mà Bằng gõ lần thứ hai (độ dài xâu không quá ~10^6~).

Output

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

Scoring

Subtask	% số test	Giới hạn
1	~80\%~	Xâu thứ hai không có hai kí tự nào kề nhau mà giống nhau.
2	~20\%~	Không có ràng buộc gì thêm.

Sample Input 1

tiin hojcc laf mot ngannh khoa hojc
tin hoc la mot nganh khoa hoc

Sample Output 1

4

Nhân dịp chào đón Giáng sinh, Thành quyết định lấy hết tiền học bổng của mình để mua toàn bộ ~N~ món quà lưu niệm tặng các bạn nữ trong lớp, các món quà được đánh số từ ~1~ đến ~N~, món thứ ~i~ có giá là ~a_i~, ~i = 1 \div N~. Cảm động trước hành động của Thành, chủ cửa hàng đã có chương trình khuyến mãi đặc biệt dành cho em. Thành được phép chia ~N~ món quà thành một hay nhiều đơn hàng với điều kiện hai món quà bất kì trong một đơn phải có giá chênh lệch nhau không bé hơn ~K~. Với mỗi đơn hàng như vậy, Thành chỉ phải thanh toán số tiền là giá của món quà đắt nhất trong đơn đó mà thôi.

Yêu cầu: Giúp Thành chia ~N~ món quà thành các đơn hàng sao cho tổng số tiền phải trả cho tất cả đơn hàng là nhỏ nhất.

Input

Vào từ tệp văn bản BAI3.INP gồm ~2~ dòng:

• Dòng thứ nhất chứa hai số nguyên dương ~N~ và ~K~ (~N \le 10^5, K \le 10^9~)

• Dòng thứ hai gồm ~N~ số nguyên dương ~a_1, a_2,.. a_N~ (~a_i \le 10^9, i = 1 \div N~)

Output

Ghi ra tệp văn bản BAI3.OUT một số nguyên duy nhất là tổng số tiền phải trả.

Scoring

Subtask	Điểm	Giới hạn
1	~50~	~N \le 10^4~
2	~50~	Không ràng buộc gì thêm

Sample Input 1

3 2
1 3 3

Sample Output 1

6

Sau khi tính toán cẩn thận, chia các đơn hàng một cách hợp lý, Thành đã mua được tất cả các món quà chỉ với số tiền là ~117649~. Mặc dù không liên quan đến việc mua bán này nhưng Thịnh nhận thấy rằng số ~117649~ rất đặc biệt, đó là nó không phải số nguyên tố nhưng lại có số các ước số dương là một số nguyên tố (số ~117649~ có đúng ~7~ ước dương), em gọi các số nguyên dương có tính chất như vậy là số "đặc biệt". Vốn rất yêu thích môn Toán và những con số, Thịnh muốn đố các bạn giải bài toán như sau:

Yêu cầu: Đếm các số "đặc biệt" trong đoạn từ ~L~ đến ~R~.

Input

Vào từ tệp văn bản BAI4.INP gồm ~2~ số nguyên dương ~L~ và ~R~ (~L \le R \le 10^{12}~).

Output

Đưa ra tệp văn bản BAI4.OUT một số duy nhất là kết quả tìm được.

Scoring

Subtask	Điểm	Giới hạn
1	~\frac{1}{3}~ số điểm	~R \le 10^5~
2	~\frac{2}{3}~ số điểm	không có ràng buộc gì thêm

Sample Input 1

2 5

Sample Output 1

1

Để đáp lại tấm lòng của Thành, Trâm cũng quyết định lấy tiền thưởng của mình để mua quà lưu niệm tặng các bạn nam lớp ~\text{12I}~. Trâm vào trang Web của một cửa hàng, chọn được ~n~ món hàng đưa vào danh sách sẽ mua làm quà, món hàng thứ ~i~ có giá ~a_i~, ~i = 1 \div n~. Khi em chuẩn bị chuyển danh sách hàng đã chọn vào giỏ mua thì xuất hiện thông báo về một chương trình khuyến mãi mới. Nếu giỏ hàng mua của khách có dưới ~10~ món hàng thì không được khuyến mãi gì, nếu có từ ~10~ đến ~19~ món hàng thì món giá thấp nhất trong số đó sẽ được nhận miễn phí, nếu giỏ hàng mua có từ ~20~ đến ~29~ món hàng thì hai món giá thấp nhất trong số đó sẽ được nhận miễn phí, nếu giỏ hàng mua có từ ~30~ đến ~39~ món hàng thì ba món giá thấp nhất trong số đó sẽ được nhận miễn phí~\dots~ Tóm lại, nếu số lượng hàng trong giỏ là ~m~ thì sẽ được miễn phí ~\lfloor \frac{m}{10} \rfloor~ món có giá nhỏ nhất trong giỏ đó.

Trâm không thể thay đổi trình tự hàng trong danh sách đã đăng ký mua nhưng có thể cắt danh sách thành các phần, mỗi phần gồm một dãy liên tiếp các hàng trong danh sách và bỏ vào một giỏ hàng riêng để nhận được chính sách ưu đãi đã nêu với giỏ hàng. Là một người giỏi tính toán, Trâm nhanh chóng hoàn thành các giỏ đặt hàng để tổng chi phí phải trả cho ~n~ mặt hàng muốn mua là nhỏ nhất.

Yêu cầu: Hãy xác định số tiền nhỏ nhất mà Trâm phải thanh toán.

Input

Vào từ tệp văn bản BAI5.INP gồm:

• Dòng đầu tiên chứa một số nguyên dương ~n~ (~n \le 10^5~),

• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ (~a_i \le 10^9~, ~i = 1 \div n~).

Output

Đưa ra tệp văn bản BAI5.OUT một số nguyên là kết quả tìm được.

Scoring

Subtask	Điểm	Giới hạn
1	~25~	~n \le 19~
2	~75~	Không có ràng buộc gì thêm

Sample Input 1

12
4 4 5 5 5 5 5 5 5 5 5 5

Sample Output 1

53