Танд жижиг Англи цагаан толгойн үсэгнээс бүтсэн $s$ хоосон бус тэмдэгт мөр өгөгдөнө. Та яг нэг ширхэг хоосон бус дэд тэмдэгт мөр сонгох бөгөөд үүний үсэгнүүдийн байрлалыг дараах байдлаар өөрчлөнө '$z$' '$y$' '$x$' '$b$' '$a$' '$z$'. Өөрөөр хэлвэл үсэг болгон дараагийн үсэгнийхээ байранд очих бөгөөд мөн $a$ нь $z$-ээр солигдох юм.

$s$ тэмдэгт мөрөөс энэ үйлдлийг яг нэг удаа хийн олдох боломжтой толь зүйн хамгийн богино тэмдэгт мөр юу вэ?

Оролт

Ганц мөрөнд жижиг Англи цагаан толгойн үсэгнээс бүтэх $s$ ($1 ≤ |s| ≤ 100 000$) тэмдэгт мөр өгөгдөнө.

Гаралт

$s$ тэмдэгт мөрөөс энэ үйлдлийг яг нэг удаа хийн олдох боломжтой толь зүйн хамгийн богино тэмдэгт мөрийг хэвлэнэ үү.

Хэрвээ $1 ≤ i ≤ |s|$ байх $s_{1} = t_{1}, s_{2} = t_{2}, ..., s_{i - 1} = t_{i - 1}$, $s_{i} < t_{i}$ оршин байвал тэмдэгт мөр $s$ нь тэмдэгт мөр $t$-ээс богинохон.