Problem - 2038F - Codeforces

Suppose you are working in the Ministry of Digital Development of Berland, and your task is to monitor the industry of video blogging.

There are $n$ bloggers in Berland. Recently, due to the poor state of the main video platform in Berland, two alternative platforms were introduced. That's why bloggers started to reupload their videos to these alternative platforms. You've got the statistics that the $i$ -th blogger uploaded $v_i$ videos to the first alternative platform and $r_i$ videos to the second alternative platform.

You think that a potential user will be upset if even at least one of his favorite bloggers doesn't upload anything. However, if a blogger uploads videos to both platforms, the user will watch that blogger on the platform where more videos are available. So, you've come up with the following function to estimate user experience. Suppose a user watches $k$ bloggers $b_1, b_2, \dots, b_k$ ; then, let user experience be $E(b_1, \dots, b_k) = \max\left(\min_{i=1..k}{v[b_i]}, \min_{i=1..k}{r[b_i]}\right).$

In order to get some statistics, you want to calculate the value $\mathit{avg}_k$ that is equal to an average experience among all subsets of bloggers of size $k$ . Also, you have to calculate $\mathit{avg}_k$ for each $k$ from $1$ to $n$ .

Since answers may be too large, print them modulo $998\,244\,353$ .

Input

The first line contains a single integer $n$ ( $1 \le n \le 2 \cdot 10^5$ ) — the number of bloggers.

The second line contains $n$ integers $v_1, v_2, \dots, v_n$ ( $0 \le v_i \le 10^6$ ), where $v_i$ is the number of videos of the $i$ -th blogger on the first alternative platform.

The third line contains $n$ integers $r_1, r_2, \dots, r_n$ ( $0 \le r_i \le 10^6$ ), where $r_i$ is the number of videos of the $i$ -th blogger on the second alternative platform.

Output

Print $n$ integers $\mathit{avg}_1, \mathit{avg}_2, \dots, \mathit{avg}_n$ .

It can be proven that $\mathit{avg}_k$ may be represented as an irreducible fraction $\dfrac{x}{y}$ where $y \not\equiv 0 \pmod{998\,244\,353}$ . So, print $\mathit{avg}_k$ in a form $x \cdot y^{-1} \bmod 998\,244\,353$ .

Examples

Input

3
2 1 2
1 2 1

Output

2 332748119 1

Input

4
5 5 5 5
0 0 0 0

Output

5 5 5 5

Input

5
1 9 3 7 5
2 4 6 8 5

Output

6 4 3 199648873 2

Note

In the first example, $332748119$ is $\frac{4}{3}$ . In the third example, $199648873$ is $\frac{12}{5}$ .

2024-2025 ICPC, NERC, Southern and Volga Russian Regional Contest (Unrated, Online Mirror, ICPC Rules, Preferably Teams)
Finished

→ Virtual participation

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests. If you've seen these problems, a virtual contest is not for you - solve these problems in the archive. If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive. Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

→ Problem tags

combinatorics

data structures

fft

math

sortings

*2500

No tag edit access