Xét dãy số nguyên dương ~a_1, a_2,...,a_n~, trong đó. Với mỗi truy vấn số nguyên x, hãy xác định số cặp ~(a_i,a_j)~ thỏa mãn các điều kiện: ~a_i+a_j \leq x (1 \leq i < j \leq n)~.

Input

• Dòng đầu tiên chứa số nguyên ~n~
• Dòng thứ hai chứa n số nguyên dương ~a_1,a_2,...,a_n(a_i \leq 10^9)~.
• Dòng thứ ba chứa số nguyên ~q~ – số lượng truy vấn trong file input
• ~q~ dòng tiếp theo, mỗi dòng chứa một số nguyên dương ~x (x \leq2 \times 10^9)~

Output

• ~q~ dòng, mỗi dòng là số cặp tìm được tương ứng với số ~x~ theo thứ tự trong file input.

Scoring

• ~30%~ số test tương ứng ~30%~ số điểm có ~n \leq 10^3; q \leq 10; a_i \leq 10^6~.
• ~30%~ số test khác tương ứng ~30%~ số điểm có ~q,n \leq 2 \times 10^3;a_i \leq 10^6~.
• ~40%~ số test còn lại tương ứng ~40%~ số điểm có ~n \leq 5 \times 10^4;q \leq 2 \times 10^3~.

Sample Input

5
5 10 2 7 9
2
15
13

Sample Output

7
5

Cho dãy số nguyên ~a_1,a_2,\dots ,a_n~ và số nguyên ~x~. Đếm số lượng bộ 3 số nguyên dương ~i<j<k≤n~ thỏa mãn ~a_i+a_j+a_k≤x~.</p>

Input

Dòng đầu chứa 2 số nguyên dương ~n,x\ (n≤10^4,\ x\le 10^9)~;

Dòng thứ 2 chứa ~n~ số nguyên không âm ~a_1,a_2,…,a_n~ (~0\le a_i≤10^8~).

Output

Một số nguyên duy nhất là số lượng bộ 3 số thỏa mãn.

Sample Input

5 9
2 3 5 1 6

Sample Output

4

Subtask

~30\%~ số test có ~n≤100~.

Địa điểm du lịch Dailai nổi tiếng với con đường Tùng-Trúc. Đó là một con đường dài và thẳng, dọc bên đường người ta trồng rất nhiều cây tùng và cây trúc. Với mục đích tạo điểm nhấn cho con đường, Ban quản lý khu du lịch muốn chọn một đoạn đường mà dọc theo nó có ít nhất ~a~ cây tùng và có ít nhất ~b~ cây trúc để trang trí. Sau khi khảo sát, Ban quản lý ghi nhận được vị trí của từng cây tùng và cây trúc. Trên con đường có tất cả ~n~ cây. Cây thứ ~i~ ở vị trí có khoảng cách đến vị trí bắt đầu con đường là ~d_i~ (~i = 1, 2, …, n~). Với kinh phí có hạn, Ban quản lý muốn chọn đoạn đường thỏa mãn điều kiện đã nêu với độ dài là ngắn nhất.

Yêu cầu: Cho ~a~, ~b~ và vị trí của ~n~ cây. Hãy tìm đoạn đường có độ dài ngắn nhất mà dọc theo đó có ít nhất ~a~ cây tùng và có ít nhất ~b~ cây trúc.

Input

• Dòng đầu chứa 3 số nguyên dương ~n, a, b~ (~a + b \leq n~);

• Dòng thứ ~i~ trong ~n~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~d_i~ (~d_i \leq 10^9~) và ~k_i~, trong đó ~d_i~ là khoảng cách của cây tính từ vị trí bắt đầu của con đường, ~k_i = 1~ nếu là cây tùng, ~k_i = 2~ nếu là cây trúc.

Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.

Output

• Một số nguyên là độ dài đoạn đường ngắn nhất tìm được, quy ước ghi số -1 nếu không tồn tại đoạn đường nào thỏa mãn điều kiện đặt ra.

Scoring

• 30% số điểm của bài có ~n \leq 300~.
• 30% số điểm của bài có ~n \leq 3000~.
• 40% số điểm của bài có ~n \leq 300000~.

Sample Input

7 2 2
20 2
30 1
25 1
35 1
60 2
65 2
10 1

Sample Output

35

Cho phép sai lệch không quá ~10^{-4}~.

Sample Input 1

1
5.6497 2.8700

Sample Output 1

0.8700

Sample Input 2

10
3.3075 4.3820
3.1289 1.7225
3.0509 3.7184
1.2061 2.4154
1.2605 1.1585
3.5097 5.6962
1.1909 5.9109
1.6837 4.7381
2.6821 4.6537
3.7975 2.9829

Sample Output 2

9.9989

Subtask

• 20% số điểm có ~N \le 10~;
• 40% số điểm có ~N \le 1000~;
• 40% số điểm không có ràng buộc gì thêm

Trọng số của bộ ba có thứ tự ~(x, y, z)~ bằng ~(x + y) × (y + z)~ nếu ~max(x, z) ≤ y~; hoặc bằng ~0~ nếu ~max(x, z) > y~.

Cho ba dãy số nguyên dương ~a = a_1, a_2, \dots , a_n,\ b = b_1, b_2, \dots , b_m,\ c = c_1, c_2, \dots , c_q~. Hãy tính tổng trọng số của tất cả các bộ ba ~(a_i , b_j , c_k)~ với ~1 ≤ i ≤ n,\ 1 ≤ j ≤ m,\ 1 ≤ k ≤ q~.

Input

• Dòng đầu tiên chứa ba số nguyên dương ~n, m, q~;
• Dòng thứ hai chứa ~n~ số nguyên dương: ~a_1, a_2, \dots, a_n\ (a_i ≤ 10^9)~;
• Dòng thứ ba chứa ~m~ số nguyên dương: ~b_1, b_2, \dots , b_m\ (b_i ≤ 10^9)~;
• Dòng thứ tư chứa ~q~ số nguyên dương: ~c_1, c_2, \dots , c_q\ (c_i ≤ 10^9)~.

Output

• Ghi một số nguyên là tổng trọng số sau khi chia lấy dư cho ~1000000007~.

Scoring

• 12% số điểm của bài có ~n \leq 20~.
• 28% số điểm của bài có ~n \leq 1000~.
• 60% số điểm của bài có ~n \leq 10^5~.

Sample Input

4 3 5
1 4 2 3
4 6 1
6 3 2 4 2

Sample Output

2300

Trong khu vườn, người ta trồng một hàng cây chạy dài gồm có ~N~ cây, mỗi cây có độ cao là ~a_1, a_2, \dots, a_N~. Người ta cần lấy ~M~ mét gỗ bằng cách đặt cưa máy sao cho lưỡi cưa ở độ cao ~H~ (mét) để cưa tất cả các cây có độ cao lớn hơn ~H~ (dĩ nhiên những cây có độ cao không lớn hơn ~H~ thì không bị cưa).

Ví dụ: Nếu hàng cây có các cây với độ cao tương ứng là ~20; 15; 10; 18~ mét, cần lấy ~7~ mét gỗ. Lưỡi cưa đặt tại độ cao hợp lí là ~15~ mét thì độ cao của các cây còn lại sau khi bị cưa tương ứng là ~15; 15; 10; 15~ mét. Tổng số mét gỗ lấy được là ~8~ mét (dư ~1~ mét).

Yêu cầu: Hãy tìm vị trí đặt lưỡi cưa hợp lí (số nguyên ~H~ lớn nhất) sao cho lấy được ~M~ mét gỗ và số mét gỗ dư ra là ít nhất.

Input:

File "WOOD.INP" gồm:

• Dòng thứ nhất chứa ~2~ số nguyên dương ~N~ và ~M~ ~(1 \le N \le 10^6;\ 1 \le M \le 2 \times 10^9)~ cách nhau một dấu cách.
• Dòng thứ hai chứa ~N~ số nguyên dương ~a_i~ là độ cao của mỗi cây trong hàng ~(1 \le a_i \le 10^9\; i=1 \dots N)~, mỗi số cách nhau ít nhất một dấu cách.

Output:

• File "WOOD.OUT" một số nguyên cho biết giá trị cần tìm.

Sample Input 1

4 7
20 15 10 18

Sample Output 1

15

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

Chủ đề vẫn là con game Arknights mà Loli đang chơi.

Arknights có rất nhiều màn chơi. Ta có thể đơn giản hóa rằng, tựa game này có ~n~ màn chơi tất cả. Mỗi màn chơi sẽ yêu cầu người chơi phải có cấp độ không dưới cấp độ mà màn chơi yêu cầu. Gọi cấp độ tối thiểu để chơi màn chơi thứ ~i~ là ~h_i~.

Các màn chơi sẽ càng ngày càng khó, đòi hỏi người chơi phải có cấp độ càng ngày càng cao. Nói cách khác, ta có ~h_i \le h_{i+1}~ với mọi ~i < n~.

Do Loli rất yêu tựa game này nên Loli lập ra ~q~ tài khoản, mỗi tài khoản được đánh số thứ tự từ ~1~ đến ~q~. Hiện tại cấp độ tài khoản thứ ~i~ của Loli là ~x_i~, và Loli muốn biết rằng, nếu hắn cố gắng lên thêm ~y_i~ cấp độ nữa ở tài khoản này, thì hắn sẽ qua được thêm bao nhiêu màn chơi?

Input

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

• Dòng đầu tiên chứa một số nguyên dương ~n~ ~(1\le n\le 5\times 10^5)~ là số màn chơi.
• Dòng thứ hai chứa ~n~ số nguyên dương ~h_i~ ~(1\le h_i\le 2\times 10^9)~ là cấp độ tối thiểu để chơi màn chơi thứ ~i~.
• Dòng thứ ba chứa số nguyên dương ~q~ ~(1\le q \le 10^5)~ là số tài khoản của Loli.
• ~q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~x_i~ và ~y_i~ ~(1\le x_i, y_i \le 10^9)~ thể hiện câu hỏi của Loli ở tài khoản thứ ~i~.

Output

Ghi ra tệp THANGCAP.OUT gồm:

• ~q~ dòng, dòng thứ ~i~ chứa một số nguyên tương ứng với số màn chơi có thể qua được thêm sau khi thăng cấp ở tài khoản thứ ~i~.

Sample Input 1

5
2 6 7 10 15
3
1 3
7 8
5 20

Sample Output 1

1
2
4

Giải thích

• Ở tài khoản thứ ~1~, Loli thăng cấp từ cấp ~1~ lên cấp ~1+3=4~, qua thêm được màn chơi thứ ~1~.
• Ở tài khoản thứ ~2~, Loli thăng cấp từ cấp ~7~ lên cấp ~7+8=15~, qua thêm được ~2~ màn chơi là màn thứ ~4~ và ~5~.
• Ở tài khoản thứ ~3~, Loli thăng cấp từ cấp ~5~ lên cấp ~5+20=25~, qua thêm được ~4~ màn chơi từ màn thứ ~2~ đến màn thứ ~5~.

Ràng buộc

• ~40\%~ test có ~q\times n \le 10^8~;
• ~60\%~ test còn lại không có ràng buộc gì thêm.

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

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.

Cho dãy số ~A_1, A_2,….,A_n~ và ~M~ truy vấn. Có 2 loại truy vấn:

• Loại 1: ~1~ ~x~ ~y~ – gán giá trị của ~A_x=y~.
• Loại 2: ~2~ ~l~ ~r~ (~l \leq r~)– Yêu cầu tìm giá trị nhỏ nhất trong đoạn [~l,r~]

Input

• Dòng đầu chứa số 2 nguyên ~N,M~ (~N,M \leq 10^5~)
• Dòng thứ 2 chứa ~N~ số nguyên dương ~A_1 A_2…A_n (A_i \leq 10^9)~

~M~ dòng tiếp theo chứa ~M~ truy vấn thuộc một trong 2 loại. Tất cả các số đều dương và nhỏ hơn ~10^9~

Output

Kết quả của các truy vấn loại 2 theo thứ tự.

Sample Input

4 4
2 6 8 7
2 1 3
1 2 1
2 1 3
2 3 4

Sample Output

2
1
7

Bé Loli đáng iu thích chơi đùa với trái tim lũ con trai mảng. Loli có mảng ~a~, chứa ~n~ phần tử nguyên dương, đánh số từ ~1~ đến ~n~.

Ngoài ra Loli còn có ~m~ câu hỏi liên quan tới mảng, mỗi câu hỏi có cấu trúc là một cặp số nguyên ~(l_j, r_j)~ ~(1\le l_j \le r_j \le n)~. Với mỗi câu hỏi ~(l_j, r_j)~, Loli sẽ bắt đứa em của mình phải đếm có bao nhiêu số ~x~ thỏa mãn, sao cho ~x~ xuất hiện đúng ~x~ lần trong các số từ ~a_{l_j}, a_{l_{j+1}}, \dots, a_{r_j}~.

Bạn hãy giúp đứa em của Loli trả lời toàn bộ câu hỏi của Loli, để nó còn được chơi Free Fire trong yên bình.

Input

• Dòng đầu tiên chứa 2 số nguyên dương ~n, m\ (1\le n, m\le 10^5)~ - là kích cỡ của mảng ~a~ và số lượng câu hỏi.
• Dòng tiếp theo chứa ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ ~(1\le a_i \le 10^9)~.
• ~m~ dòng cuối cùng chứa ~m~ câu hỏi Loli đưa ra. Dòng thứ ~j~ là câu hỏi thứ ~j~ bao gồm cặp số nguyên ~(l_j, r_j)~ ~(1\le l_j \le r_j \le n)~.

Output

• In ra ~m~ dòng, mỗi dòng một số nguyên là đáp án của ~m~ câu hỏi. Dòng thứ ~j~ trả lời câu hỏi thứ ~j~.

Sample Input

7 2
3 1 2 2 3 3 7
1 7
3 4

Sample Output

3
1

Cho dãy ~n~ số nguyên ~a_1, a_2, ..., a_n~ và ~m~ truy vấn. Mỗi truy vấn có dạng 2 số nguyên ~u, v~ với ý nghĩa đếm xem trong dãy con ~a_u, a_{u+1}, ..., a_v~ có bao nhiêu giá trị khác nhau mà các giá trị này xuất hiện đúng 2 lần?

Input

• Dòng đầu ghi hai số nguyên dương ~n, m (1 \leq n, m \leq 5 \times 10^5)~
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, ..., a_n (0 \leq a_i \leq 10^9)~
• ~m~ dòng cuối, mỗi dòng ghi 2 số nguyên ~u, v~ mô tả một truy vấn.

Output

• Với mỗi truy vấn in ra một dòng một số nguyên - kết quả tìm được.

Sample Input

5 1
1 2 1 1 1
1 3

Sample Output

1

Sample Input 1

3 2
1 2 1
1 2
1 3

Sample Output 1

3
6

Sample Input 2

8 3
1 1 2 2 1 3 1 1
2 7
1 6
2 7

Sample Output 2

20
20
20