Nguồn ảnh: Văn Việt, FPT

Theo truyền thuyết "Bánh chưng, bánh giầy", hoàng tử Lang Liêu đã dâng lên Vua Hùng hai thứ bánh làm từ gạo nếp: bánh chưng hình vuông tượng trưng cho Đất và bánh giầy hình tròn tượng trưng cho Trời. Từ đó, mỗi dịp Tết, người Việt làm bánh để tưởng nhớ tổ tiên và trân trọng hạt gạo, nghề nông.

Ngày nay, nhiều gia đình vẫn giữ thói quen gói bánh và thức xuyên đêm canh nồi bánh chưng: thêm củi để giữ lửa, canh nước để bánh luôn được luộc đều, và quây quần kể chuyện cho đỡ buồn ngủ.

Để chia ca canh nồi "cho khoa học", cả nhà ghi lại nhật ký đêm canh nồi dưới dạng một chuỗi ký tự ~S~. Mỗi ký tự là một hành động đã được mã hóa (ví dụ: thêm củi, châm nước, kiểm tra lửa, trở bánh, ...). Từ nhật ký này, mọi người muốn tìm ra "mẫu công việc" lặp lại nhiều lần nhất có thể, vì độ dài của mẫu đó thể hiện mức độ "ổn định" và dễ lập lịch cho năm sau.

Mỗi nhật ký được biểu diễn bằng chuỗi ký tự ~S~ gồm ~N~ ký tự ~S_1, S_2, ..., S_N~.

Bạn được cung cấp ba số nguyên ~N, K, T~ với ý nghĩa:

• ~N~ là độ dài của chuỗi ~S~.
• ~K~ là số lần xuất hiện tối thiểu yêu cầu.
• ~T~ quy định cách tính số lần xuất hiện của các chuỗi con.

Một chuỗi con liên tiếp (substring) ~S[l..r]~ được coi là "hợp lệ" nếu nó xuất hiện ít nhất ~K~ lần trong chuỗi ~S~, với quy tắc phụ thuộc vào giá trị ~T~:

• Nếu ~T = 1~, các lần xuất hiện được phép chồng lấn nhau.
• Nếu ~T = 2~, các lần xuất hiện không được phép chồng lấn nhau, tức là hai lần xuất hiện bất kỳ không được chia sẻ ký tự chung.

Yêu cầu: hãy tìm độ dài lớn nhất của một chuỗi con thỏa mãn điều kiện trên.

Input

• Dòng đầu tiên chứa ba số nguyên ~N~, ~K~ và ~T~ ~(1 \leq N \leq 300\ 000~, ~1 \leq K \leq N~, ~1 \leq T \leq 2)~
• Dòng thứ hai chứa chuỗi ký tự ~S~ gồm ~N~ ký tự, mỗi ký tự là chữ cái latin viết thường.

Output

• In ra một số nguyên duy nhất là độ dài lớn nhất của một chuỗi con thỏa mãn yêu cầu đề bài.

Scoring

Example input 1

8 3 1
abababab

Example output 1

4

Explanation

Với ~T = 1~, các lần xuất hiện được phép chồng lấn.

Chuỗi con ~abab~ có độ dài ~4~ và xuất hiện tại các vị trí:

• từ ~1~ đến ~4~
• từ ~3~ đến ~6~
• từ ~5~ đến ~8~

Tổng cộng có ~3~ lần xuất hiện, thỏa mãn yêu cầu ~K = 3~. Không tồn tại chuỗi con nào có độ dài lớn hơn ~4~ xuất hiện ít nhất ~3~ lần, nên kết quả là ~4~.