题目背景

题目描述

将 $[1,n]$ 中的整数划分为 $m$ 个集合 $S_1,S_2,\cdots,S_m$，集合间按照其中的最小值 $\min\{S_i\}$ 从小到大排序，记数 $i$ 在第 $p_i$ 个集合中。

唐吉诃德定义整数数对 $(i,j)$ 是逆序对，如果：

• $i\in[1,n],j\in[1,m]$；
• $p_i<j\land i>\min\{S_j\}$。

称一个划分方案 $P=\{S_1,S_2,\cdots,S_m\}$ 的价值为 $q^{\text{inv}(P)}$，其中 $\text{inv}(P)$ 为该划分方案中的逆序对个数。

唐吉诃德给了你两个任务：

1. $n$ 固定时，对于 $[1,n]$ 中的每个整数 $m$，求所有划分方案的价值之和；
2. $m$ 固定时，对于 $[m,m+k-1]$ 中的每个整数 $n$，求所有划分方案的价值之和。

两问答案均对 $998244353$ 取模。

输入格式

一行四个正整数 $n,m,k,q$。

输出格式

第一行输出 $n$ 个整数，第 $i$ 个整数表示 $n$ 固定、$m=i$ 时的答案；
第二行输出 $k$ 个整数，第 $i$ 个整数表示 $m$ 固定、$n=m+i-1$ 时的答案。

两问答案均对 $998244353$ 取模。

8 4 8 1

1 127 966 1701 1050 266 28 1
1 10 65 350 1701 7770 34105 145750

8 4 8 0

1 7 21 35 35 21 7 1
1 4 10 20 35 56 84 120

8 4 8 2

1 1093 34041 122861 77527 9807 247 1
1 26 480 7870 122861 1876956 28393720 427584740

20 10 20 5

1 287921741 197538754 417997771 330974293 599777130 328477156 548671166 770352032 110248695 539485921 565871517 217002594 291371341 141328110 747637192 848546735 926168809 945690124 1
1 3051755 660508903 761237775 200310096 713887381 483477004 628232938 254386116 853526578 110248695 979696047 765825484 385364031 517701641 799832905 699031448 23144968 304263185 631524901

提示

对于所有数据，$1\le n,m,k\le10^6$，$0\le q<998244353$，保证若 $q\neq1$ 则 $\forall i\in[1,\max(n,m+k-1)],q^i\not\equiv1\pmod{998244353}$。

• 对于 $20\%$ 的数据，$n,m,k\le5\times10^3$；
• 对于另外 $20\%$ 的数据，$q=0$；
• 对于另外 $20\%$ 的数据，$q=1$。