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\).
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\).
Note
In the first example, \(332748119\) is \(\frac{4}{3}\). In the third example, \(199648873\) is \(\frac{12}{5}\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2 1 2
1 2 1
|
2 332748119 1
|
|
2
|
4
5 5 5 5
0 0 0 0
|
5 5 5 5
|
|
3
|
5
1 9 3 7 5
2 4 6 8 5
|
6 4 3 199648873 2
|