有 $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$ 的英雄会感到高兴，否则他会感到沮丧。

定义 $ans_k$ 为满足以下条件的英雄集合 $S$（大小为 $k$）的数量：存在一种战斗分配方案，使得集合 $S$ 中的所有英雄都感到高兴，而其他所有英雄都感到沮丧。

给定 $q$ 个查询，每个查询包含 $l$ 和 $r$。对于每个查询，求 $(\sum_{i=l}^{r} ans_i) \pmod{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$)，表示对应查询的参数。

输出格式

对于每个查询，在单独的一行中输出一个整数，即所求的 $(\sum_{i=l}^{r} ans_i) \pmod{998244353}$。

子任务

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 分): 无附加限制。

样例

输入 1

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

输出 1

2
3
1

说明

下图展示了第一个样例中的英雄和怪物。英雄位于上方，怪物位于下方。方框内的数字表示相应英雄或怪物的战力。

在样例中，存在三种可能的快乐英雄集合：$\{1, 2, 3\}, \{2, 3\}$ 和 $\{1, 3\}$。下方展示了三种战斗分配方案，在这些方案中，相应的英雄集合会感到高兴。请注意，对于同一个快乐英雄集合，可能存在多种战斗分配方案。