Feb có ba ruộng khoai tây, anh ta đã thu hoạch được ~a~ củ khoai tây ở ruộng thứ nhất và ~b~ củ khoai tây ở ruộng thứ hai. Anh ta vẫn chưa thu hoạch ở ruộng thứ ba. Feb là người mê tín và anh ta tin rằng nếu tổng số củ khoai tây thu hoạch được ở cả ba ruộng là một số nguyên tố thì anh ta sẽ gặp được nhiều may mắn. Tuy nhiên Feb muốn nghỉ ngơi sớm nên muốn số lượng khoai tây thu hoạch ở ruộng thứ ba là ít nhất.

Hãy cho biết Feb cần thu hoạch thêm ít nhất bao nhiêu củ khoai tây ở ruộng thứ ba để tổng số lượng khoai tây thu hoạch được ở cả ba ruộng là một số nguyên tố.

Lưu ý rằng phải có ít nhất 1 củ khoai tây được thu hoạch ở ruộng thứ ba.

Input

Hai số ~a~, ~b~ (~1 \leq a,b \leq 10^7~) trên một dòng.

Output

Một số nguyên duy nhất là kết quả bài toán.

Sample Test

Input 1

1 3

Output 1

1

Input 2

3 4

Output 2

4

Sau buổi học về số học, Minh đã biết cách tính tổng của ~n~ số tự nhiên liên tiếp. Ở nhà, Minh tiếp tục làm các bài tập về tính tổng của các số tự nhiên liên tiếp. Minh thắc mắc, liệu với số tự nhiên ~k~ thì có thể phân tích ~k~ thành tổng các số tự nhiên liên tiếp hay không? Ví dụ với ~k = 9~ (có thể phân tích: ~9 = 9~; ~9 = 5+4~; ~9 = 2 + 3 + 4~) thì có 3 cách phân tích thành tổng các số tự nhiên liên tiếp.

Yêu cầu

Viết chương trình giúp Minh tìm số cách phân tích số tự nhiên ~k~ thành tổng các số tự nhiên liên tiếp.

Input

Số nguyên dương ~k~ (~1 \leq k \leq 10^{12}~).

Output

Một số duy nhất là số cách phân tích tìm được.

Sample Test

Input

9

Output

3

Bạn đang chế tạo một loại thuốc thần kỳ có tác dụng làm khuôn mặt trở nên xinh đẹp. Công thức loại thuốc này là ~x\%~ ma thuật và ~(100 - x)\%~ nước. Mỗi thao tác bạn cần thêm 1 ml tinh chất ma thuật hoặc 1 ml tinh chất nước. Hãy cho biết bạn ít nhất bao nhiêu thao tác để tạo được loại thuốc thần kỳ.

Input

Số nguyên ~x~ (~0 \leq x \leq 100~).

Output

Số thao tác ít nhất để tạo được thuốc thần kỳ.

Sample Test

Input

25

Output

4

Tom có ~n~ đồng tiền vàng, cậu ta thường lấy các đồng tiền vàng này để xếp thành hình tam giác theo quy tắc: Dòng đầu tiên dùng 1 đồng tiền, dòng thứ 2 dùng 2 đồng tiền, dòng thứ 3 dùng 3 đồng tiền, dòng thứ ~i~ dùng ~i~ đồng tiền...

Yêu cầu

Hãy cho biết với ~n~ đồng tiền vàng, Tom có thể xếp được tam giác nhiều nhất bao nhiêu dòng?

Input

Dòng đầu tiên ghi số nguyên ~n~ (~1 \leq n \leq 10^9~).

Output

Một số nguyên cho biết kết quả của bài toán.

Sample Test

Input

7

Output

3

Chef có 3 hộp với kích thước ~a, b, c~. Anh ấy cho các hộp vào những chiếc túi có kích thước là ~d~ (~a, b, c \leq d~). Tìm số túi nhỏ nhất Chef cần để tất cả các hộp đều thuộc một túi nào đó. Một túi có thể chứa nhiều hơn một hộp nếu tổng kích thước của các hộp không vượt quá kích thước của túi.

Input

• Dòng đầu tiên chứa số nguyên ~t~ (~t \leq 100~) cho biết số test.
• ~t~ dòng tiếp theo, mỗi dòng chứa 4 số nguyên ~a, b, c, d~ (~0 < a, b, c, d \leq 100~) thể hiện kích thước của các hộp và các túi.

Output

Với mỗi test in ra một số nguyên cho biết số túi ít nhất mà Chef cần sử dụng.

Sample Test

Input

3
2 3 5 10
1 2 3 5
3 3 4 4

Output

1
2
3

Nam đang có ~n~ tờ tiền, tờ thứ ~i~ (~1 \leq i \leq n~) có giá trị ~a_i~. Nam đang cần tiền để mua bút chì cho bài kiểm tra trắc nghiệm sắp tới nên anh ấy sẽ lấy 1 tờ trong số ~n~ tờ tiền Nam đang có. Tuy nhiên Nam muốn lấy 1 tờ tiền sao cho sau khi lấy, giá trị trung bình cộng của các tờ tiền còn lại không thay đổi so với ban đầu.

Ví dụ: Nam đang có 5 tờ tiền với các giá trị 5, 4, 1, 3, 2; Nam cần lấy tờ tiền có giá trị 3 để trung bình cộng của các tờ tiền trước và sau khi lấy đều là 3.

Yêu cầu

Với các tờ tiền đang có, hãy cho biết Nam cần lấy tờ tiền nào để trung bình cộng của các tờ tiền còn lại không thay đổi so với ban đầu?

Input

• Dòng đầu tiên ghi số nguyên dương ~n~ (~2 \leq n \leq 10^6~);
• Dòng thứ hai lần lượt ghi các số ~a_1, a_2, \dots, a_n~ (~1 \leq a_i \leq 10^9~).

Output

Ghi một số nguyên cho biết giá trị của tờ tiền cần lấy. Nếu Nam không có cách để lấy 1 tờ tiền thỏa mãn yêu cầu thì ghi ~-1~.

Sample Test

Input

5
5 4 1 3 2

Output

3

Ràng buộc:

• Có 70% số test tương ứng với 70% số điểm có ~2 \leq n \leq 2000~;
• Có 30% số test còn lại tương ứng 30% số điểm không có ràng buộc gì thêm.

Vào học kỳ hè, GV lớp Chuyên Tin có chính sách chấm điểm các bài luyện tập của học sinh như sau:

• Mỗi học sinh sẽ nhận được một điểm trong phạm vi từ 0 đến 100.
• Bất kỳ điểm của bài tập nào ít hơn 40 sẽ được coi là một điểm không đạt – phải làm lại bài.

Để tổng kết, GV muốn làm tròn điểm của các học sinh để khuyến khích theo các quy tắc sau:

• Nếu sự khác biệt giữa điểm và bội số tiếp theo của 5 ít hơn 3, làm tròn điểm lên đến bội số tiếp theo của 5.
• Nếu giá trị của điểm ít hơn 38, không làm tròn số vì kết quả sẽ vẫn là điểm không đạt.

Yêu cầu

Với các giá trị điểm ban đầu mà GV đã cho ~n~ học sinh, hãy giúp GV của bạn tự động hóa quá trình làm tròn điểm.

Input

• Dòng đầu tiên chứa một số nguyên ~n~ - số lượng học sinh.
• ~n~ các dòng tiếp theo chứa một số nguyên ~a_i~ duy nhất tương ứng với học sinh thứ ~i~.

Output

Ghi ra số nguyên tương ứng là điểm làm tròn theo yêu cầu.

Ràng buộc:

• ~1 \leq n \leq 60~
• ~0 \leq a_i \leq 100~

Sample Test

Input

4
73
67
38
33

Output

75
67
40
33

Cho số nguyên dương ~n~ ở hệ thập phân.

Yêu cầu

Hãy biểu diễn số ~n~ ở hệ nhị phân.

Input

Gồm nhiều dòng, mỗi dòng chứa một số nguyên dương ~n~ (~n < 10^{18}~).

Output

Mỗi dòng một kết quả tương ứng với giá trị của Input.

Sample Test

Input

79
24
29

Output

1001111
11000
11101

Cho số ~S~ được biểu diễn ở hệ nhị phân.

Yêu cầu

Hãy biểu diễn số ~S~ ở hệ thập phân.

Input

Gồm nhiều dòng, mỗi dòng chứa một số ~S~ (có tối đa 32 chữ số).

Output

Mỗi dòng một kết quả tương ứng với giá trị của Input.

Sample Test

Input

1001111
11000

Output

79
24

Cho số ~S~ được biểu diễn ở hệ thập phân.

Yêu cầu

Hãy biểu diễn số ~S~ ở hệ thập lục phân (hệ 16).

Input

Gồm nhiều dòng, mỗi dòng chứa một số ~N~ (có tối đa 32 chữ số).

Output

Mỗi dòng một kết quả tương ứng với giá trị của Input.

Sample Test

Input

557
897
384

Output

22D
381
180

Cho hai số nguyên dương ~n~, ~q~ và dãy số nguyên ~a_1, a_2, \dots, a_n~ (~a_i = i~; ~i = 1 \dots n~) và ~q~ thao tác được thực hiện theo thứ tự từ 1 đến ~q~. Với thao tác thứ ~i~ (~1 \leq i \leq q~) bạn được cho một số nguyên ~x_i~ (~1 \leq x_i \leq n~) và thực hiện yêu cầu hoán đổi giá trị của số có giá trị ~x_i~ với số đứng liền sau nó trong dãy số. Nếu ~x_i~ đang đứng cuối dãy số thì hoán đổi với số đứng liền trước nó.

Input

• Dòng đầu tiên ghi lần lượt hai số nguyên ~n~, ~q~ (~1 \leq n, q \leq 10^5~);
• ~q~ dòng tiếp theo, dòng thứ ~i~ (~1 \leq i \leq q~) ghi số nguyên ~x_i~ (~1 \leq x_i \leq n~)

Output

• In ra dãy số ~a_1, a_2, \dots, a_n~ sau khi thực hiện lần lượt ~q~ thao tác trong dữ liệu vào.

Sample Test

Input

5 3
3
5
1

Output

2 1 4 5 3

Giải thích: Dãy số ban đầu: ~1, 2, 3, 4, 5~

• Truy vấn ~x_1 = 3~: hoán đổi ~a_3~ với ~a_4 \rightarrow 1, 2, 4, 3, 5~
• Truy vấn ~x_2 = 5~: hoán đổi ~a_5~ với ~a_4 \rightarrow 1, 2, 4, 5, 3~
• Truy vấn ~x_3 = 1~: hoán đổi ~a_1~ với ~a_2 \rightarrow 2, 1, 4, 5, 3~

Ràng buộc:

• Có 70% số test tương ứng 70% số điểm có ~n, q \leq 2000~;
• Có 30% số test còn lại tương ứng 30% số điểm không có ràng buộc gì thêm.

Đang là giữa mùa đông và việc đi ra khỏi nhà là việc vô cùng khó khăn với Bờm. Ngày mai, bạn ấy được giao việc đi thu hoạch nấm trên khu đất nhà mình.

Có thể coi khu đất có nấm mà Bờm phải thu hoạch là một đoạn thẳng trên trục số. Có ~n~ vị trí có nấm, vị trí thứ ~i~ ở điểm ~x_i~ và có ~c_i~ cây nấm. Vì trời rất lạnh nên Bờm muốn chọn 1 điểm xuất phát để từ đó thu hoạch nấm những điểm có khoảng cách không quá ~k~ so với vị trí mà Bờm chọn sao cho tổng số nấm thu được là nhiều nhất có thể.

Yêu cầu

Hãy giúp Bờm tính xem tổng số nấm lớn nhất mà Bờm có thể thu hoạch được trong khoảng cách không quá ~k~ tính từ vị trí xuất phát mà Bờm đã chọn từ trước.

Input

• Dòng đầu là số ~n~ (~n \leq 10^6~) và số ~k~ (~k \leq 2 \times 10^6~): số vị trí có nấm.
• ~n~ dòng tiếp theo, mỗi dòng gồm 2 số ~c_i~ và ~x_i~ (~c_i \leq 10^4~, ~x_i \leq 10^6~): có ~c_i~ cây nấm ở điểm ~x_i~.

Output

Ghi ra một số nguyên duy nhất là tổng số nấm lớn nhất mà Bờm có thể thu hoạch được.

Sample Test

Input

4 3
4 7
10 15
2 2
5 1

Output

11

Giải thích: Bờm nên xuất phát từ vị trí 4 để có thể thu hoạch được nấm ở vị trí 1, 2 và 7. Tổng số nấm là: ~5 + 2 + 4 = 11~.

Ràng buộc

• Ít nhất 40% số điểm ứng với các test có ~n \leq 5000~.

Cho dãy số nguyên ~X_1, X_2, \dots, X_n~ ban đầu có giá trị tất cả các phần tử bằng 0. Cho một dãy gồm ~q~ truy vấn, mỗi truy vấn có dạng ~a~ ~b~ ~k~ với ý nghĩa tăng giá trị các phần tử có vị trí từ ~a~ đến ~b~ lên ~k~ đơn vị.

Yêu cầu

Hãy cho biết giá trị lớn nhất của dãy ~X_1, X_2, \dots, X_n~ sau khi thực hiện lần lượt ~q~ truy vấn.

Input

• Dòng đầu ghi 2 số nguyên ~n~, ~q~.
• ~q~ dòng tiếp theo, mỗi dòng ghi 3 số nguyên lần lượt là ~a~, ~b~, ~k~.

Output

Một số nguyên là giá trị lớn nhất của dãy số sau khi thực hiện ~q~ truy vấn.

Giới hạn:

• ~3 \leq n \leq 10^7~;
• ~1 \leq q \leq 2.10^5~;
• ~1 \leq a \leq b \leq n~;
• ~0 \leq k \leq 10^9~.

Sample Test

Input

5 3
1 2 100
2 5 100
3 4 100

Output

200

Cho số nguyên dương ~n~ và dãy số nguyên ~a_1, a_2, \dots, a_n~. Có ~q~ câu hỏi, mỗi câu hỏi được cho bởi hai số nguyên ~x_1~, ~x_2~ (~1 \leq x_1 \leq x_2 \leq n~), với mỗi câu hỏi hãy cho biết tổng các số từ vị trí ~x_1~ đến vị trí ~x_2~ trong dãy ~a_1, a_2, \dots, a_n~ là bao nhiêu?

Input

• Dòng đầu tiên ghi hai số nguyên dương ~n~, ~q~.
• Dòng thứ hai ghi lần lượt các số ~a_1, a_2, \dots, a_n~.
• ~q~ dòng tiếp theo, mỗi dòng ghi một cặp số nguyên ~x_1, x_2~.

Giới hạn:

• ~1 \leq n, q \leq 10^5~
• ~|a_i| \leq 10^9~

Output

Ghi trên ~q~ dòng, mỗi dòng là tổng các số từ ~x_1~ đến ~x_2~ trong dãy ~a_1, a_2, \dots, a_n~ tương ứng với thứ tự trong input.

Sample Test

Input

4 2
1 4 2 8
1 3
1 4

Output

7
15

Năm ngoái Conan chỉ mới bước vào học Tin học thật sự. Thế nhưng anh ta đã bị đàn em là Như Quỳnh thách đố bài toán sau:

Cho ~t \leq 10^5~ dòng, mỗi dòng của ~t~ có 1 số nguyên ~n~ (~n \leq 10^5~).

Dãy số ~A~ được xây dựng như sau:

• ~A[0] = 0~
• ~A[1] = 1~
• ~A[2i] = A[i]~
• ~A[2i + 1] = A[i] + A[i + 1]~

Yêu cầu

Nhiệm vụ của bạn là tìm số lớn nhất của dãy ~A~ từ 1 đến ~n~.

Input

• Dòng đầu tiên ghi số nguyên dương ~t~.
• ~t~ dòng sau, mỗi dòng là một số ~n~.

Output

• Có ~t~ dòng tương ứng với giá trị lớn nhất của các đoạn.

Sample Test

Input

2
5
10

Output

3
4

Một dãy số gồm ~n~ số nguyên được đánh số theo thứ tự từ 1 đến ~n~ và được xếp thành một vòng tròn theo chiều kim đồng hồ.

Yêu cầu

Hãy tìm tổng lớn nhất của ~k~ số liên tiếp nhau trong vòng tròn trên.

Input

• Dòng đầu tiên ghi hai số nguyên ~n~ và ~k~ (~0 < k < n \leq 10^5~) cách nhau một dấu cách.
• Dòng thứ hai ghi ~n~ số nguyên trong dãy, mỗi số có giá trị tuyệt đối không vượt quá 1000. Giữa các số được ghi cách nhau một dấu cách.

Output

Ghi một số nguyên duy nhất là tổng lớn nhất của ~k~ số liên tiếp nhau tìm được trong vòng tròn số.

Sample Test

Input

5 3
10 2 3 5 7

Output

22

Cho số nguyên dương ~n~ và dãy số nguyên ~a_1, a_2, \dots, a_n~.

Một phép dịch trái dãy số là chuyển số ~a_1~ về cuối dãy số, lúc đó các phần tử trong dãy số sẽ dịch qua bên trái 1 vị trí. Ví dụ với dãy số ~[3,2,1,5,6,4]~ sau khi thực hiện một phép dịch trái là ~[2,1,5,6,4,3]~; dịch trái thêm một lần nữa sẽ được ~[1,5,6,4,3,2]~.

Yêu cầu

Hãy cho biết giá trị các phần tử của dãy số sau khi dịch trái ~k~ lần.

Input

• Dòng đầu tiên ghi hai số nguyên dương ~n~ và ~k~ (~1 \leq k \leq n \leq 10^5~).
• Dòng thứ hai ghi lần lượt các số ~a_1, a_2, \dots, a_n~ (~1 \leq a_i \leq 10^6~).

Output

• Giá trị các phần tử của dãy số sau khi thực hiện dịch trái ~k~ lần.

Sample Test

Input

5 4
1 2 3 4 5

Output

5 1 2 3 4

Cho số nguyên dương ~n~ và dãy số nguyên ~a_1, a_2, \dots, a_n~. Hãy tìm dãy số ~B~ sao cho ~b_i = a_1 + a_2 + \dots + a_i~, hay nói cách khác ~b_i~ là tổng của ~i~ số đầu tiên trong dãy ~A~.

Input

• Dòng đầu tiên ghi số nguyên dương ~n~ (~1 \leq n \leq 10^6~).
• Dòng tiếp theo ghi lần lượt các số ~a_1, a_2, \dots, a_n~ (~|a_i| \leq 10^9~).

Output

Ghi lần lượt các số ~b_1, b_2, \dots, b_n~.

Sample Test

Input

4
1 4 3 2

Output

1 5 8 10