tokitsukaze and Another Protoss and Zerg
时间限制:C/C++/Rust/Pascal 4秒,其他语言8秒
空间限制:C/C++/Rust/Pascal 512 M,其他语言1024 M
64bit IO Format: %lld

题目描述

还记得校赛的"Protoss and Zerg"吗?(https://ac.nowcoder.com/acm/contest/303/H)

这是另一个版本。

---------------以下为原题目描述(稍有修改)----------------

1v1,是星际争霸(StarCraft)中最常见的竞技模式。

tokitsukaze进行了n场1v1。在每一场的1v1中,她都有星灵(Protoss)和异虫(Zerg)两个种族可以选择,分别有a个单位和b个单位。因为tokitsukaze不太擅长玩人类(Terran),所以她肯定不会选择人类。

对于每一场1v1,玩家只能控制己方单位。也就是说,如果选择虫族,那么只能控制虫族单位,如果玩家选择星灵,那么只能控制星灵单位。

在n场1v1中,假设第i场,有ai个星灵单位,和bi个虫族单位。tokitsukaze可以在一场1v1中,任选一种种族进行游戏。如果选择了星灵,那么在这场游戏中,可以选择出兵1到ai个单位。那么同理,如果选择了虫族,那么在这场游戏中,可以选择出兵1到bi个单位。

假设所有星灵单位互不相同,所有异虫单位也互不相同,那么请问tokitsukaze打完这n场1v1,出兵的总方案数是多少。

注意:若两个方案,有其中一个单位不同,即视为不相同。

---------------以上为原题目描述(稍有修改)----------------

但是,tokitsukaze认为这个问题太简单了。

tokitsukaze想知道,恰好选择了0,1,2,3,...,\sum_{i=1}^{n}a[i]个星灵单位的方案数分别是多少。由于答案很大,所以输出答案mod 998244353 后的结果。

数据保证 \sum_{i=1}^{n}a[i] \leq 2\times 10^5

输入描述:

第一行包括一个正整数 n,(1≤n≤10^5)。
接下来一行有 n 个正整数 a[i],(1≤a[i]≤2*10^5)。
接下来一行有 n 个正整数 b[i],(1≤b[i]≤10^5)。
数据保证 \sum_{i=1}^{n}a[i] \leq 2\times 10^5

输出描述:

输出一行,\sum_{i=1}^{n}a[i] +1个整数,用空格隔开,行末无多余的空格。
示例1

输入

复制
2
1 2
2 1

输出

复制
3 7 5 1
示例2

输入

复制
1
1
1

输出

复制
1 1