Өнгөт зураас гэдэг нь $k$ өнгөний аль нэгээр нь будагдсан нийт $n$ ширхэг дараалсан будагдсан нүд юм. Таны даалгавар бол аль ч хоёр хөрш нүдний өнгө ялгаатай байхаар хамгийн цөөн дахин будалт хийх юм. Та будалт хийхдээ $1$-c $k$-н хоорондох өнгийг ашиглаж болно.

Оролт

Эхний мөрөнд $n$, $k$ ($1 ≤ n ≤ 5·10^5$; $2 ≤ k ≤ 26$) тоо өгөгдөнө. Дараагийн мөрөнд нийт $n$ ширхэг латин цагаан толгойн том үсэг өгөгдөнө. Энд "A" үсэг эхний өнгийг, "B" үсэг дараагийн өнгийг гэх мэтээр өнгүүдийг илэрхийлнэ. Энд эхний $k$ үсэг л хэрэглэгдсэн байх юм. Үсэг бүр харгалзах нүднийхээ өнгийг илэрхийлнэ.

Гаралт

Эхний мөрөнд хамгийн цөөн дахин будалтын тоог, дараагийн мөрөнд ямар ч хамаагүй боломжит будалтыг хэвлэ.