C. Наибольшая из подстрок

Даны $q$ подстрок строки $s$, каждая задана парой $(l, r)$. Выведите номер лексикографически наибольшей из них. Если таких несколько, выведите наименьший номер.

Сравнение двух подстрок - то же, что в классной задаче: двоичным поиском находим длину общего префикса, дальше смотрим на первый различающийся символ, а если различий нет - на длины.

Дальше это просто поиск максимума: держим текущего лидера и сравниваем с ним каждую следующую подстроку. Всего $q$ сравнений по $O(\log n)$.

Тонкость с «наименьшим номером»: лидер меняется только при строго большей подстроке. Если сравнение вернуло «равны», лидер остаётся прежним.

Заведите сравнение отдельной функцией, возвращающей $-1$, $0$ или $1$, - иначе ветка равенства теряется почти наверняка.

В первой строке - строка $s$ ($1 \le \lvert s \rvert \le 10^5$) из строчных латинских букв.

Во второй - число $q$ ($1 \le q \le 10^5$).

В следующих $q$ строках - пары $l$, $r$ ($1 \le l \le r \le \lvert s \rvert$).

Одно число - номер лексикографически наибольшей подстроки.