Cho hình chữ nhật có độ dài hai cạnh là các số tự nhiên. Biết chu vi của hình là ~P~ và hiệu độ dài hai cạnh là ~D~

Yêu cầu: Hãy xác định diện tích của hình chữ nhật đó

Input

Một dòng duy nhất là ~2~ số tự nhiên ~P,D~ được viết cách nhau bởi ~1~ dấu cách

Output

Một số nguyên duy nhât là diện tích của hình chữ nhật tương ứng.

Subtask

• Có ~40\%~ test tương ứng ~40\%~ số điểm có ~D = 0 1 \le P \le 200~
• Có ~40\%~ test khác tương ứng ~40\%~ số điểm cô ~200 < P \le 10 ^ 4~
• Có ~20\%~ test còn lại tương ứng ~20\%~ số điểm có ~P \le 10 ^ 9~

Sample Input 1

14 1

Sample Output 1

12

Sample Input 2

20 2

Sample Output 2

24

Bạn Vinh rất yêu thích các con số. Hôm nay Vinh được học về dấu hiệu chia hết cho ~2~ và ~3~. Thầy giáo viết cho Vinh hai số nguyên dương ~A,B~ ~(A \le B)~. Thầy yêu cầu Vinh đếm xem từ ~A~ tới ~B~ có bao nhiêu số chia hết cho ít nhất một trong hai số ~2~ và ~3~. Vinh rất ngại đếm bằng tay nên muốn nhờ bạn lập trình tìm câu trả lời cho câu hỏi thầy giáo đưa ra.

Yêu cầu: Cho biết ~A, B~. Tính và đưa ra số lượng số trong phạm vi từ ~A~ tới ~B~ chia hết cho ít nhất một trong hai số ~2~ và ~3~.

Input

Gồm ~2~ số nguyên dương ~A, B~ ~(A \le B \le 10^{18})~ được viết cách nhau một dấu cách.

Output

Một dòng duy nhất là số lượng số tìm được

Subtask

• Có ~40\%~ test tương ứng ~40\%~ số điểm có ~A = 1~, ~B \le 10 ^ 6~
• Có ~30\%~ test khác tương ứng ~30\%~ số điểm có ~A = 1~, ~B \le 2\times 10 ^ 9~
• Có ~30\%~ test còn lại tương ứng ~30\%~ số điểm không có bổ sung

Sample Input 1

1 10

Sample Output 1

7

Sample Input 2

3 5

Sample Output 2

2

Giải thích

Trong ví dụ ~1~, các số chia hết cho ít nhất một trong hai số ~2, 3~ là: ~2, 3, 4, 6, 8, 9, 10~.

Trong ví dụ ~2~, các số chia hết cho ít nhất một trong hai số ~2, 3~ là: ~3, 4~.

Cho hai số nguyên ~n, k~ và xâu ký tự ~S~ gồm n ký tự chữ số. Trong các xâu con gồm ~k~ ký tự liên tiếp của ~S~, tìm xâu con có tổng các chữ số đạt giá trị lớn nhất.

Input

Dòng đầu tiên chứa ~2~ số nguyên dương ~n, k~

Dòng thứ hai chứa xâu ký tự ~S~

Output

Đưa ra tổng các chữ số lớn nhất của xâu con tim được

Subtasks

• ~25\%~ số test tương ứng ~25\%~ số điểm có ~k = 1, n \le 1000~
• ~30\%~ số test khác tương ứng ~30\%~ số điểm có ~k \le n \le 1000~
• ~45\%~ số test còn lại tương ứng ~45\%~ số điểm có ~k \le n \le 200000~

Sample Input 1

5 1
48063

Sample Output 1

8

Sample Input 2

6 3
362720

Sample Output 2

15

Giải thích

Trong ví dụ đầu tiên, xâu tìm được là 8.

Trong ví dụ thứ hai, xâu tìm được là 627.

Một trợ lý AI đang được giao nhiệm vụ lập lịch cho một người dùng. Danh sách các cuộc họp được gửi dưới dạng sau:

• Số nguyên dương ~n~ là số lượng cuộc họp.
• Dãy ~A = (A_1, A_2, A_3, ..., A_n)~ với ~A_i~ là thời gian bắt đầu của cuộc họp ~i~.
• Dãy ~B = (B_1, B_2, B_3, ..., B_n)~ với ~B_i~ là thời gian kết thúc của cuộc họp ~i~.

Trợ lý AI cần kiểm tra xem người dùng có thể tham gia đầy đủ tất cả các cuộc họp hay không. Một cuộc họp mới chỉ có thể tham gia nếu thời gian bắt đầu của nó lớn hơn hoặc bằng thời gian kết thúc của cuộc họp trước đó.

Yêu cầu: Cho ~q~ truy vấn, mỗi truy vấn là thông tin một danh sách các cuộc họp. Với mỗi truy vấn, đưa ra YES nếu có thể tham dự tất cả các cuộc họp, đưa ra NO nếu không thể.

Input

Dòng đầu ghi số nguyên dương ~q~.

~q~ nhóm dòng tiếp theo, mỗi nhóm gồm 3 dòng xác định một truy vấn:

• Dòng đầu tiên chứa số nguyên dương ~n~ là số lượng cuộc họp
• Dòng thứ hai chứa ~n~ số ~A_1, A_2, A_3, ..., A_n~ (~1 \le A_i \le 10^9~).
• Dòng thứ ba chứa ~n~ số ~B_1, B_2, B_3, ..., B_n~ (~1 \le B_i \le 10^9~).

Output

Đưa ra ~q~ dòng, dòng thứ ~j~ là câu trả lời tương ứng với truy vấn thứ ~j~ theo thứ tự trong input.

Subtasks

Gọi ~T~ là tổng số lượng số xuất hiện trong input.

• Có ~20 \%~ test tương ứng ~20 \%~ số điểm có ~q = 1; T ≤ 100~.
• Có ~30 \%~ test khác tương ứng ~30 \%~ số điểm có ~q = 1; T ≤ 200000~.
• ~50 \%~ test còn lại tương ứng ~50 \%~ số điểm có ~T ≤ 200000~.

Sample Input 1

1
3
1 7 4
3 10 7

Sample Output 1

YES

Sample Input 2

3
3
1 4 7
5 6 10
2
1 5
3 8
2
1 6
8 10

Sample Output 2

NO
YES
NO

Giải thích

Ở ví dụ 2 có 3 truy vấn:

Truy vấn đầu tiên: cuộc họp thứ nhất bắt đầu từ thời điểm 1, kết thúc ở thời điểm 5. Cuộc họp thứ 2 bắt đầu từ thời điểm 4 và kết thúc ở thời điểm 6. Do đó không thể tham dự đầy đủ hai cuộc họp này.

Truy vấn thứ hai: các cuộc họp không chồng nhau nên trả lời là YES.

Truy vấn thứ ba: cuộc họp thứ 2 bắt đầu từ thời điểm 6 trong khi cuộc họp thứ nhất kết thúc ở thời điểm 8 nên không thể tham dự đầy đủ các cuộc họp.

Nhân dịp Tết thiếu nhi, các bạn tỉnh nguyện viên chuẩn bị n hộp để đựng kẹo. Các hộp được đánh số ~1,2,3,..., n~ từ trái qua phải. Ban đầu, hộp thứ ~i~ có ~a_i~ viên.

Ban tổ chức tặng thêm ~m~ viên kẹo và các tỉnh nguyện viên muốn chia số kẹo này vào các hộp sao cho sau khi chia kẹo, số kẹo ở hộp ít nhất là lớn nhất có thể. Cách chia kẹo như sau:

• Mỗi lần lẩy ~1~ viên kẹo và bỏ vào hộp có ít kẹo nhất.
• Nếu có nhiều hộp cùng ít kẹo nhất, chọn hộp có số hiệu nhỏ nhất (bên trái nhất).
• Lặp lại cho đến khi chia hết ~m~ viên kẹo.

Yêu cầu: Hãy xác định số kẹo từng hộp sau khi chia hết số kẹo đó.

Input

Dòng đầu tiên chứa hai số nguyên ~n,m~ (~n ≤ 10^4~, ~m ≤ 10^{16}~)

Dòng thứ hai chứa ~n~ số tự nhiên ~a_1, a_2, ..., a_n~ là số lượng kẹo ban đầu trong mỗi hộp (~a_i \le 10^{16}~).

Output

Dòng dầu tiên ghi số lượng kẹo của hộp ít nhất sau khi thực hiện chia hết ~m~ viên kẹo.

Dòng thứ hai là ~n~ số ~b_1, b_2, b_3 ..., b_n~ với ~b_i~ là số lượng kẹo trong hộp ~i~ sau khi thực hiện chia kẹo.

Sample Input 1

5 3
6 2 4 2 3

Sample Output 1

3
6 4 4 3 3

Dãy ban đầu: ~(6,2,4,2,3)~

• Lượt ~1~: thêm ~1~ viên vào hộp ~2~: ~(6,3,4,2,3)~
• Lượt ~2~: thêm ~1~ viên vào hộp ~4~: ~(6,3,4,3,3)~
• Lượt ~3~: thêm ~1~ viên vào hộp ~2~: ~(6,4,4,3,3)~

Sample Input 2

5 7
8 8 8 8 8

Sample Output 2

9 
10 10 9 9 9

Subtasks

Bài làm của thí sinh sẽ được ~60 \%~ số điểm của test nếu như chi đưa ra đúng số lượng kẹo nhỏ nhất trong các hộp.