D. Ом Ном ба хүзүүний зүүлт

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Нэгэн өдөр Ом Ном ялгаатай өнгийн $n$ ширхэг сувднуудын хэлхээс олжээ. Тэр энэ хэлхээстэй сувднаас эхний хэдийг нь хайчилж аваад өөрийн найз охин Ом Неллидэээ хүзүүний зүүлт хийж бэлэглэхээр шийджээ.

Ом Ном түүний найз охин гоёмсог хэв загварт дуртай гэдгийг мэднэ. Иймээс тэр хүүзүүний зүүлтний сувднуудыг нэгэн жигд хэв загвартай байлгахыг хүсчээ. Сувднуудын дараалал $S$ нь $S = A + B + A + B + A + ... + A + B + A$ маягаар харагдаж байвал $S$-г нэгэн жигд гэнэ. Энд $A$, $B$-ээр сувднуудын дарааллыг, "$ + $" тэмдгээр дарааллын хэлхээсийг илэрхийлж байгаа бөгөөд нийт $2k + 1$ нэмэгдэхүүн байгаагаас $k + 1$ нэмэгдэхүүн нь "$A$", $k$ нэмэгдэхүүн нь "$B$" байна. Хэрвээ $A$ эсвэл $B$ хоосон дараалал бол Ом Нелли тоохгүй.

Ом Ном нэгэн жигд хэв маягтай зүүлт хийхийн тулд олсон хэлхээнээсээ эхний хэдэн сувдыг таслах арга замуудыг тодорхойлоход нь Ом Номд тусал (хамгийн багадаа нэгийг, бүр бүгдийг нь ч байж болно). Ом Ном тасалсан сувднуудынхаа дарааллыг өөрчилж чадахгүй.

Оролт

Эхний мөрөнд $n$, $k$ ($1 ≤ n, k ≤ 1000000$) хоёр бүхэл тоо байна. $n$ бол Ом Номын олсон хэлхээний сувднуудын тоо, $k$ нь дээрх нэгэн жигд дарааллыг тодорхойлох тоо юм.

Хоёр дахь мөрөнд сувднуудын өнгийг илэрхийлсэн $n$ ширхэг Латин жижиг үсэгнүүдээс бүрдсэн дараалал байна. Нэг үсэг нэг өнгийг илэрхийлнэ.

Гаралт

$n$ ширхэг тэг эсвэл нэгийн тоо агуулсан тэмдэгт мөр хэвлэнэ. Хэрвээ хэлхээний эхний $i$ сувднууд нэгэн жигд дарааллыг бий болгодог бол $i$-р ($1 ≤ i ≤ n$) байрлалд нэгийн тоо байна. Эсрэг тохиолдолд тэг байна.

Орчуулсан: Даариймаа

Жишээ тэстүүд

Оролт
7 2
bcabcab
Гаралт
0000011
Оролт
21 2
ababaababaababaababaa
Гаралт
000110000111111000011

Тэмдэглэл

Эхний жишээнд эхний $6$ сувднуудын дараалал (бид $A$ = "", $B$ = "bca" гэж авбал), мөн эхний $7$ сувднуудын дараалал (бид $A$ = "b", $B$ = "ca" гэж авбал) хоёулаа нэгэн жигд дараалал мөн.

Хоёр дахь жишээнд бид $A$ = "aba", $B$ = "ba" гэж авбал эхний $13$ сувднуудын дараалал нэгэн жигд дараалал мөн.

Сэтгэгдлүүдийг ачааллаж байна...