Замовлення від викладача

Обмеження: 4 сек., 256 МіБ

До компанії Зеника й Марічки PLVIV звернувся із замовленням викладач університету.

Викладач задав студентам виконати роботу на тему «Обробка запитів знаходження лексикографічно найменшого суфікса-паліндрома для підрядків заданого рядка».

Робота полягає в розв’язанні такої задачі.

Задано рядок \(s\) довжини \(n\) з малих латинських букв.

Треба відповісти на \(q\) запитів. Кожен запит — це деякий підрядок \(s_{l..r}\). Для кожного запиту потрібно знайти лексикографічно найменший суфікс підрядка \(s_{l..r}\), який є паліндромом.

Рядок \(p\) довжини \(m\) є суфіксом рядка \(q\), якщо останні \(m\) символів рядка \(q\) збігаються з \(p\).

Лексикографічний порядок — це порядок слів у словнику.

Рядок \(p\) довжини \(m\) є паліндромом, якщо для всіх \(i\) (\(1 \le i \le m\)) \(i\)-ий символ спочатку та \(i\)-ий символ з кінця збігаються.

Викладачу потрібна програма, щоб перевіряти роботу його студентів.

Напишіть програму, яка розв’язує задачу.

Вхідні дані

У першому рядку задано ціле число \(n\) — довжину рядка.

У другому рядку задано \(s\).

У третьому рядку записано ціле число \(q\) — кількість запитів.

У наступних \(q\) рядках задано по два цілі числа \(l\), \(r\) — межі підрядка.

Вихідні дані

У \(q\) рядках виведіть відповіді на всі запити.

Обмеження

\(1 \le n \le 3 \cdot 10^5\),

\(s\) складається з малих латинських букв,

\(1 \le q \le 3 \cdot 10^5\),

\(1 \le l \le r \le n\) для кожного запиту.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
4 aabc 3 1 2 3 3 3 4	a b c

Примітки

• У підрядка aa є два суфікси: aa і a, і обидва є паліндромами. a є лексикографічно меншим за aa, бо йде в словнику раніше.

• У підрядка b є один суфікс b, який є паліндромом.

• У підрядка bc є два суфікси: bc і c. Тільки суфікс c є паліндромом.