题目背景

Eileen 是自走棋大师。作为全团现役的真 Gamer，她经常会直播这款游戏并和幸运观众一起对战。

现在，她正面临着一个经典的残局。精通游戏的她很快便算出了残局的最优解。但转念一想，Eileen 又停住了她正在操作棋子的手：虽然自己可以是一名技术主播，但是偶尔犯犯错，或许会有更好的节目效果呢？

题目描述

有 $n$ 位英雄和 $n$ 个怪物，第 $i$ 位英雄的能力是 $a_i$，第 $i$ 个怪物的实力是 $b_i$，保证 $a_i,b_i$ 两两不同且它们构成一个 $1\sim 2n$ 的排列。

现在，每位英雄将会挑选一个怪物与其对战。形式化地说，他们会选定一个排列 $p$，使得第 $i$ 位英雄对战第 $p_i$ 个怪物。英雄会赢得战斗当且仅当其能力高于怪物的能力。

在战斗之后，我们考虑所有获胜的英雄的编号集合 $S\subseteq \{1,2,\ldots,n\}$。$q$ 次给定整数 $l,r$，你需要求出存在多少集合 $S_i$，满足 $|S_i|\in [l,r]$，且存在一个排列 $p$ 满足在这种对战情况下获胜英雄的编号集合为 $S_i$。

由于答案过大，你只需要输出其对 $998244353$ 取模的结果。

输入格式

第一行输入一个整数 $n$。

第二行输入 $n$ 个整数 $a_i$。

第三行输入 $n$ 个整数 $b_i$。

第四行输入一个整数 $q$。

接下来 $q$ 行，每行输入两个整数 $l,r$。

输出格式

输出 $q$ 行，每行一个整数，代表答案。

样例 1 输入

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

样例 1 输出

2
3
1

样例 1 解释

可能的 $S$ 为 $\{1,2,3\}$，$\{2,3\}$ 和 $\{1,3\}$。

样例 2 输入

5
2 3 5 9 10
1 4 6 7 8
5
1 1
2 2
3 3
4 4
5 5

样例 2 输出

0
1
3
2
0

数据范围

本题共 8 个测试点，你需要通过一个测试点的全部测试数据才能获得该测试点的分数。

对于所有数据，$1\le n\le 5\times 10^3$，$1\le a_i,b_i\le 2n$，$1\le q\le n+1$，$0\le l\le r\le n$。