Expected Query Outputs on ToPTree

You are given an array a of n integers (indexed from 1 to n), initially all equal to 0. There are q operations defined on the array. Each operation is generated independently at random from the following two types with equal probability (each operation is chosen uniformly among all possible parameters):

• Type 1 (Addition): choose integers l, r, x satisfying \(1 \le l \le r \le n\) and \(1\le x\le N\); then for every index \(i\) with \(l\le i\le r\), do \(a_i \mathrel{+}= x\).
• Type 2 (Assignment): choose integers l, r, x satisfying the same conditions; then for every index \(i\) with \(l\le i\le r\), do \(a_i = x\).

Total number of different operations is \(n \cdot N \cdot (n+1)\) (because there are \(n(n+1)/2\) choices for \([l,r]\) and N choices for x, and two types with equal probability). However, the twist is that the array is stored in a so‐called ToothPaste Tree. In this structure, the operations are not executed immediately. Instead, they are stored in an operation sequence A in the order of generation. Only when you query the value of some array element, the tree executes all pending operations that affect that element (i.e. every operation whose interval \([l,r]\) contains the queried index) in the order they appear in A and then removes them permanently from A.

More precisely, suppose that you perform m queries in the order \(p_1, p_2, \dots, p_m\) (each query asks for the current value of \(a_{p_i}\)). When processing the query for index \(p_i\):

1. For every operation in \(A\) that affects index \(p_i\) (i.e. its interval \([l,r]\) satisfies \(l \le p_i \le r\)), execute them in the same order as in A and then remove them from A.
2. Output the current value of \(a_{p_i}\) after these operations.

Note that an operation may affect indices other than the one you are querying; however, it is executed only when one of its covered indices is queried for the first time. In other words, if an operation’s interval intersects multiple queried indices, it will be executed only at the moment of the first such query. Also note that because assignment operations overwrite previous values (and even previous additions), the final value of \(a_{p_i}\) is determined by all operations executed up to that query. (For example, if among the executed operations affecting \(a_{p_i}\) the last assignment set it to \(x\) and later some additions have been applied, then the final \(a_{p_i}\) equals \(x\) plus the sum of the additions performed after that assignment.)

Given the integers n, m, q, N and the query sequence \(p_1, p_2, \dots, p_m\), the tree will output m numbers (one per query). Since the operations are random, you are asked to compute the expected value of each output modulo \(998244353\>.

---

An Equivalent Formulation

For each query, the operations that are executed are exactly those operations whose randomly chosen interval \([l,r]\) contains the query index and do not contain any previously queried index. In fact, if we denote by S the set of indices queried in earlier queries, then the operations executed at query i are those for which the chosen interval \([l, r]\) satisfies:

[ l \le p_i \le r,\quad \text{and} \quad [l,r] \cap S = \emptyset. ]

It can be shown that the number of intervals satisfying this condition is \((p_i- L)\cdot (R-p_i)\), where

[ L = \max({0} \cup {p_j: j < i \text{ and } p_j < p_i}), \quad R = \min({n+1} \cup {p_j: j < i \text{ and } p_j > p_i}). ]

Since there are a total of \(T = \frac{n(n+1)}{2}\) intervals, the probability that a fixed operation is executed at query i (and affects \(a_{p_i}\)) is

[ t_i = \frac{(p_i-L)\cdot (R-p_i)}{T}. ]

Each operation (when executed) is of addition type with probability \(1/2\) and assignment type with probability \(1/2\); furthermore, the integer x is chosen uniformly from \(\{1,2,\dots, N\}\) (its expected value is \(\alpha=\frac{N+1}{2}\)). If we assume that the operations executed at query i are independent with respect to type and value – and that the total number of such operations follows a binomial distribution with parameters \(q\) and \(t_i\) (since every one of the \(q\) operations is allocated to some query) – one may show that the final expected value at query i can be written in closed‐form as:

[ E[a_{p_i}] = \alpha \cdot \left( \frac{q,t_i + 1}{2} + \frac{q,t_i}{4}\Bigl(1-\frac{t_i}{2}\Bigr)^{q-1} - \frac{1}{2}\Bigl(1-\frac{t_i}{2}\Bigr)^q \right) \quad (\bmod, 998244353). ]

Your task is to compute \(E[a_{p_i}]\) for each query \(i=1,2,\dots,m\).

inputFormat

The first line contains four integers n, m, q, and N (1 ≤ n, m, q, N ≤ 10⁵).
The second line contains m integers: p₁, p₂, …, p_m (1 ≤ p_i ≤ n), which represent the query indices in the order of queries.

outputFormat

Output a single line containing m integers, where the i-th integer is the expected value of the output for the query on index p_i, computed modulo 998244353.

sample

4 2 4 1
2 3

831870296 598946614