假设您在 Berland 数字发展部工作,您的任务是监控视频博客行业。
Berland 有 $$$n$$$ 博主。最近,由于Berland的主要视频平台状况不佳,推出了两个替代平台。这就是博主开始将他们的视频重新上传到这些替代平台的原因。您已获得统计数据,第 $$$i$$$ 个博主将 $$$v_i$$$ 视频上传到第一个替代平台,并将 $$$r_i$$$ 视频上传到第二个替代平台。
您认为,如果潜在用户至少有一位最喜欢的博主没有上传任何内容,他就会感到不安。但是,如果博主将视频上传到两个平台,用户将在有更多视频的平台上观看该博主。因此,您提出了以下函数来估计用户体验。假设用户观看 $$$k$$$ 博主 $$$b_1, b_2, \dots, b_k$$$;那么,让用户体验为 $$$$$$E(b_1, \dots, b_k) = \max\left(\min_{i=1..k}{v[b_i]}, \min_{i=1..k}{r[b_i]}\right).$$$$$$
为了获得一些统计数据,您需要计算值 $$$\mathit{avg}_k$$$,该值等于大小为 $$$k$$$ 的所有博主子集的平均体验。另外,您还必须计算从 $$$1$$$ 到 $$$n$$$ 的每个 $$$k$$$ 的 $$$\mathit{avg}_k$$$ 。
由于答案可能太大,请以 $$$998\,244\,353$$$ 为模打印它们。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 博主的数量。
第二行包含 $$$n$$$ 整数 $$$v_1, v_2, \dots, v_n$$$ ($$$0 \le v_i \le 10^6$$$),其中 $$$v_i$$$ 是第一个替代平台上第 $$$i$$$ 个博主的视频数量。
第三行包含 $$$n$$$ 整数 $$$r_1, r_2, \dots, r_n$$$ ($$$0 \le r_i \le 10^6$$$),其中 $$$r_i$$$ 是第二个替代平台上第 $$$i$$$ 个博主的视频数量。
输出
打印 $$$n$$$ 整数 $$$\mathit{avg}_1, \mathit{avg}_2, \dots, \mathit{avg}_n$$$。
可以证明 $$$\mathit{avg}_k$$$ 可以表示为不可约分数 $$$\dfrac{x}{y}$$$,其中 $$$y \not\equiv 0 \pmod{998\,244\,353}$$$。因此,以 $$$x \cdot y^{-1} \bmod 998\,244\,353$$$ 的形式打印 $$$\mathit{avg}_k$$$。
示例
输入 #1
3 2 1 2 1 2 1
输出 #1
2 332748119 1
输入 #2
4 5 5 5 5 0 0 0 0
输出 #2
5 5 5 5
输入 #3
5 1 9 3 7 5 2 4 6 8 5
输出 #3
6 4 3 199648873 2
注意
在第一个示例中,$$$332748119$$$ 是 $$$\frac{4}{3}$$$。在第三个示例中,$$$199648873$$$ 是 $$$\frac{12}{5}$$$。