There are $n$ heroes and $n$ monsters. The heroes and monsters are numbered with integers from $1$ to $n$. The strength of the $i$-th hero is $a_i$, and the strength of the $i$-th monster is $b_i$. It is guaranteed that all values $a_1, a_2, \dots, a_n, b_1, b_2, \dots, b_n$ are pairwise distinct.

A total of $n$ battles will take place. In each battle, exactly one hero and exactly one monster will participate, such that every hero and every monster participates in exactly one battle. Suppose a hero with index $i$ and a monster with index $j$ participate in a battle. If $a_i > b_j$, then the hero with index $i$ will be happy, otherwise they will be sad.

Let $ans_k$ be the number of such distinct sets of heroes $S$ of size $k$ that there exists an assignment of battles where all heroes in $S$ are happy and all other heroes are sad.

Given $q$ queries of the form $l, r$. For each query, find $(\sum_{i=l}^{r} ans_i) \pmod{998244353}$.

Input

The first line contains one integer $n$ ($1 \le n \le 5 \cdot 10^3$) — the number of battles that will take place. The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 2 \cdot n$) — the strengths of the heroes. The third line contains $n$ integers $b_1, b_2, \dots, b_n$ ($1 \le b_i \le 2 \cdot n$) — the strengths of the monsters. It is guaranteed that all values $a_1, a_2, \dots, a_n, b_1, b_2, \dots, b_n$ are pairwise distinct. The fourth line contains one integer $q$ ($1 \le q \le n + 1$) — the number of queries. The next $q$ lines each contain two integers $l$ and $r$ ($0 \le l \le r \le n$) — the parameters of the corresponding query.

Output

For each query, output one integer on a separate line — the required value $(\sum_{i=l}^{r} ans_i) \pmod{998244353}$.

Subtasks

1. (3 points): $a_i < b_j$ for $1 \le i, j \le n$;
2. (9 points): $q = 1, l = 1, r = 1$;
3. (6 points): $a_i = 2 \cdot i - 1, b_i = 2 \cdot i$ for $1 \le i \le n$;
4. (16 points): $n \le 500, q = 1, l = 0, r = n$;
5. (14 points): $q = 1, l = 0, r = n$;
6. (15 points): $q = 1, l = r$;
7. (17 points): $n \le 500$;
8. (20 points): no additional constraints.

Examples

Input 1

3
3 4 6
1 2 5
3
1 2
2 3
3 3

Output 1

2
3
1

Note

The figure below shows the heroes and monsters of the first example. Heroes are at the top, and monsters are at the bottom. The number inside the square denotes the strength of the corresponding hero or monster.

In the example, there are three possible sets of happy heroes: $\{1, 2, 3\}$, $\{2, 3\}$, and $\{1, 3\}$. Below are three variants of battle assignments in which the corresponding sets of heroes will be happy. Note that there may exist multiple battle assignments for which the same set of heroes is happy.