A. Үсэгний шилжилт
хугацааны хязгаарлалт 1 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Танд жижиг Англи цагаан толгойн үсэгнээс бүтсэн $s$ хоосон бус тэмдэгт мөр өгөгдөнө. Та яг нэг ширхэг хоосон бус дэд тэмдэгт мөр сонгох бөгөөд үүний үсэгнүүдийн байрлалыг дараах байдлаар өөрчлөнө '$z$' '$y$'
'$x$'
'$b$'
'$a$'
'$z$'. Өөрөөр хэлвэл үсэг болгон дараагийн үсэгнийхээ байранд очих бөгөөд мөн $a$ нь $z$-ээр солигдох юм.
$s$ тэмдэгт мөрөөс энэ үйлдлийг яг нэг удаа хийн олдох боломжтой толь зүйн хамгийн богино тэмдэгт мөр юу вэ?
Оролт
Ганц мөрөнд жижиг Англи цагаан толгойн үсэгнээс бүтэх $s$ ($1 ≤ |s| ≤ 100 000$) тэмдэгт мөр өгөгдөнө.
Гаралт
$s$ тэмдэгт мөрөөс энэ үйлдлийг яг нэг удаа хийн олдох боломжтой толь зүйн хамгийн богино тэмдэгт мөрийг хэвлэнэ үү.
Орчуулсан: Энхлут
Жишээ тэстүүд
Оролт
codeforces
Гаралт
bncdenqbdr
Оролт
abacaba
Гаралт
aaacaba
Тэмдэглэл
Хэрвээ $1 ≤ i ≤ |s|$ байх $s_{1} = t_{1}, s_{2} = t_{2}, ..., s_{i - 1} = t_{i - 1}$, $s_{i} < t_{i}$ оршин байвал тэмдэгт мөр $s$ нь тэмдэгт мөр $t$-ээс богинохон.