Масив символів і майже паліндроми

Це інтерактивна задача.

Рядок вважається паліндромом, якщо він читається однаково з обох сторін. Формально, рядок $s$ довжини $n$ вважається паліндромом, якщо $s_i=s_{n-i+1}$ для $1\le i\le n$. Наприклад, рядки «gg», «ara», «abacaba», «rotator» є паліндромами, а рядки «array», «palindrome», «uoi» — ні.

Назвемо рядок майже паліндромом, якщо в ньому можна переставити символи так, щоб він став паліндромом. Наприклад, рядки «n», «ara», «arr», «array» є майже паліндромами, а рядки «palindrome», «uoi», «random» — ні.

Підрядком рядка вважається рядок, який може бути утворений за допомогою видалення деякої (можливо нульової) кількості елементів з його початку та кінця.

Визначимо $f(s)$ як максимальну довжину серед довжин підрядків $s$, які не є майже паліндромами, або $0$, якщо таких підрядків немає.

Задано рядок $s$ довжини $n$, що складається з маленьких літер латинського алфавіту. Також задано $q$ запитів виду $l_i$, $r_i$. Для кожного запиту знайдіть значення $f(s[l_i..r_i])$, де $s[l_i..r_i]$ позначає підрядок, що складається з символів $s_{l_i},s_{l_i+1},\dots ,s_{r_i}$.

Вхідні дані

У першому рядку задано одне ціле число $n$ ($1\le n\le 2\cdot 10^5$) — довжина рядка.

У другому рядку задано рядок $s$, що складається з $n$ маленьких літер латинського алфавіту.

У третьому рядку задано одне ціле число $q$ ($1\le q\le 2\cdot 10^5$) — кількість запитів.

У четвертому рядку задано два цілі числа $l_1,r_1$ ($1\le l_1\le r_1\le n$) — параметри першого запиту.

Параметри наступних запитів ви отримаєте від програми журі (див. розділ «Протокол взаємодії»).

Протокол взаємодії

Програма журі виводитиме у окремих рядках по два цілі числа $l_i$, $r_i$ ($1\le l_i\le r_i\le n$) — параметри чергового запиту, починаючи з другого.

Програма журі не виведе параметри чергового запиту, доки не прочитає відповідь вашої програми на попередній запит.

Подбайте про виклик методу flush після виводу кожного рядка. Для цього можна використовувати:

• fflush(stdout), cout << endl або cout.flush() в C++;

• System.out.flush() в Java;

• flush(output) в Pascal;

• sys.stdout.flush() в Python;

• дивіться документації для інших мов програмування.

Вихідні дані

Для $i$-го запиту в окремому рядку виведіть одне ціле число — шукане значення $f(s[l_i..r_i])$.

Приклади

8
aabaaaba
3
3 7
1 8
4 4

4
6
0

Примітка

У першому прикладі необхідно знайти відповіді на три запити:

1. $s[\mathrm{3..7}]=$«baaab», підрядком якого є рядок «aaab» довжини 4, який не є майже паліндромом;

2. $s[\mathrm{1..8}]=$«aabaaaba», підрядком якого є рядок «aabaaa» довжини 6, який не є майже паліндромом;

3. $s[\mathrm{4..4}]=$«a», усі підрядки якого є майже паліндромами.

Оцінювання

1. ($6$ балів): $q=1$, $l_1=1$, $r_1=n$, $n$ — парне, $s$ має вигляд «aabbaabbaa...»;

2. ($9$ балів): $q=1$, $l_1=1$, $r_1=n$, $n\le 200$;

3. ($5$ балів): $q=1$, $l_1=1$, $r_1=n$, $n\le 5000$;

4. ($8$ балів): $q=1$, $l_1=1$, $r_1=n$;

5. ($10$ балів): $s$ містить лише літери a та b;

6. ($8$ балів): $s_{l_i}\ne s_{r_i}$ для $1\le i\le q$;

7. ($7$ балів): $s_i\ne s_{i+1}$ для $1\le i<n$;

8. ($10$ балів): $s$ містить лише літери a, b, c, d, e та f;

9. ($18$ балів): $(r_i-l_i+1)$ — непарне для $1\le i\le q$;

10. ($19$ балів): без додаткових обмежень.