Trong một ngôi làng nhỏ có tên là Prime Ville, người dân nơi đây có truyền thống tôn vinh những con số nguyên tố. Hằng năm, vào ngày lễ hội lớn nhất làng, dân làng sẽ tổ chức một cuộc thi để tìm ra những con số nguyên tố đặc biệt. Người chiến thắng sẽ được nhận danh hiệu "Nhà Toán Học Tài Ba". Năm nay, bài toán mà trường làng đưa ra như sau: "Hãy tìm ra số nguyên tố nhỏ thứ ~K~ trong danh sách số nguyên tố tìm được từ ~N~ số nguyên mà ta đã chuẩn bị".

Yêu cầu

Em hãy viết chương trình để giúp dân làng tìm ra kết quả câu đố nhanh nhất.

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng đầu tiên ghi hai số nguyên ~N~ và ~K~ ~(1 \le N \le 10^5;\ 1 \le K < N)~.
• Dòng tiếp theo ghi ~N~ số nguyên ~A_i~ ~(0 < A_i \le 10^9)~.

Chú ý: Do đề không nói rõ, trong bộ test tôi đã giả định rằng các số đều khác nhau đôi một. Tôi cũng đã điều chỉnh bộ test phù hợp để có thể AC câu này trong thời gian xấp xỉ 1 giây. Tuy nhiên, nếu trong trường hợp tệ hơn, đặc biệt là khi ~K~ lớn và số nguyên tố xuất hiện dày đặc, việc sử dụng thuật toán có độ phức tạp là ~\mathcal{O}(N\sqrt{X})~ là chưa đủ tốt để đảm bảo thời gian chạy xấp xỉ 1 giây (nếu không dùng thuật toán Rabin-Miller)

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là số nguyên tố nhỏ thứ ~K~ tìm được, nếu không tìm được, in ra ~-1~.

Ràng buộc dữ liệu

• Có 50% số điểm tương ứng với 50% số test thỏa ~1 \le N \le 20;\ 0 < A_i \le 10^4~.
• Có 50% số điểm tương ứng với 50% số test thỏa ~N \le 10^5;\ 0 < A_i \le 10^9~.

Ví dụ

Ví dụ 1

INPUT

10 3
2 8 5 3 7 10 11 4 6 13

OUTPUT

5

Chiến tranh ác liệt, cha mẹ đều tham gia cách mạng và hy sinh, năm chị em ông Hứa Bồn (Đại Lộc, Quảng Nam) ly tán, riêng người em kế út mất liên lạc. Gần 50 năm, ông Bốn không ngừng tìm kiếm em gái với niềm tin bà vẫn còn sống. Bà Phùng Thị Năm (tên khác là Phùng Thị Thuỷ) lưu lạc từ nhỏ, sống lang thang, làm thuê, rồi được gia đình khác nhận nuôi sau đó lập gia đình và sinh sống tại Đại Lộc.

Tháng 4/2017, hai người tình cờ gặp nhau, Ông Bốn có linh cảm Bà Năm chính là người em gái thất lạc bấy lâu. Để xác minh, họ quyết định thực hiện xét nghiệm ADN dựa trên mức độ tương đồng giữa hai chuỗi ADN (theo thứ tự các cặp). Nếu mức độ giống nhau (tỉ lệ phần trăm giữa số cặp giống nhau trên tổng số cặp) trên ~50\%~ (sau khi làm tròn ~2~ chữ số phần thập phân), họ sẽ được xác nhận là anh em ruột.

Yêu cầu

Em hãy viết chương trình để giúp họ tìm ra tỷ lệ giống nhau giữa hai chuỗi ADN.

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng thứ nhất chứa chuỗi ADN của người thứ nhất;
• Dòng thứ hai chứa chuỗi ADN của người thứ hai.

Mỗi chuỗi ADN bao gồm các ký tự A, C, G, T được nối với nhau bằng dấu _ (gạch dưới). Ví dụ: A_C_G_T_A. Độ dài của chuỗi ADN được xác định nhỏ hơn ~10^6~ ký tự.

Dữ liệu đầu ra

Gồm hai dòng:

• Dòng đầu tiên ghi số tỷ lệ phần trăm (được làm tròn đến ~2~ chữ số phần thập phân) trùng khớp của hai chuỗi ADN;
• Dòng thứ hai nếu mức độ giống nhau giữa hai chuỗi ADN trên ~50\%~, in ra: OK ngược lại NO.

Ràng buộc dữ liệu

• Có 50% số điểm tương ứng với 50% số test có độ dài chuỗi ADN ~< 256~ kí tự;
• Có 50% số điểm tương ứng với 50% số test có độ dài chuỗi ADN ~\le 10^6~ kí tự.

Ví dụ

Ví dụ 1

INPUT

G_A_C_A_G_A_A_A_A_C_C_A_T_C_C_G_C_A_A_T_T_G_A_C_A_A_G_C_G_C_C_T_G_A_C
A_A_C_A_A_A_A_C_A_A_A_T_T_C_G_G_G_A_A_T_T_G_A_C_A_A_G_C_A_C_C_T_G_A_C

OUTPUT

74.29
OK

Tại thành phố ABC có ~T~ cơ quan để đảm nhận các nhiệm vụ quan trọng của thành phố. Hiện tại, mỗi cơ quan đang thực hiện một số công việc được giao. Tuy nhiên, do có sự chồng chéo trong việc phân công, một số công việc đang được nhiều cơ quan thực hiện đồng thời. Điều này dẫn đến lãng phí nguồn lực và giảm hiệu quả hoạt động. Để chuẩn bị phân công lại công việc, chính quyền thành phố đánh giá cơ quan có ít công việc hơn sẽ giải quyết nhanh hơn so với các cơ quan còn lại nên sẽ ưu tiên giữ lại các nhiệm vụ đã phân công cho cơ quan này. Chính quyền thành phố yêu cầu phân công lại công việc theo các quy tắc sau:

• Mỗi công việc chỉ được thực hiện bởi một cơ quan duy nhất, và số lượng công việc của các cơ quan sau khi phân công lại phải được cân bằng một cách tối ưu, ưu tiên giữ lại công việc cho cơ quan ban đầu được phân công ít công việc hơn. Nếu một cơ quan không còn công việc nào, cơ quan đó sẽ bị giải thể để tiết kiệm nguồn lực;
• Quy tắc chuyển công việc: Nếu một công việc ~X~ thuộc cả hai cơ quan A và B, thì công việc ~X~ sẽ được chuyển từ A sang B nếu:
  • Cơ quan B ban đầu được phân công ít công việc hơn A.
  • Nếu cả hai cơ quan có cùng số lượng công việc ban đầu, cơ quan B được phân công sớm hơn A (xuất hiện trước trong danh sách phân công).

Ban đầu, đề bài phát biểu các quy tắc chuyển công việc rất thiếu chặt chẽ: giả sử tồn tại hai cơ quan A và B có cùng số lượng công việc ban đầu và có một công việc ~X~ nằm trong danh sách công việc của cả A và B (~X~ không nằm trong danh sách công việc của cơ quan nào khác nữa) thì thử hỏi cuối cùng ~X~ sẽ được chuyển cho cơ quan nào??? Điều này khiến tôi phải thêm vào một quy tắc nữa: "Nếu cả hai cơ quan có cùng số lượng công việc ban đầu, cơ quan B được phân công sớm hơn A (xuất hiện trước trong danh sách phân công)" thì B sẽ nhận được công việc ~X~. Ví dụ 2 được tôi bổ sung vào để làm rõ ý này.

Yêu cầu

Em hãy viết chương trình để giúp chính quyền phân công lại các nhiệm vụ đã phân công cho các cơ quan.

Dữ liệu đầu vào

Gồm ~T + 2~ dòng:

• Dòng đầu ghi số nguyên dương ~T~ ~(1 \le T \le 10^5)~.
• Dòng thứ hai là dãy số ~N~ gồm ~T~ số nguyên tương ứng số công việc được phân công của lần lượt các cơ quan với ~N_i \le 100~.
• Dòng thứ ~i~ trong ~T~ dòng tiếp theo, mỗi dòng ghi dãy số nguyên dương ~X~ ~(1 \le X_j \le 100;\ 1 \le j \le 100)~ là các công việc của cơ quan ~i~.

Dữ liệu đầu ra

Gồm nhiều dòng:

• Dòng đầu ghi số cơ quan sau khi phân công lại.
• Các dòng tiếp theo: số đầu tiên ghi số thứ tự ban đầu của cơ quan, các số còn lại là các công việc của các cơ quan sẽ được phân công.

Lưu ý: Xuất theo số thứ tự cơ quan tăng dần, danh sách công việc được đánh số tăng dần.

Ràng buộc dữ liệu

• Có 20% số điểm tương ứng với 20% số test có ~T \le 5;\ N_{i} \le 10;\ X_{j} \le 50~.
• Có 30% số điểm tương ứng với 30% số test có ~T \le 10;\ N_{i} \le 50;\ X_{j} \le 100~.
• Có 50% số điểm tương ứng với 50% số test có ~T \le 10^5;\ N_{i} \le 100;\ X_{j} \le 100~.

Ví dụ

Ví dụ 1

INPUT

3
3 2 1
1 2 3
2 3
2

OUTPUT

3
1 1
2 3
3 2

Ví dụ 2

INPUT

3
3 2 2
3 1 2
2 4
4 3

OUTPUT

3
1 1
2 2 4
3 3

Để chuẩn bị tham gia kì thi chọn HSG giỏi sắp tới bạn An được giáo viên cho tham gia lớp ôn tập với ~N~ buổi học khác nhau để nâng cao năng lực lập trình. Mỗi buổi học bạn ấy có thể được tăng thêm hoặc bị giảm đi năng lực lập trình của mình (năng lực lập trình được thể hiện bằng điểm số trong buổi học, điểm này có thể dương hoặc âm). Dữ liệu dự kiến về năng lực lập trình của bạn An được thể hiện bằng một dãy số nguyên ~A~ gồm ~N~ phần tử. Để tránh quá mệt mỏi khi học tập, An chỉ có tham gia không quá ~K~ buổi học liên tục ~(1 \le K \le N)~ trong thời gian giáo viên của bạn ấy qui định.

Yêu cầu

Tìm ra khoảng thời gian tối ưu để nâng cao năng lực nhiều nhất trong giới hạn cho phép.

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng đầu tiên gồm hai số nguyên ~N, K~ với ~1 \le K \le N \le 10^6~.
• Dòng thứ hai chứa ~N~ số nguyên dương ~A_1, A_2, ..., A_N~ ~(|A_i| \le 10^6;\ 1 \le i \le N)~.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là kết quả cần tìm.

Ràng buộc dữ liệu

• Có 30% số điểm tương ứng với 30% số test có ~K = 1~ và ~N \le 10^6~.
• Có 30% số điểm tương ứng với 30% số test có ~K \le N \le 10^3~.
• Có 40% số điểm tương ứng với 40% số test có ~K \le N \le 10^6~.

Ví dụ

Ví dụ 1

INPUT

6 3
2 1 -3 4 5 -2

OUTPUT

9

Giải thích: Tổng ~4 + 5 = 9~ là lớn nhất của ~2~ số nguyên liên tiếp (không quá ~3~ phần tử).