E. Алимхүү ба тоглоом

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

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

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

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

Алимхүү, Талххүү нар тоглоомонд дуртай. Ѳнѳѳдѳр тэд дараах дүрэмтэй тэмдэгт мѳрийн тоглоом тоглоно. Эхлээд Талххүү Алимхүүд зѳвхѳн 'A', 'B', 'C', 'D' үсгүүдээс бүрдэх $s$, $t$ хоёр тэмдэгт мѳрийг хэлнэ. Тэгээд Алимхүү аль болох хурдан $s$ тэмдэгт мѳрийг бүтээх ёстой. Анх түүнд хоосон тэмдэгт мѳр байх ба нэг секундэд одоо байгаа тэмдэгт мѳрнийхѳѳ ард $t$ тэмдэгт мѳрийн дараалсан дэд үсгүүдээс бүрдэх дэд тэмдэгт мѳрийг залгаж болно.

Одоо Талххүү Алимхүү нар тоглоомоо эхэлж байна. Талххүү $t$ тэмдэгт мѳрийг Алимхүүд хэлчихсэн боловч $s$ тэмдэгт мѳрийг хараахан хэлээгүй байна. Талххүү зѳвхѳн $s$ тэмдэгт мѳрийг $n$ үсгээс бүрдсэн байхаар сонгож хэлнэ гэж бодож байгаа. Мэдээж тэр Алимхүүд аль болох хамгийн муу (аль болох их хугацаа зарцуулдаг) байхаар сонгохыг хүснэ. Хамгийн муу тохиолдолд Алимхүү хэр хугацааг зарцуулахыг Талххүүд хэлнэ үү. Алимхүү ямар ч үед хамгийн сайнаар буюу боломжит хамгийн бага хугацааг $s$ тэмдэгт мѳрийг бүтээхэд зарцуулна гэж үз.

Оролт

Эхний мѳр $n$ ($1 ≤ n ≤ 10^{18}$) бүхэл тоог агуулна. Хоёрдугаар мѳр $t$ ($1 ≤ |t| ≤ 10^{5}$) тэмдэгт мѳрийг агуулна. $t$ тэмдэгт мѳр зѳвхѳн 'A', 'B', 'C', 'D' үсгүүдээс бүрднэ. Үсэг бүр ядаж нэг удаа орно.

Гаралт

Алимхүүд шаардагдаж болох боломжит хамгийн их хугацааг хэвлэ.

Орчуулсан: Sugardorj

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

Оролт
5
ABCCAD
Гаралт
5
Оролт
5
AAABACADBABBBCBDCACBCCCDDDBDCDD
Гаралт
4

Тэмдэглэл

Эхний жишээнд Талххүү $s$ тэмдэгт мѳрийг "AAAAA" гэж авч болно.

Хоёрдугаар жишээнд Талххүү $s$ тэмдэгт мѳрийг "DADDA$" гэж авч болно.

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