P8057 D ToPTree

ToPTree stands for **To**oth**P**aste **Tree**. It works like squeezing toothpaste: it moves only when you squeeze it.

You have a sequence of $n$ numbers $[a_1\sim a_n]$. Initially, $a_i=0$. There is an operation sequence $A$ consisting of $q$ operations. The $i$-th operation is chosen uniformly at random from all $nN(n+1)$ possible operations: - With probability $\dfrac{1}{2}$, randomly choose one of the following two types of operations as this operation. - Randomly choose positive integers $l,r,x\ (1\le l\le r\le n,1\le x\le N)$, and add $x$ to every number in the interval $[l,r]$. - Randomly choose positive integers $l,r,x\ (1\le l\le r\le n,1\le x\le N)$, and set every number in the interval $[l,r]$ to $x$. - It is easy to see that there are $nN(n+1)$ possible operations each time. Since this tree is a ToothPaste Tree, it will execute only the operations related to your current query that have not been executed yet, and only when you query. Specifically, suppose you query the values of $a_{p_1\sim p_m}$ in order, then: - When querying $a_{p_i}$, execute all operations in $A$ that involve this number (i.e. whose interval $[l,r]$ contains $p_i$) in chronological order (i.e. in the order in $A$), and delete them from $A$. Then output the current value of $a_{p_i}$. > For example, $A$ currently contains the following four operations in order, and all elements in $a$ are currently $0$: > > 1. Add $1$ to interval $[2,3]$. > 2. Add $1$ to interval $[3,4]$. > 3. Assign interval $[2,4]$ to $1$. > 4. Add $1$ to interval $[2,3]$. > > Now query the value of $a_2$. Then operations $1,3,4$ will be executed in order, causing $a_1\sim a_4$ to become $[0,2,2,1]$. Therefore ToPTree outputs $2$. The operation sequence becomes: > > 1. Add $1$ to interval $[3,4]$. > > Query the value of $a_3$ next. Then operation $1$ will be executed, making the operation sequence empty, and $a_1\sim a_4$ becomes $[0,2,3,2]$, so the output is $3$. Note that this result is not the same as the result obtained by executing all operations $1\sim 4$ in order. Given $n,m,q,N$ and the sequence $p$, ToPTree will output $m$ values in the query order. Find the expected value of each of these $m$ outputs, modulo $998244353$. (Before the first query, no operations have been executed.)

The first line contains four positive integers $n,m,q,N$. The next line contains $m$ positive integers $p_1\sim p_m$.

Output one line with $m$ non-negative integers separated by spaces, as the answers modulo $998244353$.

**Constraints** **This problem uses bundled testdata.** For all testdata: $1\le n,N,q\le 9\times 10^8$, $1\le m\le 10^6$, $1\le p_i\le n$. The detailed constraints are as follows: - Subtask #1 (4 pts): $n,m,q,N\le 3$. - Subtask #2 (10 pts): $n,m,q,N\le 5$. - Subtask #3 (3 pts): $n=1$, $m,q\le 123456$. - Subtask #4 (3 pts): $q=1$, $m\le 123456$. - Subtask #5 (12 pts): $m=1$, $q\le 123456$. - Subtask #6 (27 pts): $n,m,q,N\le 50$. - Subtask #7 (9 pts): $m,q\le 5000$. - Subtask #8 (16 pts): $m,q\le 123456$. - Subtask #9 (16 pts): No additional constraints. Translated by ChatGPT 5