Bạn được cho một dãy gồm ~n~ số nguyên dương đôi một phân biệt và một số nguyên dương ~k~. Một số ~x~ trong dãy được gọi là đặc biệt nếu trong dãy cũng tồn tại đầy đủ các giá trị ~x, x^2, x^3, \dots, x^k~.

Yêu cầu

Hãy đếm xem trong dãy có bao nhiêu số là số đặc biệt.

Dữ liệu

• Dòng đầu tiên chứa hai số nguyên ~n, k~ ~(1 \le n \le 1000000,\ 1 \le k \le 10)~.
• Dòng thứ hai chứa ~n~ số nguyên dương đôi một phân biệt ~a_i~ ~(1 \le a_i \le 10000)~.

Kết quả

In ra một số nguyên: số lượng số đặc biệt trong dãy.

Ví dụ

Ví dụ 1

Input

9 3
1 2 3 4 8 9 16 32 64

Output

3

Ví dụ 2

Input

9 2
1 2 3 4 8 9 16 32 64

Output

5

Ví dụ 3

Input

9 2
1 2 3 4 5 6 7 8 9

Output

3

Giải thích

Ví dụ 1

Với ~k=3~:

• ~1~ là số đặc biệt vì ~1^1=1, 1^2=1, 1^3=1~ đều có trong dãy.
• ~2~ là số đặc biệt vì ~2^1=2, 2^2=4, 2^3=8~ đều có trong dãy.
• ~4~ là số đặc biệt vì ~4^1=4, 4^2=16, 4^3=64~ đều có trong dãy. Các số còn lại không thỏa điều kiện, nên đáp án là ~3~.

Ví dụ 2

Với ~k=2~, một số ~x~ đặc biệt khi ~x~ và ~x^2~ cùng xuất hiện:

• Các số đặc biệt là ~1,2,3,4,8~ (tương ứng có ~1,4,9,16,64~). Do đó có ~5~ số đặc biệt.

Ví dụ 3

Với dãy ~1..9~ và ~k=2~:

• Các số thỏa ~x^2 \le 9~ và có mặt trong dãy là ~1,2,3~ (vì ~1^2=1, 2^2=4, 3^2=9~). Vậy đáp án là ~3~.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le n \le 1000000~
• ~1 \le k \le 10~
• ~1 \le a_i \le 10000~
• Các ~a_i~ đôi một phân biệt

Chấm điểm

• Subtask ~1~ (~30%~): ~1 \le n \le 100, \ k=2~
• Subtask ~2~ (~30%~): ~1 \le n \le 100, \ 1 \le k \le 10~
• Subtask ~3~ (~20%~): ~1 \le n \le 10000, \ 1 \le k \le 10, \ a_i=i~
• Subtask ~4~ (~20%~): ~1 \le n \le 1000000, \ 1 \le k \le 10~

Nhân dịp Tết Nguyên Đán, các bạn Chuyên Tin đến một vườn hoa mới xây dựng của thành phố để ngắm hoa dưới ánh trăng. Vườn hoa là một lưới hình chữ nhật kích thước ~W \times H~. Trong vườn đã có sẵn ~N~ bông hoa, mỗi bông hoa nằm tại một ô ~(x_i, y_i)~ (các vị trí đôi một khác nhau).

Mỗi bông hoa tỏa hương ra các ô xung quanh, và độ thơm giảm dần khi đi xa. Độ thơm ban đầu tại ô có hoa là ~K~.

Khoảng cách giữa hai ô ~(a,b)~ và ~(u,v)~ được tính theo khoảng cách Manhattan: ~d = |a-u| + |b-v|~.

Độ thơm tại một ô ~(x,y)~ được xác định bởi:

• Gọi ~d~ là khoảng cách từ ~(x,y)~ tới bông hoa gần nhất trong vườn.
• Khi đó độ thơm tại ~(x,y)~ là ~max(0, K - d)~.

Nam muốn trồng thêm một bông hoa tại vị trí có độ thơm nhỏ nhất trong vườn. Hãy xác định giá trị độ thơm nhỏ nhất đó.

Yêu cầu

Tính và in ra độ thơm nhỏ nhất trong toàn bộ các ô của vườn.

Dữ liệu

• Dòng đầu chứa ~4~ số nguyên dương ~W, H, N, K~ với ~1 \le N \le W \times H \le 10^5~, ~1 \le K \le 10^9~.
• ~N~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~x_i, y_i~ với ~1 \le x_i \le W~, ~1 \le y_i \le H~, cho biết vị trí bông hoa thứ ~i~.

Kết quả

In ra một số nguyên duy nhất: giá trị độ thơm nhỏ nhất trong vườn.

Ví dụ

Ví dụ 1

Input

3 3 2 10
2 1
2 3

Output

8

Giải thích

Ví dụ 1

Hai ô có độ thơm nhỏ nhất là ~(1,2)~ và ~(3,2)~. Khoảng cách từ mỗi ô này đến bông hoa gần nhất là ~2~, nên độ thơm là ~K-2 = 10-2 = 8~.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le N \le W \times H \le 10^5~
• ~1 \le K \le 10^9~
• ~1 \le x_i \le W~, ~1 \le y_i \le H~
• Các vị trí ~(x_i, y_i)~ đôi một khác nhau

Chấm điểm

• Subtask ~1~ (~20%~): ~N=1~ (cả vườn chỉ có đúng một bông hoa)
• Subtask ~2~ (~20%~): ~1 \le W, H \le 100~
• Subtask ~3~ (~20%~): ~W=1~ và ~1 \le H \le 10^5~
• Subtask ~4~ (~40%~): Không có giới hạn thêm

Sắp tới thành phố ~A~ sẽ tổ chức một lễ hội hoa để trưng bày và quảng bá các loài hoa đặc trưng. Trong lễ hội, ban tổ chức tổ chức một trò chơi: người tham gia được chọn một vùng hoa hình chữ nhật trong khu vườn sao cho tổng độ đẹp của các bông hoa trong vùng đó là lớn nhất.

Khu vườn được mô tả bởi lưới hình chữ nhật kích thước ~N \times M~. Ô ở hàng ~i~, cột ~j~ có tọa độ ~(i,j)~. Tại mỗi ô có thể có hoặc không có bông hoa:

• Nếu ~a_{i,j} > 0~ thì có hoa với độ đẹp là ~a_{i,j}~.
• Nếu ~a_{i,j} = 0~ thì ô đó trống (không có hoa).

Người chơi sẽ chọn một hình chữ nhật có các cạnh song song với cạnh khu vườn, thỏa mãn:

• Diện tích không vượt quá ~S~.
• Số ô trống trong hình chữ nhật không vượt quá ~X~.

Hãy tìm tổng độ đẹp lớn nhất có thể đạt được.

Yêu cầu

Chọn một hình chữ nhật trong lưới sao cho:

• ~\text{diện tích} \le S~
• ~\text{số ô có } a_{i,j}=0 \le X~ và tổng ~\sum a_{i,j}~ trong hình chữ nhật là lớn nhất.

Nếu không tồn tại hình chữ nhật nào thỏa mãn, in ra ~-1~.

Dữ liệu

• Dòng đầu chứa bốn số nguyên không âm ~N, M, S, X~ ~(1 \le N, M \le 500,\ 1 \le S \le N \times M,\ 0 \le X \le N \times M)~.
• ~N~ dòng tiếp theo, mỗi dòng chứa ~M~ số nguyên ~a_{i,1}, a_{i,2}, \dots, a_{i,M}~ ~(0 \le a_{i,j} \le 1000)~.

Kết quả

In ra một số nguyên duy nhất: tổng độ đẹp lớn nhất của một hình chữ nhật thỏa mãn yêu cầu. Nếu không có cách chọn, in ra ~-1~.

Ví dụ

Ví dụ 1

Input

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

Output

36

Giải thích

Ví dụ 1

Chọn hình chữ nhật gồm các hàng ~1..4~ và các cột ~1..2~ (diện tích ~4 \times 2 = 8~). Trong vùng này chỉ có đúng ~1~ ô trống (tại ~(3,2)~), nên thỏa ~X=1~. Tổng độ đẹp là: ~(6+7) + (3+3) + (8+0) + (7+2) = 36~.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le N, M \le 500~
• ~1 \le S \le N \times M~
• ~0 \le X \le N \times M~
• ~0 \le a_{i,j} \le 1000~

Chấm điểm

• ~50%~ số điểm: ~N, M \le 100~
• ~50%~ số điểm còn lại: không có giới hạn thêm

Trên một đoạn đường thẳng (trục số), một đàn kiến tìm thấy ~n~ đống thóc được đánh số từ ~1~ đến ~n~. Đống thóc thứ ~i~ nằm tại vị trí ~x_i~ trên trục số và chứa ~a_i~ hạt thóc. Kiến chúa dự định xây dựng ~k~ kho tại các tọa độ nguyên để cất giữ thóc.

Sau khi xây kho, mỗi đống thóc sẽ được giao cho đúng một con kiến phụ trách vận chuyển (tổng cộng có ~n~ con kiến).

Với con kiến phụ trách đống thóc ~i~:

• Trước khi vận chuyển, nó xác định kho gần đống thóc ~i~ nhất và đứng ở kho đó.
• Khi có lệnh vận chuyển, nó chạy từ kho đến đống thóc, lấy đúng ~1~ hạt thóc, rồi mang về kho; lặp lại cho đến khi chuyển hết ~a_i~ hạt.
• Tốc độ di chuyển là ~1~ đơn vị độ dài / giây (dù có đang mang thóc hay không).
• Thời gian lấy thóc ở đống và cất thóc vào kho coi như không đáng kể.

Tất cả ~n~ con kiến bắt đầu làm việc đồng thời ngay khi có lệnh vận chuyển.

Yêu cầu

Hãy chọn vị trí xây ~k~ kho (tọa độ nguyên, có thể trùng vị trí đống thóc) sao cho thời gian từ lúc phát lệnh đến khi tất cả thóc được chuyển xong về các kho là nhỏ nhất.

Dữ liệu

• Dòng đầu tiên chứa hai số nguyên dương ~n, k~ với ~n \le 10^5~, ~k \le n~.
• Dòng thứ hai chứa ~n~ số nguyên không âm ~x_1, x_2, \dots, x_n~ mô tả vị trí các đống thóc ~(x_i \le 10^6)~.
• Dòng thứ ba chứa ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ mô tả số hạt thóc ở mỗi đống ~(a_i \le 10^6)~.

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

Kết quả

In ra một số nguyên duy nhất: thời gian nhỏ nhất (tính bằng giây) để chuyển hết thóc về các kho theo phương án xây kho tối ưu.

Ví dụ

Ví dụ 1

Input

4 2
0 20 50 60
70 150 200 200

Output

2000

Giải thích

Ví dụ 1

Xây hai kho tại tọa độ ~14~ và ~55~.

• Đống ~1~: ~|0-14|=14~ ⇒ thời gian ~2 \cdot 14 \cdot 70 = 1960~.
• Đống ~2~: ~|20-14|=6~ ⇒ thời gian ~2 \cdot 6 \cdot 150 = 1800~.
• Đống ~3~: ~|50-55|=5~ ⇒ thời gian ~2 \cdot 5 \cdot 200 = 2000~.
• Đống ~4~: ~|60-55|=5~ ⇒ thời gian ~2 \cdot 5 \cdot 200 = 2000~.

Tất cả kiến làm song song nên tổng thời gian hoàn thành là giá trị lớn nhất trong các thời gian trên, bằng ~2000~.

Ràng buộc và chấm điểm

Ràng buộc

• ~n \le 10^5~, ~k \le n~
• ~0 \le x_i \le 10^6~
• ~1 \le a_i \le 10^6~
• Vị trí kho là số nguyên, có thể trùng vị trí một đống thóc

Khi viết phân số ~\dfrac{a}{b}~ dưới dạng thập phân, ta có thể thu được một số thập phân hữu hạn hoặc một số thập phân vô hạn tuần hoàn. Với trường hợp hữu hạn, ta có thể coi nó như vô hạn bằng cách thêm vô hạn chữ số ~0~ vào sau chữ số cuối cùng sau dấu chấm thập phân.

Ví dụ:

• ~\dfrac{100}{8} = 12.5000\dots~
• ~\dfrac{17}{3} = 5.6666\dots~
• ~\dfrac{99}{140} = 0.70714285714285\dots~

Yêu cầu

Đánh số các chữ số sau dấu chấm thập phân của biểu diễn thập phân của ~\dfrac{a}{b}~ từ trái qua phải bắt đầu từ ~1~. Hãy xác định chữ số thứ ~k~.

Dữ liệu

Một dòng chứa ba số nguyên dương ~a, b, k~ với ~a < 10^{18}~, ~b < 10^{18}~, ~k < 10^{18}~.

Kết quả

In ra một số nguyên duy nhất là chữ số thứ ~k~ sau dấu chấm thập phân trong biểu diễn thập phân của ~\dfrac{a}{b}~.

Ví dụ

Ví dụ 1

Input

100 8 1

Output

5

Ví dụ 2

Input

17 3 10

Output

6

Ví dụ 3

Input

99 140 12

Output

2

Giải thích

Ví dụ 1

~\dfrac{100}{8} = 12.5000\dots~ nên chữ số thứ ~1~ sau dấu chấm thập phân là ~5~.

Ví dụ 2

~\dfrac{17}{3} = 5.6666\dots~ nên mọi chữ số sau dấu chấm đều là ~6~, do đó chữ số thứ ~10~ là ~6~.

Ví dụ 3

~\dfrac{99}{140} = 0.70714285714285\dots~ Dãy chữ số sau dấu chấm bắt đầu bằng ~707142857142\dots~, vì vậy chữ số thứ ~12~ là ~2~.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le a, b, k < 10^{18}~

Bạn được cho một đồ thị vô hướng gồm ~n~ đỉnh đánh số từ ~1~ đến ~n~ và ~m~ cạnh đánh số từ ~1~ đến ~m~. Cạnh thứ ~i~ nối hai đỉnh ~u_i~ và ~v_i~.

Khi xóa đi một đỉnh (đồng thời xóa tất cả các cạnh kề với nó), số thành phần liên thông của đồ thị có thể thay đổi.

Yêu cầu

Với mỗi đỉnh ~j~ ~(1 \le j \le n)~, hãy xác định số thành phần liên thông của đồ thị sau khi xóa đỉnh ~j~.

Dữ liệu

• Dòng đầu chứa hai số nguyên dương ~n, m~ ~(n \le 10^5,\ m \le 2 \cdot 10^5)~.
• ~m~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên dương ~u_i, v_i~ là hai đầu mút của cạnh ~i~.

Kết quả

Ghi ra ~n~ dòng. Dòng thứ ~j~ là số thành phần liên thông của đồ thị sau khi xóa đỉnh ~j~.

Ví dụ

Ví dụ 1

Input

4 3
1 2
2 3
2 4

Output

1
3
1
1

Giải thích

Ví dụ 1

Đồ thị là một ngôi sao với đỉnh trung tâm ~2~.

• Xóa đỉnh ~1~: các đỉnh còn lại ~2,3,4~ vẫn liên thông ⇒ có ~1~ thành phần.
• Xóa đỉnh ~2~: các đỉnh ~1,3,4~ bị tách rời hoàn toàn ⇒ có ~3~ thành phần.
• Xóa đỉnh ~3~ hoặc ~4~: phần còn lại vẫn liên thông ⇒ có ~1~ thành phần.

Ràng buộc và chấm điểm

Ràng buộc

• ~n \le 10^5~
• ~m \le 2 \cdot 10^5~

Trên một con đường thẳng có ~n~ cây cổ thụ được đánh số từ ~1~ đến ~n~ theo thứ tự từ đầu đến cuối đường. Cây thứ ~i~ có chiều cao ~h_i~.

Nhà vua muốn sau khi chặt bớt một số cây thì khi đi từ đầu đến cuối đường, dãy chiều cao các cây còn lại sẽ tăng dần nghiêm ngặt.

Mỗi ngày diễn ra như sau:

• Buổi sáng, nhà vua đi dọc con đường và đánh dấu tất cả cây ~i~ ~(i \ge 2)~ thỏa ~h_i \le h_{i-1}~, trong đó ~h_{i-1}~ là cây đứng liền trước cây ~i~ ở thời điểm đó.
• Buổi chiều cùng ngày, những người làm vườn chặt bỏ toàn bộ cây đã bị đánh dấu.
• Sang ngày tiếp theo, các cây còn lại khép lại thành một dãy mới theo đúng thứ tự ban đầu.

Yêu cầu

Hãy xác định số ngày mà những người làm vườn phải chặt cây, tức là số ngày cho đến khi dãy cây còn lại có chiều cao tăng dần nghiêm ngặt (không còn cây nào bị đánh dấu).

Dữ liệu

• Dòng ~1~ chứa số nguyên dương ~n~ ~(n \le 10^5)~.
• Dòng ~2~ chứa ~n~ số nguyên dương ~h_1, h_2, \dots, h_n~ ~(h_i \le 10^9)~.

Kết quả

In ra một số nguyên duy nhất là số ngày những người làm vườn phải làm việc.

Ví dụ

Ví dụ 1

Input

9
4 3 2 1 8 6 7 8 9

Output

3

Giải thích

Ví dụ 1

• Ngày ~1~: dãy ~4, 3, 2, 1, 8, 6, 7, 8, 9~ Các cây bị đánh dấu: ~3, 2, 1, 6~ ⇒ còn lại ~4, 8, 7, 8, 9~.
• Ngày ~2~: dãy ~4, 8, 7, 8, 9~ Cây bị đánh dấu: ~7~ ⇒ còn lại ~4, 8, 8, 9~.
• Ngày ~3~: dãy ~4, 8, 8, 9~ Cây bị đánh dấu: ~8~ (vì ~8 \le 8~) ⇒ còn lại ~4, 8, 9~.

Từ đây dãy ~4, 8, 9~ tăng dần nghiêm ngặt, nên đáp án là ~3~.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le n \le 10^5~
• ~1 \le h_i \le 10^9~

Cu Tí được phân công mua bút chì cho cả lớp nhân dịp đầu năm học mới. Cả lớp cần ít nhất ~n~ chiếc bút chì.

Trong cửa hàng, giá mua lẻ mỗi chiếc bút chì là ~p~. Tuy nhiên, cửa hàng có chương trình ưu đãi: cứ mỗi ~k~ chiếc bút chì Cu Tí mua thì được tặng thêm 1 chiếc bút chì nữa (bút tặng không phải trả tiền).

Yêu cầu

Hãy xác định số tiền tối thiểu Cu Tí cần mang theo để sau khi mua và nhận khuyến mãi, Cu Tí có thể mang về ít nhất ~n~ chiếc bút chì.

Dữ liệu

Một dòng chứa ba số nguyên dương ~n, k, p~ ~(n \le 10^9,\ k \le 10^9,\ p \le 10^9)~.

Kết quả

In ra một số nguyên duy nhất là số tiền tối thiểu cần mang theo.

Ví dụ

Ví dụ 1

Input

36 5 5

Output

150

Giải thích

Ví dụ 1

Nếu Cu Tí mua ~30~ chiếc thì được tặng thêm ~\left\lfloor 30/5 \right\rfloor = 6~ chiếc, tổng cộng nhận ~30 + 6 = 36~ chiếc, vừa đủ ~n~. Mua ~29~ chiếc chỉ được tặng ~5~ chiếc, tổng ~34~ là chưa đủ. Vì vậy số tiền tối thiểu là ~30 \cdot 5 = 150~.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le n, k, p \le 10^9~