Dạo một vòng Facebook, Loli cảm thấy rất chán khi thấy giới trẻ cứ thấy cái gì đấy là lại muốn "uoc j uoc j". Vì vậy Loli nhờ các bạn coder giải quyết vấn nạn nhức nhối này bằng việc tạo ra chương trình trả lời hết các câu "uoc j".

Input:

• Dòng đầu tiên chứa một số nguyên ~j~ ~(1 \le j \le 10^{12})~.

Output:

• Gồm một dãy số nguyên tăng dần là ước của ~j~.

Sample Input 1

3

Sample Output 1

1 3

Sample Input 2

69

Sample Output 2

1 3 23 69

Trong đợt bùng phát dịch COVID-19 đầu tiên, xét nghiệm trên diện rộng với từng người là một trong những chiến lược tốt để kiểm soát và ngăn chặn dịch lây lan mạnh. Tuy nhiên, xét nghiệm bằng PCR tiêu tốn khá nhiều thời gian và tiền bạc. Một cách làm hiệu quả để tăng tốc quá trình và tiết kiệm tài nguyên vốn đã hạn hẹp là thực hiện xét nghiệm theo từng hộ gia đình. Với cách làm này, thay vì xét nghiệm từng người, ta hợp mẫu thử của p người và xét nghiệm trong một lần. Nếu cho ra kết quả 1 vạch, chúng ta có thể kết luận rằng cả p người đều âm tính. Ngược lại, nếu chẳng may kết quả có thêm vạch nữa, chúng ta lại phải xét nghiệm riêng từng người để xem ai là người bị nhiễm virus.

Trong một khu vực có ~n~ hộ gia đình, mỗi hộ được đánh số từ ~0~ đến ~n-1~. Hộ thứ ~i~ có ~a_i~ thành viên. Sau khi làm ~n~ xét nghiệm cho ~n~ hộ, ta có ~k~ hộ có kết quả dương tính. Nhiệm vụ của bạn là tính số lần xét nghiệm riêng lẻ tối đa và tối thiểu mà nhân viên y tế phải làm.

Input:

• Dòng đầu tiên chứa số nguyên ~n\ (1 \le n \le 10^5)~ và ~k\ (k \le n)~ với ý nghĩa như trên.
• Dòng tiếp theo chứa ~n~ số nguyên ~p_i\ (1 \le p_i \le 10^4)~ là số ngưởi trong hộ thứ ~i~.

Output:

• Gồm 2 số nguyên dương là số lần xét nghiệm thêm tối thiểu và tối đa.

Sample Input 1

5 2
2 3 6 4 5

Sample Output 1

5 11

Sample Input 2

3 1
1 2 3

Sample Output 2

0 3

Giải thích

• Ở testcase 1: Nếu hộ thứ ~0~ và ~1~ dương tính thì ta chỉ cần làm ~5~ lần xét nghiệm riêng. Nếu hộ thứ ~2~ và ~4~ dương tính thì ta cần làm ~11~ lần xét nghiệm riêng. ~5~ lần là ít nhất, ~11~ lần là nhiều nhất.
• Ở testcase 2: Nếu hộ thứ ~0~ dương tính thì ta không cần xét nghiệm thêm vì hộ này chỉ có ~1~ người. Nếu hộ thứ ~2~ dương tính thì ta cần làm ~3~ lần xét nghiệm nữa.

Loli là một chàng trai khôi ngô tuấn tú. Từ nhỏ cho đến lớn, ai cũng có mơ ước, mộng tưởng, để mà nuôi ấp ủ, để mà theo đuổi, và Loli cũng thế. Loli ước rằng mình có thể thực hiện một hành động, nghe thì đơn giản nhưng lại không hề đơn giản chút nào. Đó chính là hành động Mang tiền về cho mẹ. Nhưng trần đời, những gì bạn thấy, chưa chắc bạn đã thấy gì. Ước mơ gì thì cũng phải có tiền bạc mới có thể trở thành hiện thực. Và tiền không dễ để kiếm. Loli suy nghĩ mãi và cuối cùng, thay vì bỏ ngang Bách khoa Cơ khí sang làm ngành IT, anh đã quyết định đi đầu tư "trứng khoán".

Con đường đầu tư "trứng khoán" cũng có nhiều gian truân. Đầu tiên là việc học. Anh đã theo học một tradẻ nổi tiếng, với lời cam kết: "Học với tôi, ai cũng có thể trở thành Ông hoàng Thổi nến". Sau khi học 6 phút 9 giây, theo như lời cao nhân: "Học phải đi đôi với hành", Loli quyết định All In bắt đáy luôn. Nhưng khổ nỗi, có quá nhiều cổ phiếu Loli không thể theo (vì rõ ràng không có ziền), và ngược lại, có nhiều cổ phiếu Loli có thể theo. Loli đang có ~X~ tiền trong tài khoản. Loli mù code và muốn bạn code cho anh ấy một công cụ với mục đích tìm giá trị cổ phiếu có giá đắt nhất mà Loli có thể theo được. Như lời người đi trước, code ra tiền là có thật.

Input:

• Dòng đầu tiên chứa một số nguyên ~N (1 \le N \le 10^5)~ – số cổ phiếu.
• Dòng thứ 2 cho ~N~ số nguyên ~a[i]~ ~(1 \le a[i] \le 10^9)~ – giá trị cổ phiếu thứ ~i~. Thật tiện lợi rằng ~a[i]~ luôn nhỏ hơn hoặc bằng ~a[i+1]~ với mọi ~i~ thuộc khoảng ~[1; N-1]~.
• Dòng thứ 3 chứa một số nguyên ~Q (1 \le Q \le 10^5)~ là số truy vấn cần thực hiện.
• ~Q~ dòng tiếp theo, mỗi dòng bao gồm một số nguyên ~X~ duy nhất ~(1 \le X \le 10^9)~ — thể hiện số tiền của Loli trong một truy vấn.

Output:

• Gồm ~Q~ dòng, mỗi dòng in ra kết quả truy vấn tương ứng thỏa mãn đề bài. Nếu không có số nào thỏa mãn, in ra ~-1~.

Sample Input

5
1 1 2 4 5
2
3
5

Sample Output

2
5

Cửa hàng sách 210VN dạo gần đây đang vắng khách một cách lạ kỳ. Sau khi tìm hiểu vài khóa tăng sale, họ đã tâm đắc với chiến dịch kích cầu nổi tiếng: "mua ~x~ trả tiền ~x-1~". Ưu đãi rất có lợi dành cho các bạn fan cứng của nhiều thể loại sách, đặc biệt là thể loại truyện segg. Ưu đãi vô cùng đơn giản: Khi mua ~x~ cuốn truyện segg sướt mướt, khách hàng sẽ được miễn phí cuốn rẻ nhất trong ~x~ cuốn này. Ví dụ, với ~x=3~, khi mua hai cuốn truyện đình đám 177013 và 161531, khách hàng được tặng miễn phí cuốn 228922 đầy căng cực.

Hơn nữa, nếu khách hàng muốn mua nhiều hơn ~x~ cuốn, họ có thể chia số sách muốn mua thành các nhóm, mỗi nhóm gồm từ ~1~ tới ~x~ cuốn. Trong mỗi nhóm ~x~ cuốn, khách hàng sẽ được tặng cuốn có giá thấp nhất trong ~x~ cuốn này. Các nhóm có số lượng sách nhỏ hơn ~x~ không được hưởng ưu đãi.

Vốn là fan cứng yêu thích các tác phẩm sến súa ướt át, Loli ngây thơ muốn mua ~n~ cuốn truyện segg với giá ~c_1,c_2,\ldots,c_n~. Hãy tìm cách để mua ~n~ cuốn này với giá thấp nhất dựa trên ưu đãi "mua ~x~ trả tiền ~x-1~" của cửa hàng.

Input:

Lấy từ tệp DISCOUNT.INP gồm:

• Dòng đầu tiên chứa số nguyên ~n,x\ (2\le n,x\le10^5)~ là số sách muốn mua và ưu đãi của cửa hàng.
• Dòng 2 chứa ~n~ số nguyên ~c_i\ (1 \le c_i \le 9696969)~ là giá tiền của cuốn sách thứ ~i~.

Output:

• Ghi ra tệp DISCOUNT.OUT là tổng số tiền nhỏ nhất cần phải trả.

Sample Input 1

4 3
3 2 3 2

Sample Output 1

8

Sample Input 2

6 3
6 4 5 5 5 5

Sample Output 2

21

Giải thích

Ở test đầu, mua 3 cuốn có giá là ~3,\ 2,\ 3~, ta được free cuốn ~2~ đồng. Sau đó mua cuốn còn lại.

Ràng buộc

• 50% số test có ~n\le5000~.
• 50% số test còn lại không có ràng buộc gì thêm.

Cho dãy số ~A~ gồm ~n~ số nguyên dương ~A_1, A_2, \dots, A_n~. Một bộ ba số được gọi là bộ số tam giác, nếu ba số này là độ dài ba cạnh của một tam giác.

Yêu cầu: Hãy đếm xem trong dãy ~A~ có bao nhiêu bộ số tam giác ~(A_i, A_j, A_k)~ với ~i, j, k~ đôi một khác nhau.

Input:

Vào từ file văn bản BSTG.INP gồm:

• Dòng đầu chứa số nguyên ~n\ (3 ≤ n ≤ 1000)~.
• Dòng tiếp theo chứa ~n~ số nguyên dương trong dãy ~A\ (A_i ≤ 10^9)~.

Output:

• Ghi ra file văn bản BSTG.OUT số lượng bộ số tam giác trong dãy đã cho.

Ví dụ:

BSTG.INP

5
4 3 1 5 7

BSTG.OUT

3

Giải thích

Có ~3~ bộ số tam giác là ~(4, 3, 5),\ (4, 5, 7)~ và ~(3, 5, 7)~.

Subtask:

• ~60\%~ số test có ~n \le 500~.
• ~40\%~ số test không có ràng buộc gì thêm.

Nhà cung cấp dịch vụ viễn thông Mobi đã khảo sát số lượng người sẽ dùng dịch vụ trên một con đường thẳng mới được xây dựng và đánh dấu lại những vị trí trên con đường này. Đầu con đường được đánh tọa độ bắt đầu từ ~0~. Tại vị trí có tọa độ ~X~ (~X~ nguyên dương) có số lượng người sẽ sử dụng dịch vụ là ~Y~. Trước mắt, nhà cung cấp dịch vụ cần đặt một trạm phát sóng có bán kính phủ sóng là ~K~ đơn vị chiều dài để phủ sóng cho một số người sử dụng dịch vụ trên con đường này.

Yêu cầu: Bạn hãy xác định vị trí đặt trạm phát sóng (tọa độ nguyên dương) sao cho trạm có thể phục vụ được số lượng người sử dụng nhiều nhất có thể.

Input:

Vào từ file văn bản "MOBI.INP":

• Dòng đầu tiên ghi hai số nguyên ~N~ và ~K~ ~(0 < N \le 10^6,\ 0 < K \le 2 \times 10^6)~, trong đó ~N~ là số điểm dân cư đã được đánh dấu, ~K~ là bán kính phủ sóng của trạm.
• Trong ~N~ dòng tiếp theo, dòng thứ ~i\ (i=1..N)~ ghi hai số nguyên ~X~ và ~Y~ cho biết tại vị trí ~X~ có số lượng người dùng là ~Y (0 \le X \le 10^6,\ 0 \le Y \le 10^4)~. Các số trên cùng dòng viết cách nhau ít nhất một dấu cách.

Output:

Ghi ra file văn bản "MOBI.OUT" một số nguyên cho biết số người dùng nhiều nhất sẽ được phục vụ.

Sample Input 1

4 3
7 4
15 10
2 2
1 5

Sample Output 1

11

Bạn được cho bốn danh sách, mỗi danh sách gồm ~N~ số nguyên (các danh sách này ký hiệu là ~A, B, C, D~). Bạn được yêu cầu đếm số bộ ~(a,b,c,d)~ với ~a \in A,\ b \in B,\ c \in C,\ d \in D~ sao cho ~a+b+c+d=0~.

Input

Vào từ tệp SUM.INP:

• Dòng đầu tiên ghi số nguyên dương ~N\ (N \le 4000)~.
• ~N~ dòng tiếp theo, mỗi dòng ghi bốn số tương ứng với các số trong danh sách ~A, B, C, D~.

Output

• Ghi ra tệp SUM.OUT một số nguyên duy nhất là số bộ số tìm được.

Sample Input 1

6 
-45 22 42 -16 
-41 -27 56 30 
-36 53 -37 77 
-36 30 -75 -46 
26 -38 -10 62 
-32 -54 -6 45

Sample Output 1

5

Giải thích

Các bộ số tìm được là: ~(-45;-27; 42; 30);\ (26;30;-10;-46);\ (-32; 22; 56;-46);\ (-32; 30;-75; 77);\ (-32;-54; 56; 30)~

Cho bảng ~A~ kích thước ~m \times n~, các hàng của bảng được đánh số từ ~1~ tới ~m~ và các cột của bảng được đánh số từ ~1~ tới ~n~. Ô nằm trên hàng ~i~ và cột ~j~ được điền một số nguyên có giá trị bằng ~i^2 + j^2~.

Hỏi nếu đem các số trên bảng xếp theo thứ tự không giảm (tăng dần) và đánh số từ ~1~ tới ~m \times n~ thì số thứ ~k~ mang giá trị bao nhiêu.

Input

Vào từ tệp NUMORDER.INP:

• Một dòng chứa 3 số nguyên dương ~n, m, k\ (k \le m \times n \le 10^9)~;

Output

Ghi ra tệp NUMORDER.OUT

• Một số nguyên là kết quả tìm được.

Sample Input 1

3 5 10

Sample Output 1

18

Giải thích:

2, 5, 5, 8, 10, 10, 13, 13, 17, 18, 20, 25, 26, 29, 34.