8986: Smoke

You are right, but “Smoke God” is a brand new open-world adventure game independently developed by Ding Zhenzhen. The game takes place in a fantasy world called “Litang”, where people chosen by the gods will be granted “electronic cigarettes” to guide the power of nicotine. You will play a mysterious character named “Furong Wang” and meet animal friends with different personalities and unique abilities during your free travels. Together, you will defeat powerful enemies, find lost family members, and gradually uncover the truth about “Litang”.

The harm of electronic cigarettes to the body is significant, and the damage to body depends on the level of addiction.

Let's assume that Ding Zhenzhen's current addiction level is $j$, and the damage to body is $x$. When she smokes $i$-th electronic cigarette:

• There is a probability of $p$ that the addiction level increases by one, and $x$ is multiplied by AjA_jAj.
• There is a probability of $1-p$ that the addiction level remains unchanged, and $x$ is multiplied by Bj+CiB_j+C_iBj+Ci.

However, you do not know Ding Zhenzhen's current addiction level and the current damage to her body. You only know that if her addiction level is $j$, the current damage to her body is DjD_jDj.

Assuming that the initial addiction level to Ding Zhenzhen's body is equally likely to be any integer from $1$ to $m$. Given $N$, what is the expected damage to her body after smoking n=1,2⋯,Nn=1,2\cdots,Nn=1,2⋯,N cigarettes?

The first line contains two integers, N,mN, mN,m and $p$ (1≤N,m≤105,0≤p<9982443531 \leq N,m \leq 10^5, 0\leq p < 9982443531≤N,m≤105,0≤p<998244353), representing the number of smoking, the maximum addiction level and the probability to increase the addiction level when smoking an electronic cigarette respectively.

The second line contains m+N−1m+N-1m+N−1 integers, where the $i$-th integer AiA_iAi (0≤Ai<9982443530 \leq A_i < 9982443530≤Ai<998244353) represents the damage coefficient when the addiction level increases from $i$ to $i+1$ after smoking an electronic cigarette.

The thrid line contains m+N−1m+N-1m+N−1 integers, where the $i$-th integer BiB_iBi (0≤Bi<9982443530 \leq B_i < 9982443530≤Bi<998244353) represents one of the damage coefficient when the addiction level remains at $i$ after smoking an electronic cigarette.

The fourth line contains $N$ integers, where the $i$-th integer CiC_iCi (0≤Ci<9982443530 \leq C_i < 9982443530≤Ci<998244353) represents one of the damage coefficient after smoking $i$-th electronic cigarette.

The fifth line contains $m$ integers, where the $i$-th integer DiD_iDi (0≤Di<9982443530 \leq D_i < 9982443530≤Di<998244353) represents the initial damage to her body if the initial addiction level was $i$.

Output $N$ integers for n=1,2,⋯,Nn=1,2,\cdots,Nn=1,2,⋯,N representing expected damage to her body after smoking $n$ cigarettes, module $998244353$.