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

Limits: 4 sec., 256 MiB

До компанії Зеника й Марічки 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\)-ий символ з кінця збігаються.

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

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

Input

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

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

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

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

Output

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

Constraints

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

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

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

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

Samples

Input (stdin) сopy	Output (stdout) сopy
4 aabc 3 1 2 3 3 3 4	a b c

Notes

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

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

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