Герої та Монстри

Існує $n$ героїв та $n$ монстрів. Герої та монстри пронумеровані цілими числами від $1$ до $n$. Сила $i$-го героя дорівнює $a_i$, а сила $i$-го монстра рівна $b_i$. Гарантується, що всі значення $a_1,a_2,\dots ,a_n,b_1,b_2,\dots ,b_n$ попарно різні.

Всього відбудеться $n$ боїв. У кожному бою візьме участь рівно один герой та рівно один монстр, при чому кожен герой та кожен монстр візьмуть участь рівно в одному бою. Нехай у бою беруть участь герой з номером $i$ та монстр з номером $j$. Якщо $a_i>b_j$, то герой з номером $i$ буде щасливим, а інакше він засмутиться.

Визначимо $an{s}_k$ — кількість таких різних множин героїв $S$ розміру $k$, що існує розподіл на бої, при якому будуть щасливими усі герої з $S$ та засмутяться усі інші герої.

Задано $q$ запитів виду $l$, $r$. Для кожного запиту знайдіть $(\sum _{i=l}^{r}an{s}_i)\mathrm{mod}998244353$.

Вхідні дані

У першому рядку задано одне ціле число $n$ ($1\le n\le 5\cdot 10^3$) — кількість боїв, що відбудуться.

У другому рядку задано $n$ цілих чисел $a_1,a_2,\dots ,a_n$ ($1\le a_i\le 2\cdot n$) — сили героїв.

У третьому рядку задано $n$ цілих чисел $b_1,b_2,\dots ,b_n$ $(1\le b_i\le 2\cdot n)$ — сили монстрів.

Гарантується, що всі значення $a_1,a_2,\dots ,a_n,b_1,b_2,\dots ,b_n$ попарно різні.

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

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

Гарантується, що всі значення $a_1,a_2,\dots ,a_n,b_1,b_2,\dots ,b_n$ попарно різні.

Вихідні дані

Для кожного запиту в окремому рядку виведіть одне ціле число — шукане значення $(\sum _{i=l}^{r}an{s}_i)\mathrm{mod}998244353$.

Приклади

Примітка

На малюнку нижче зображенні герої та монстри першого прикладу. Герої знаходяться зверху, а монстри — знизу. Число всередині квадрату позначає силу відповідного героя чи монстра.

У прикладі існує три можливих множини щасливих героїв: $\{1,2,3\}$, $\{2,3\}$ та $\{1,3\}$. Знизу зображенні три варіанти розподілу боїв, в яких будуть щасливими відповідні множини героїв. Зауважте, що може існувати декілька розподілів на бої, при яких буде щасливою та сама множина героїв.

Оцінювання

1. ($3$ бали): $a_i<b_j$ для $1\le i,j\le n$;

2. ($9$ балів): $q=1$, $l=1$, $r=1$;

3. ($6$ балів): $a_i=2\cdot i-1$, $b_i=2\cdot i$ для $1\le i\le n$;

4. ($16$ балів): $n\le 500$, $q=1$, $l=0$, $r=n$;

5. ($14$ балів): $q=1$, $l=0$, $r=n$;

6. ($15$ балів): $q=1$, $l=r$;

7. ($17$ балів): $n\le 500$;

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