Vì có nhiều xe đậu trên lề đường gây khó khăn cho người đi bộ nên chính quyền thành phố quyết định đặt thêm các cột phân cách để phân cách lề đường với lòng đường.
Lề đường được chia thành các đoạn có độ dài ~1~ mét. Ta có thể coi lề đường là một dãy kí tự chỉ gồm kí tự X
và dấu chấm .
, trong đó X
là nơi đặt cột phân cách và dấu chấm (.
) là nơi xe có thể đậu.
Tất cả xe trong thành phố đều có chiều dài ~L~ mét. Xe có thể đậu được trên lề đường nếu lề đường có ít nhất ~L~ mét liên tiếp nhau không bị đặt cột phân cách.
Ví dụ: Dãy kí tự ..X...X..
đại diện cho trạng thái của lề đường và với xe có chiều dài ~2~ mét thì có ~4~ vị trí khác nhau có thể đậu xe (bắt đầu tại vị trí thứ nhất, thứ tư, thứ năm và thứ tám).
Vì số lượng cột phân cách để đặt thêm có giới hạn, chỉ có ~N~ cột, nên chính quyền thành phố muốn đặt thêm các cột phân cách sao cho:
- Số lượng vị trí khác nhau có thể đậu xe là ít nhất.
- Nếu có nhiều cách đặt cột phân cách thỏa mãn điều kiện ~1~ thì chọn cách đặt sao cho số lượng cột phải sử dụng là ít nhất.
Yêu cầu:
Cho biết ~N~ cột phân cách có thể được dùng để đặt thêm, chiều dài của xe ~L~ và trạng thái ban đầu của lề đường, hãy tìm cách đặt các cột phân cách thỏa mãn hai điều kiện trên.
Dữ liệu vào:
- Dòng đầu tiên chứa hai số nguyên dương ~N~ và ~L~ ~(1 \leq N, L \leq 100)~, cách nhau ít nhất một dấu cách.
- Dòng thứ hai chứa một dãy kí tự thể hiện trạng thái ban đầu của lề đường. Trong đó mỗi kí tự đại diện một mét chiều dài,
X
đại diện một mét không thể đậu xe vì đã có sẵn một cột phân cách ở đó; dấu chấm (.
) đại diện một mét trống có thể đậu xe.
Dữ liệu ra:
Gồm một dãy kí tự thể hiện trạng thái của lề đường sau khi đặt thêm các cột phân cách.
Sample Input
3 4
.........
Sample Output
..X...X..
Bình luận