题目描述 2s 512MB

注意：本题保证数据随机生成，生成策略在数据范围处。

小明看完田忌赛马的故事以后，觉得田忌赛马很有趣，于是臆想了田忌赛马2。

齐王和田忌各有$n$匹马，田忌第$i$匹马的能力是$a_i$，齐王第$i$匹马的能力是$b_i$。在初始时候，两人各自的马已经按照能力从小到大排好序了，也就是$a_i\leq a_{i+1}$，$b_i\leq b_{i+1}$。由于齐王是君王，所以对于两人的第$i$匹马来说，总是满足$a_i\leq b_i$。

齐王经过第一次田忌赛马以后，很生气，要求在赛马的时候，两个人每次都派出自己最差的马去比赛，直到两人没马为止。

那这田忌不是稳输吗？不，田忌不想坐以待毙，他从遥远的西域国度采购了一种名为星粉剂的神秘药物，每次给一匹马服用，可以使得一匹马的能力$+1$。

齐王自然发现了田忌的神秘药物，因此齐王也提出了一个要求：田忌可以给自己的马服用星粉剂，但是服用之后，需要对自己参赛的马重新按能力排序，然后再进行比赛。

田忌知道自己的星粉剂是无限的，但田忌不敢赢掉齐王，只想让所有比赛都以平局收场。

请帮助田忌算一算，他喂自己的马吃星粉剂有多少种不同的方案吧。由于田忌天生喜欢plan b，所以田忌会多次询问你区间$[l,r]$的答案。

例如：齐王的三匹马能力分别是[3,3,4]，田忌的三匹马能力分别是[1,1,3]，田忌可以把自己的马喂成[3,3,4],[3,4,3],[4,3,3]，来使得每一局都是平局。

顺便给一个形式化题面：

你有两个长度为$n$的正整数单调不递降序列$a,b$。保证$a_i\leq b_i$。你可以生成一个数组$c$满足$c_i\geq a_i$，且$c$数组排序后与$b$相同，问$c$数组的方案数。

多次询问，每次问$a_{[l_i,r_i]}$与$b_{[l_i,r_i]}$对应数组的答案。

输入格式

第一行输入$n$。

接下来一行输入$a_i$。

接下来一行输入$b_i$。

接下来输入$Q$。

接下来$Q$行，每行输入$l_i,r_i$。

输出格式

输出$Q$行，每行输出答案$\mod 998244353$。

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

60
15
3
10
10

大样例

数据范围

注意：本题保证数据随机生成。

生成策略是：先手动指定$a$的最大值，随机生成$a$数组，然后$b_i=a_i+random(0,k),k\leq 10$，之后对$b$数组排序。

对于15%的数据：$n\leq 10,Q\leq 10$。

对于30%的数据：$n,Q\leq 1000$。

对于45%的数据：$n\leq 10^5,a_i,b_i\leq 1000$。

对于另15%的数据：$l_i=1$。

对于另15%的数据：$r_i=n$。

对于100%的数据：$n,Q\leq 2\times 10^5,1\leq a_i,b_i\leq n,1\leq l_i<r_i\leq n,a_i\leq b_i$。