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

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 є паліндромом.