D. Тэмдэгт мөр хувиргах

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

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

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

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

$n$ урттай $s$ гэсэн тэмдэгт мөр байна гэж үзье. Энд агуулагдах тэмдэгтүүд нь $0$-ээс $n - 1$ хүртэл дугаарлагдах ба $i$ болон $j$ нь $0 ≤ i < j < n$ гэсэн бүхэл тоонууд юм. Энэ функцыг дараах байдлаар тодорхойлцгооё.

$f(s, i, j) = s[i + 1... j - 1] + r(s[j... n - 1]) + r(s[0... i])$.

Энд $s[p... q]$ нь $s$-ы дэд тэмдэгт мөр ба энэ нь $p$ байрлалаас эхэлж $q$ байрлалд төгсөнө. "+" нь тэмдэгт мөрний тасралгүй холбогч ба $r(x)$ тэмдэгт мөр нь $r(x)$ тэмдэгт мөрний тэмдэгтүүдийг урвуу байрлалаар бичигдсэн байдал юм. Хэрэв $j = i + 1$ бол дэд тэмдэгт мөр $s[i + 1... j - 1]$ нь хоосон гэж тооцогдно.

Танд $a$ болон $b$ гэсэн тэмдэгт мөр өгөгдсөн байна. $i$ болон $j$-ы $f(a, i, j) = b$ гэсэн утгыг ол. $i$ тоо нь хамгийн их утга байх боломжтой. $i$-ы хувьд $j$-ы хэд хэдэн үндэслэлтэй утга байвал хамгийн бага утгыг $j$-г сонго.

Оролт

Эхний хоёр нь $a$ болон $b$ гэсэн хоосон биш тэмдэгт мөр агуулна. Тэмдэгт мөр тус бүрийн урт $10^{6}$-ээс хэтрэхгүй байна. Тус тэмдэгт мөр нь ASCII кодын 32-оос 126 хоорондох ямар ч тэмдэгтүүд агуулж болно.

Гаралт

Бодлогын хариу болох $i$, $j$ гэсэн хоёр бүхэл тоо хэвлэнэ үү. Хэрэв зөв хариу байхгүй бол $-1$ гэж хэвлэ.

Орчуулсан: Энхгэрэл

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

Оролт
Die Polizei untersucht eine Straftat im IT-Bereich.
untersucht eine Straftat.hciereB-TI mi  ieziloP eiD
Гаралт
11 36
Оролт
cbaaaa
aaaabc
Гаралт
4 5
Оролт
123342
3324212
Гаралт
-1 -1
Сэтгэгдлүүдийг ачааллаж байна...