Xâu K-đẹp
Đề bài
Mô tả
Cho số nguyên . Một xâu gồm các chữ cái Latin in thường được gọi là đẹp nếu số lần xuất hiện của mỗi chữ cái trong xâu đều chia hết cho (chữ cái không xuất hiện có số lần là , cũng chia hết cho ).
Cho xâu độ dài gồm các chữ cái Latin in thường. Hãy tìm xâu đẹp độ dài nhỏ nhất theo thứ tự từ điển mà lớn hơn hoặc bằng theo thứ tự từ điển. Nếu không tồn tại xâu như vậy, in ra .
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên : số bộ dữ liệu.
- Mỗi bộ dữ liệu gồm hai dòng:
- Dòng thứ nhất chứa hai số nguyên và .
- Dòng thứ hai chứa xâu độ dài gồm các chữ cái Latin in thường.
Dữ liệu ra
Với mỗi bộ dữ liệu, in ra trên một dòng xâu đẹp nhỏ nhất theo thứ tự từ điển, có độ dài và lớn hơn hoặc bằng , hoặc nếu không tồn tại.
Ràng buộc
- Tổng trên tất cả các bộ dữ liệu không vượt quá
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 4 2 abcd 3 1 abc 4 3 aaaa 9 3 abaabaaaa |
acac abc -1 abaabaaab |
Bộ 1: trong acac, mỗi chữ a và c xuất hiện 2 lần. Bộ 2: với mọi xâu đều đẹp nên đáp án là chính . Bộ 3: không có xâu đẹp nào độ dài 4 với . Bộ 4: trong abaabaaab, a xuất hiện 6 lần, b xuất hiện 3 lần. |
| 4 4 2 abcd 3 2 cba 4 4 aaaa 9 5 abaabaaaa |
acac -1 aaaa -1 |
Bộ 2 và bộ 4: không chia hết cho nên không có xâu đẹp. Bộ 3: aaaa đã đẹp nên đáp án là chính nó. |
Bình luận