Trong một vương quốc kỳ diệu, các thành phố và con đường tạo thành một mạng lưới rộng lớn. Mỗi thành phố được đánh số từ ~1~ đến ~N~, được kết nối với nhau bằng ~M~ con đường hai chiều. Vương quốc này không chỉ nổi tiếng với cảnh quan tuyệt đẹp mà còn bởi sự phức tạp trong hệ thống giao thông.

Có ~N~ thành phố trong vương quốc, và giữa chúng tồn tại ~M~ con đường hai chiều. Mỗi con đường kết nối hai thành phố ~u~ và ~v~, khách lữ hành cần một khoảng thời gian nhất định (trọng số ~w~) để đi qua. Các con đường có thể có độ dài khác nhau, và không phải mọi cặp thành phố đều được nối trực tiếp.

Bạn là một nhà thám hiểm lừng danh, được giao nhiệm vụ trả lời ~Q~ câu hỏi từ những khách du hành khác. Mỗi câu hỏi đưa ra: "Đâu là con đường ngắn nhất từ thành phố ~x~ đến thành phố ~y~?"

Nhiệm vụ của bạn là xác định thời gian di chuyển ngắn nhất giữa hai thành phố bất kỳ. Nếu không tồn tại đường đi từ ~x~ đến ~y~, hãy báo rằng chuyến đi là không thể.

Input

• Dòng đầu tiên: ba số nguyên dương ~N, M, Q~.

  • ~N~: số thành phố ~(N \leq 500)~.
  • ~M~: số con đường ~(M \leq 10{,}000)~.
  • ~Q~: số lượng truy vấn ~(Q \leq 10{,}000)~.

• ~M~ dòng tiếp theo: mỗi dòng chứa ba số nguyên dương ~u, v, w~.

  • ~u, v~: hai thành phố được kết nối bởi một con đường ~(u, v \leq N)~
  • ~w~: thời gian di chuyển trên con đường này ~(w \leq 10^9)~
• ~Q~ dòng cuối: mỗi dòng chứa hai số nguyên ~x, y~ – biểu thị một truy vấn hỏi đường đi ngắn nhất từ thành phố ~x~ đến thành phố ~y~.

Output

• Với mỗi truy vấn, in ra một dòng chứa: Thời gian di chuyển ngắn nhất từ ~x~ đến ~y~, hoặc -1 nếu không tồn tại đường đi.

Sample Input

4 3 5
1 2 5
1 3 9
2 3 3
1 2
2 1
1 3
1 4
3 2

Sample Output

5
5
8
-1
3

Từ thuở sơ khai, khi thế giới còn chưa thành hình, Sự Thật và Dối Trá đã tồn tại như hai thực thể song sinh. Sự Thật luôn hiện ra trần trụi, thuần khiết và sáng tỏ, còn Dối Trá thì thích ẩn mình sau nhiều lớp hóa trang, phủ mờ trong sương khói. Ban đầu, cả hai sống hòa hợp. Sự Thật giữ cho thế giới trong suốt, còn Dối Trá tạo ra chỗ cho trí tưởng tượng. Nhưng dần dần, Dối Trá nhận ra rằng con người thường sợ hãi sự trần trụi của Sự Thật, trong khi lại dễ dàng chấp nhận những gì được bao bọc trong vẻ ngoài khéo léo.

Một ngày nọ, khi cả hai đang tắm trong hồ thiêng, Dối Trá bày ra một kế hoạch xảo quyệt. Khi xong, Dối Trá liền nhanh chóng khoác lấy chiếc áo choàng của Sự Thật – chiếc áo của sự sáng tỏ và chân thành – rồi bỏ chạy. Sự Thật tìm mãi không thấy áo của mình. Trước mắt ông chỉ còn lại tấm áo của Dối Trá – cầu kỳ và tinh vi, che giấu bản chất bên trong. Dù biết rằng mặc nó sẽ khiến mình dễ được chấp nhận hơn, Sự Thật vẫn kiên quyết từ chối. Ông thà trần trụi còn hơn sống dưới lớp vỏ giả dối.

Từ ngày đó, thế gian chỉ nhìn thấy một Dối Trá khoác áo Sự Thật, còn Sự Thật đích thực thì biến mất vào bóng tối. Hàng ngàn năm trôi qua. Dối Trá sống dưới lốt Sự Thật. Ban đầu, điều ấy thật huy hoàng – được mọi người tôn kính và tin tưởng. Nhưng theo thời gian, Dối Trá trở nên rỗng tuếch bên trong. Mỗi lời nói, mỗi hành động đều giả tạo. Hắn đau khổ, mang gánh nặng phải duy trì lớp vỏ bề ngoài vô tận. Trong khi đó, Sự Thật thực sự vẫn tồn tại ở đâu đó, kiên định với bản chất của mình, dù bị lãng quên.

Một chiều thu, khi lá vàng xào xạc trong gió, Dối Trá tìm đến nơi Sự Thật ẩn mình. Không còn kiêu hãnh, hắn thú nhận: "Ta đã mệt mỏi với cuộc sống lừa dối này. Ta muốn trả lại áo choàng cho ngươi, nhưng điều đó sẽ không đơn giản. Ngươi phải chứng minh rằng Sự Thật xứng đáng tồn tại trong thế giới này." Rồi Dối Trá đưa ra một thử thách: "Ta sẽ cho ngươi một dãy gồm ~N~ số nguyên – những mảnh vỡ của cuộc sống. Và một con số bí ẩn ~K~ – luật lệ của vũ trụ. Ngươi phải tìm xem có bao nhiêu dãy con liên tiếp trong dãy này có tổng chia hết cho ~K~."

Mỗi dãy con như thế, Dối Trá giải thích: "Là khoảnh khắc Sự Thật có thể tỏa sáng trong thế giới giả dối. Nếu ngươi tìm được con số ấy, ta sẽ trả lại áo choàng, và cả hai chúng ta có thể sống đúng với bản chất của mình."

Giờ đây, Sự Thật cần sự giúp đỡ của bạn. Hãy giải bài toán này để khôi phục sự cân bằng cho thế giới, để Sự Thật trở lại trong hình hài đích thực, và Dối Trá có thể sống chân thật, không còn ngụy trang.

Input

• Dòng ~1~: Hai số nguyên dương ~N~ và ~K~ ~(N, K \leq 10^6)~
• Dòng ~2~: ~N~ số nguyên, mỗi số có giá trị tuyệt đối không vượt quá ~10^9~ (các phần tử của dãy)

Output

• Một số nguyên duy nhất là đáp án mà Sự Thật cần.

Sample Input

5 13
3 1 2 7 4

Sample Output

2

Tại tỉnh Cà Mau – miền đất tận cùng phía Nam của Tổ quốc, nổi tiếng với những cánh đồng lúa bát ngát và rừng U Minh huyền thoại – hằng năm vào mùa thu hoạch sẽ diễn ra Hội chợ Nông nghiệp Cà Mau. Đây là một sự kiện thương mại quan trọng, thu hút người dân từ khắp nơi về tham dự.

Trên con đường dẫn vào trung tâm huyện U Minh, ban tổ chức dựng lên một dãy gồm ~M~ gian hàng liên tiếp, được đánh số từ ~1~ đến ~M~. Mỗi gian hàng trưng bày và bán các sản phẩm nông nghiệp địa phương. Do hạn chế về kinh phí, chỉ có ~N~ gian hàng được nông dân và hợp tác xã thuê sử dụng. Các gian hàng được thuê có chỉ số là ~x_1, x_2, ..., x_N~, và tất cả đều khác nhau.

Thời tiết Cà Mau thất thường – khi thì nắng gắt, khi lại mưa lớn. Để bảo vệ nông sản quý giá, ban tổ chức quyết định mua bạt che để phủ lên các gian hàng đã thuê. Mỗi tấm bạt sẽ che một đoạn liên tiếp các gian hàng từ vị trí ~L~ đến ~R~ (với ~L \leq R~). Kích thước (chiều rộng) của một tấm bạt là số gian hàng mà nó che phủ: ~W = R - L + 1~.

Bạt được sản xuất từ nhiều loại vật liệu và chất lượng khác nhau, nên giá cả cũng khác nhau. Đáng chú ý, tấm bạt lớn hơn chưa chắc đã có giá cao hơn. Bảng giá được cho dưới dạng một mảng ~c_1, c_2, ..., c_M~, trong đó ~c_W~ là chi phí mua một tấm bạt có kích thước ~W~.

Ban tổ chức muốn mua bạt sao cho:

• Mỗi gian hàng đã thuê đều được che bởi ít nhất một tấm bạt,
• Các tấm bạt có thể chồng lấn lên nhau ở một số gian hàng,
• Tổng chi phí là nhỏ nhất có thể.

Nhiệm vụ của bạn: Tính ra chi phí tối thiểu cần thiết!

Input

• Dòng đầu: hai số nguyên dương ~N~ và ~M~ ~(N \leq M )~.
• Dòng thứ hai: ~N~ số nguyên dương ~x_1, x_2, ..., x_N~ – chỉ số của các gian hàng được thuê.
• Dòng thứ ba: ~M~ số nguyên dương ~c_1, c_2, ..., c_M~ – trong đó ~c_i~ là giá của một tấm bạt kích thước ~i~.

Output

• Một số nguyên duy nhất: chi phí tối thiểu.

Sample Input

6 12
1 2 11 8 4 12
2 3 4 4 8 9 15 16 17 18 19 19

Sample Output

9

Constraints

• ~1 \leq N \leq 5000~
• ~N \leq M \leq 10^5~
• ~1 \leq c_i \leq 10^6~

Chào mừng bạn đến với bữa tiệc sinh nhật của Tăng! Hôm nay là một ngày đặc biệt – không chỉ vì Tăng lại thêm một tuổi mới, mà còn vì cậu ấy nhận được hai món quà vô cùng đặc biệt từ cha mẹ:

• Một chiếc bánh kem nhiều tầng hình chữ nhật, với lớp kem mềm mịn xen giữa các tầng,
• Một thanh sô-cô-la khổng lồ hình chữ nhật làm từ cacao thượng hạng.

Tăng đã mời rất nhiều bạn bè đến chung vui trong ngày trọng đại này. Mỗi vị khách đều mang theo những lời chúc chân thành và nụ cười rạng rỡ. Để mọi người đều có thể thưởng thức một phần từ hai món quà ấy, Tăng muốn cắt chúng thành nhiều miếng nhất có thể. Tuy nhiên, theo luật của bữa tiệc, cậu chỉ được phép thực hiện đúng ~N~ nhát cắt trên chiếc bánh, và đúng ~N~ nhát cắt trên thanh sô-cô-la.

Mỗi nhát cắt có thể là ngang, dọc, hoặc kết hợp (theo bất kỳ hướng nào), miễn sao giúp tạo ra nhiều miếng nhất. Tăng nhờ bạn xác định số miếng tối đa có thể có đối với cả chiếc bánh và thanh sô-cô-la, sau khi thực hiện đúng ~N~ nhát cắt cho mỗi loại.

Input

• Một dòng duy nhất chứa số nguyên dương ~N~ ~(1 \leq N \leq 10^6)~.

Output

• Dòng thứ nhất: số miếng bánh tối đa.
• Dòng thứ hai: số miếng sô-cô-la tối đa.

Sample Input

4

Sample Output

12
9

Note

Trong xử lý ảnh và phân tích dữ liệu ma trận, việc tìm các vùng đồng nhất trong một ma trận nhị phân là một bài toán cơ bản. Ở đây, ta xét một phiên bản cụ thể.

Bạn được cho một ma trận nhị phân kích thước ~M \times N~ (~M~ hàng và ~N~ cột). Mỗi ô chứa hoặc 0 hoặc 1. Một ma trận vuông con là một khối liên tiếp trong ma trận gốc, có dạng hình vuông (số hàng bằng số cột) và gồm các ô kề nhau.

Hãy đếm tổng số ma trận vuông con chỉ chứa toàn số 0 (tức là không có số 1 nào bên trong).

• Một ma trận vuông ~1\times1~ (một ô đơn lẻ) được tính là hợp lệ.
• Các ma trận vuông con có kích thước từ ~1\times1~ đến ~\min(M,N)\times\min(M,N)~.
• Hai ma trận vuông con được coi là khác nhau nếu vị trí góc trên bên trái khác nhau hoặc kích thước khác nhau.

Input

• Dòng đầu: hai số nguyên ~M~ và ~N~ ~(1 \leq M, N \leq 1000)~ – số hàng và số cột.
• ~M~ dòng tiếp theo: mỗi dòng gồm ~N~ số nguyên (0 hoặc 1) cách nhau bởi dấu cách — các hàng của ma trận.

Output

• Một số nguyên duy nhất: tổng số ma trận vuông con chỉ chứa toàn số 0.

Sample Input

2 3
0 0 0
0 0 1

Sample Output

6

Lớp Siêu Quậy – một tập thể đầy năng động và tinh thần sôi nổi – đang chuẩn bị cho chuyến tham quan. Giáo viên yêu cầu các học sinh phải được chia thành các nhóm, mỗi nhóm có đúng ~K~ thành viên. Việc chia nhóm dựa trên mối quan hệ bạn bè trong lớp.

Quan hệ bạn bè được mô tả như sau:

• Nếu ~A~ là bạn với ~B~, thì ~A~ và ~B~ có thể ở chung một nhóm.
• Tính chất bắc cầu được áp dụng: nếu ~A~ là bạn với ~B~ và ~B~ là bạn với ~C~, thì ~A~ và ~C~ được coi là có liên kết (có thể ở chung một nhóm).
• "Có thể ở chung" không có nghĩa bắt buộc phải ở chung; một tập hợp học sinh có liên kết vẫn có thể được chia thành nhiều nhóm nhỏ khác nhau.

Ghi chú đặc biệt cho lớp:

• Một số học sinh không có bạn; các em sẽ tự lập thành một nhóm riêng.
• Nhóm có ít hơn ~K~ thành viên vẫn được chấp nhận (vẫn là hợp lệ).
• Một nhóm được định nghĩa là tập hợp những học sinh có liên kết với nhau trong đồ thị tình bạn.

Sau khi học sinh tự tổ chức, giáo viên muốn biết tổng cộng có bao nhiêu nhóm đã được hình thành.

Input

• Dòng đầu: ba số nguyên dương ~N, M, K~ ~(N, M, K \leq 10^5)~

  • ~N~: số học sinh (đánh số từ ~1...N~)
  • ~M~: số quan hệ bạn bè
  • ~K~: số thành viên mong muốn cho mỗi nhóm
• ~M~ dòng tiếp theo: mỗi dòng gồm hai số nguyên ~A~ và ~B~, biểu thị ~A~ và ~B~ là bạn bè.

Output

• Một số nguyên: tổng số nhóm được hình thành.

Sample Input

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

Sample Output

3

Nam và Nữ là đôi bạn thời thơ ấu, tình cảm dần dần biến thành mối tình tuổi trẻ. Vào ngày sinh nhật của Nữ, Nam quyết định tỏ tình. Nữ đưa ra một thử thách:

Trên một màn hình TV khổng lồ có ~N~ số nguyên dương. Có hai chiếc máy đặc biệt:

• Máy ~1~: ngẫu nhiên xuất ra 0 hoặc 1.
• Máy ~2~: xuất ra một số nguyên dương bất kỳ.

Quy tắc tính điểm cho mỗi lượt:

• Nếu máy ~1~ xuất ra 0: đây là lượt của Nữ. Nữ nhận số điểm bằng với số lượng các số trên màn hình ≤ giá trị mà máy ~2~ đưa ra.
• Nếu máy ~1~ xuất ra 1: đây là lượt của Nam. Nam nhận số điểm bằng với số lượng các số trên màn hình ≤ giá trị mà máy ~2~ đưa ra.

Nhiệm vụ của bạn: Sau ~M~ lượt, hãy tính tổng số điểm của Nữ và Nam.

Input

• Dòng ~1~: Một số nguyên dương ~N~ – số lượng số trên màn hình ~(N \leq 10^6)~.
• Dòng ~2~: ~N~ số nguyên dương – các số hiển thị trên màn hình. Mỗi giá trị trên màn hình là số nguyên dương ~\leq 10^6~.
• Dòng ~3~: Một số nguyên dương ~M~ – số lượt chơi ~(M \leq 10^6)~.

• ~M~ dòng tiếp theo: mỗi dòng gồm hai số nguyên ~u~ và ~v~ trong đó:

  • ~u ∈ {0,1}~ là giá trị máy ~1~ xuất ra (xác định ai ghi điểm ở lượt này),
  • ~v~ là giá trị máy ~2~ xuất ra (ngưỡng so sánh) ~(v \leq 10^{15})~.

Output

• Dòng ~1~: tổng điểm của Nữ.
• Dòng ~2~: tổng điểm của Nam.

Sample Input

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

Sample Output

11
8

Truyền thuyết kể rằng có một vương quốc bí ẩn mang tên CNT, thiên đường dành cho những trí tuệ xuất chúng và những trái tim dũng cảm. Chỉ những ai thật sự tài năng mới có thể tìm được đường vào vùng đất này và trở thành công dân của nó. Tuấn Tú, một chàng trai trẻ khát khao khẳng định bản thân, đã vượt qua muôn vàn thử thách để đến được cổng thành CNT. Vừa đặt chân vào, anh đã chứng kiến một sự kiện trọng đại: lễ hội tuyển chọn nhân tài hằng năm. Đức vua thông minh và công minh đang tìm kiếm những người xuất sắc nhất để giao trọng trách.

Với sự tự tin của tuổi trẻ, Tuấn Tú tình nguyện tham gia ban giám khảo để giúp nhà vua xếp hạng các thí sinh một cách công bằng. Nhà vua đồng ý, và cuộc thi bắt đầu. Có ~N~ thí sinh tham dự. Mỗi người nộp một bài thi được chấm theo thang điểm ~100~ (một số nguyên không âm).

Quy tắc xếp hạng đặc biệt như sau:

• Thí sinh có điểm cao hơn sẽ được xếp hạng cao hơn.
• Nếu nhiều thí sinh có cùng điểm số, người nộp bài sớm hơn sẽ được xếp hạng cao hơn.
• Không có hai thí sinh nào có cùng hạng.

Nhiệm vụ của bạn: Hãy xuất ra thứ hạng của từng thí sinh theo đúng thứ tự nộp bài ban đầu.

Input

• Dòng đầu: một số nguyên dương ~N~ ~(N \leq 10^6)~ – số lượng thí sinh.
• Dòng thứ hai: ~N~ số nguyên không âm, mỗi số nằm trong khoảng từ ~0~ đến ~100~, biểu thị điểm số của các thí sinh theo thứ tự nộp bài.

Output

• In ra ~N~ số nguyên: thứ hạng của từng thí sinh, theo đúng thứ tự nộp bài.

Sample Input

6
1 3 4 6 3 10

Sample Output

6 4 3 2 5 1

Trong Vương quốc Toán học huyền bí, các hiền nhân đã khám phá ra một loại số đặc biệt mang năng lượng tích cực và may mắn – được gọi là Số May Mắn. Theo ghi chép cổ xưa, một số nguyên dương được coi là may mắn nếu trong dạng thập phân của nó xuất hiện ít nhất một dãy gồm ~K~ chữ số giống hệt nhau liên tiếp.

Truyền thuyết kể rằng từ thời xa xưa, các nhà toán học nhận thấy những con số có các chữ số lặp lại liên tiếp thường xuất hiện trong những sự kiện trọng đại, những phát minh quan trọng và những khoảnh khắc kỳ diệu của cuộc đời. Qua nhiều thế hệ nghiên cứu, họ đã chắt lọc nên định nghĩa về số may mắn mà ta sử dụng ngày nay.

Ví dụ, với ~K = 3~:

• Số 3555777 được coi là may mắn vì nó chứa các dãy "555" và "777".
• Số 123456789 không phải là may mắn với ~K = 3~ vì nó không có ba chữ số giống nhau liên tiếp.

Nhà Vua của Vương quốc Toán học đang tổ chức một cuộc thi tìm kiếm những nhà toán học vĩ đại nhất. Ngài giao cho bạn một nhiệm vụ đặc biệt:

Bạn được cho:

• Hai số nguyên dương ~N~ và ~K~ ~(N \le 10^5,; K \le 10^3)~
• Một danh sách gồm ~N~ số nguyên dương, mỗi số có thể dài tới ~1000~ chữ số.

Nhiệm vụ của bạn là kiểm tra từng số trong danh sách và xác định xem nó có phải là số may mắn theo tiêu chí đã cho hay không.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~N~ và ~K~, cách nhau bởi một dấu cách.
• Mỗi dòng trong số ~N~ dòng tiếp theo chứa một số nguyên dương.

Output

• Với mỗi số trong danh sách, in ra một dòng:

  • YES nếu số đó là may mắn
  • NO nếu số đó không phải may mắn

Sample Input

5 3
111222333
123456789
444555666
999999999
121212121

Sample Output

YES
NO
YES
YES
NO

Just read only two integer numbers ~a~ and ~b~ ~(a, b \leq 10^{18})~ and print only one sum of those two numbers. Don't read another one!

Main Input

9 
7

Main Output

16