Strategy to solve this problem

Let’s visualize the poles in a line. If two adjacent poles are more than distance \(H\) apart, one falling does not affect the other. Therefore, we can consider the problem independently for each “group” of adjacent poles that are within \(H\) distance from each other.

[The Japanese texts below mean the following. 互いに影響しない: do not affect each other, 独立に問題を考える: consider them individually]

Within each group, the problem simplifies to the following subproblem:

Subproblem There are \(m\) poles. The poles from left to right, numbered \(1, \dots, m\), fall during the \(p_1\)-th, \(\dots\), \(p_m\)-th earthquakes respectively. Adjacent poles may collide. Determine the probability that the last pole to fall is the \(1\)-st, \(\dots\), \(m\)-th pole, respectively. (Other settings are the same as the original problem / \(p_1, \dots, p_m\) are all distinct)

Let’s solve the problem using the following strategy:

1. Think of a way to solve the subproblem (Steps 1-4)
2. Think of a way to efficiently aggregate the results for individual groups (Step 5)

---

Step 1: Observing how poles fall

If we observe how the poles fall in the subproblem, then at any moment, the configuration looks like the following: a segment of poles that have fallen to the left, a segment of standing poles, and a segment of poles that have fallen to the right (the number of poles in these segments can be zero, as in the initial and final states).

This is because, regardless of whether a pole falls to the left or right from the state shown above, it results in a similar configuration as shown below.

---

Step 2: Consider the conditions

Many problems that involve counting cases or determining probabilities under certain conditions start by simplifying these conditions. Here, let’s consider the condition under which the last pole to fall in the subproblem is the \(i\)-th pole from the left.

Firstly, just before the \(p_i\)-th earthquake, the \(i\)-th pole from the left must still be standing. For this to happen, in the previous earthquakes:

• if poles to the left of the \(i\)-th fall, they must fall to the left;
• if poles to the right of the \(i\)-th fall, they must fall to the right.

This is because, from Step 1, if a pole to the left of the \(i\)-th falls to the right, it would cause a chain reaction making the \(i\)-th pole fall as well. The same applies if a pole to the right of the \(i\)-th falls to the left.

Conversely, if these two conditions are met, the \(i\)-th pole cannot fall.

[倒れるなら左/右に倒れる: fall to the left/right if they fall]

With this premise, when the \(i\)-th pole falls, it must result in all poles being down. The condition for this is as follows:

• If it falls to the left: It is sufficient if there is no pole standing to the right of the \(i\)-th, so \(p_i > p_{i+1}\) or \(i = m\) ensures all are down
• If it falls to the right: It is sufficient if there is no pole standing to the left of the \(i\)-th, so \(p_i > p_{i-1}\) or \(i = 1\) ensures all are down

---

Step 3: What is the probability?

3.1: Consider an example

First, let’s consider the following example and determine the probability that the last pole to fall is the red pole, based on the conditions from Step 2.

The blue poles must fall to the left if they fall, and the red pole must fall to the right if it falls. Under these conditions, simulating up to just before the \(64\)-th earthquake results in the following.

[\(i\) 回目の地震で倒れる: fall during the \(i\)-th earthquake]

All five events must result in the poles falling in the “correct direction” (respectively right, left, right, right, left). The probability of this happening is \(\left(\frac{1}{2}\right)^5 = \frac{1}{32}\). This is the probability that the red pole is still standing just before the \(64\)-th earthquake.

Now, the \(64\)-th earthquake occurs. Since \(64 > 33\), if the red pole falls to the left, all poles will be down. Since \(64 > 62\), if the red pole falls to the right, all poles will be down. Therefore, in this example, it doesn’t matter which way it falls. Thus, the probability that the last pole to fall is the red pole is \(\frac{1}{32}\).

3.2: Calculating the probability

Generalizing, the probability that the last pole to fall is the \(i\)-th pole from the left is given by \(\left(\frac{1}{2}\right)^a \times \frac{b}{2}\), where:

• \(a\) is the number of earthquakes in which poles actually fall when simulated up to just before the \(p_i\)-th earthquake, under the condition “poles to the left of the \(i\)-th fall to the left, poles to the right of the \(i\)-th fall to the right”
• \(b\) is the number of conditions “\(p_i > p_{i+1}\) or \(i = m\)” and “\(p_i > p_{i-1}\) or \(i = 0\)” that are satisfied

In the example from section 3.1, \(a = 5, b = 2\).

Here, the value of \(a\) can be determined without actual simulation.

• For an actual pole to fall during the \(p_j \ (j < i)\) earthquake, the condition is \(p_j < \min(p_{j+1}, \dots, p_i)\). This is because poles \(j+1, \dots, i-1\) must not fall first, and it must be before the \(p_i\)-th earthquake.
• In other words, the number of earthquakes in which poles to the left of the \(i\)-th fall is “the number of times \(p_j\) is updated to a new minimum when moving left from pole \(i\)”.
• Similarly, the number of earthquakes in which poles to the right of the \(i\)-th fall is “the number of times \(p_j\) is updated to a new minimum when moving right from pole \(i\)”.
• Adding these two values gives the value of \(a\).

---

Step 4: How to find the number of times the minimum is updated

From the results of Step 3, if the following problem can be solved in \(O(m)\) time, the subproblem can be solved in \(O(m)\) time.

Typical Problem Given an array \(a_1, \dots, a_n\) of length \(n\), for each \(i = 1, \dots, n\), find the number of times the minimum value is updated when moving left from \(a_i\) (i.e., the number of \(j \ (1 \leq j \leq i-1)\) such that \(a_j < \min(a_{j+1}, \dots, a_i)\)).

This is actually a typical problem of around 400-450 points level on AtCoder, which you probably have seen before. Anyway, here is the solution:

Solution to the Typical Problem

Manage the list of positions where the minimum value is updated using a stack $S$, and determine the answer in the order $i = 1, \dots, n$.

• For $i = 1, \dots, n$, do the following:
1. While stack $S$ is not empty and $a_{(\text{top element of } S)} \geq a_i$, continue removing the top element of $S$.
2. Add $a_i$ to the top of $S$.
3. The number of times the minimum value is updated when moving left from $a_i$ is $(\text{size of } S \text{ at this point}) - 1$.

The time complexity per loop iteration is not necessarily $O(1)$, but the total time complexity is $O(n)$. This is because the number of additions to $S$ is $n$, so the total number of removals is also at most $n$.

---

Step 5: Efficiently aggregating results for individual groups

Finally, let’s think about how to aggregate the results of the subproblem for individual groups to produce the answer to the original problem.

The condition for all poles to be down exactly at the \(t\)-th earthquake is:

1. In the group to which pole \(t\) belongs, the last pole to fall is pole \(t\)
2. For each other group, the following condition is satisfied:
   • The last pole to fall is one of the poles \(1, \dots, t-1\)

The probability of this happening is the product of the probabilities of satisfying conditions 1. / 2. for individual groups. This can be directly calculated using the results of the subproblem.

The problem is that calculating it in a naive way would take \(O(N^2)\) time to solve the original problem. This is because calculating the probability that the last pole to fall is one of the poles \(1, \dots, t-1\) requires adding up the probabilities for individual poles, and the overall probability requires multiplying the probabilities for individual groups. Here, by utilizing the fact that we are finding answers in the order \(t = 1, \dots, N\), we can avoid many additions.

Let the number of groups be \(K\), and let the group numbers to which poles \(1, \dots, N\) belong be \(g_1, \dots, g_N \ (1 \leq g_i \leq K)\).

• Let \(s_j\) be the probability that all poles in group \(j\) have fallen at the current point. Initially set \(s_1, \dots, s_K\) to \(0\).
• For \(i = 1, \dots, N\), do the following:
  1. Let \(x\) be the probability that the last pole to fall in the subproblem for group \(g_i\) is pole \(i\).
  2. Calculate \(s_1 \times \dots \times s_{g_i-1} \times x \times s_{g_i+1} \times \dots \times s_K\). This is the answer for \(t = i\).
  3. Add \(x\) to \(s_{g_i}\).

Now, we just need an efficient way to calculate the multiplication in 2.

Method 1: Use a Segment Tree

Using a segment tree, you can process two types of queries in $O(\log N)$ time complexity: "update a specified element of an array" and "calculate the product of elements in a specified range of the array". Thus, this problem can be solved in $O(N \log N)$ time.

Method 2: Manage the value of $s_1 \times \dots \times s_K$

Consider managing the value of $Z = s_1 \times \dots \times s_K$ in real-time. Then, the answer can be calculated with a simple formula $Z \times \frac{x}{s_{g_i}}$, and updating the value of $Z$ is also simple, as you just need to multiply $Z$ by $\frac{s_{g_i}+x}{s_{g_i}}$ when adding $x$ to $s_{g_i}$. Since the answer needs to be calculated modulo a prime $P = 998244353$, it can be processed in $O(\log P)$ time using the modular inverse.

However, there are cases where $s_{g_i} = 0$ or is a multiple of $998244353$, so it's not straightforward. One solution is to manage (modulo $998244353$) "the product of non-zero elements among $s_1, \dots, s_K$" and "the number of zeros among $s_1, \dots, s_K$", and calculate the correct $Z$ accordingly. Then, this problem can be solved in $O(N \log P)$ time.

---

Step 6: Notes on implementation

In the actual implementation, calculate everything using integers by either managing the probability multiplied by \(2^{(\text{number of poles in the group})}\) or using the modular inverse. The Sample Implementation uses the former method.

---

Sample Implementation

A sample implementation in C++ is at https://atcoder.jp/contests/arc177/submissions/53427881.

Here is how you can implement it in Python:

MOD = 998244353

# Segment Tree
class segment_tree:
    def __init__(self, n: int):
        self.size = 1 << (n-1).bit_length()
        self.v = [0] * (self.size*2)
    def add(self, pos: int, x: int):
        pos += self.size
        self.v[pos] = (self.v[pos] + x) % MOD
        while pos > 1:
            pos >>= 1
            self.v[pos] = self.v[pos * 2 + 0] * self.v[pos * 2 + 1] % MOD
    def query(self, l: int, r: int):
        l += self.size
        r += self.size
        res = 1
        while l != r:
            if l & 1:
                res = res * self.v[l] % MOD
                l += 1
            if r & 1:
                r -= 1
                res = res * self.v[r] % MOD
            l >>= 1
            r >>= 1
        return res

# Solve the problem for each group
def calc(n, p):
    level = [n-1] * n
    sl = list()
    for i in range(n):
        while sl and sl[-1] > p[i]:
            sl.pop()
        level[i] -= len(sl)
        sl.append(p[i])
    sr = list()
    for i in range(n-1, -1, -1):
        while sr and sr[-1] > p[i]:
            sr.pop()
        level[i] -= len(sr)
        sr.append(p[i])
    power2 = [0] * (n+1)
    power2[0] = 1
    for i in range(n):
        power2[i+1] = power2[i] * 2 % MOD
    res = [0] * n
    for i in range(n):
        c = int(i == n-1 or p[i] > p[i+1]) + int(i == 0 or p[i] > p[i-1])
        res[i] = power2[level[i]] * c % MOD
    return res

# Main function to solve the problem
def solve(n: int, h: int, x: list):
    # Decompose the problem into groups
    pillars = [(x[i], i) for i in range(n)]
    pillars.sort()
    p = [pillars[i][1] for i in range(n)]
    v = list()
    g = list()
    pre = 0
    m = 0
    for i in range(1, n+1):
        if i == n or pillars[i][0] - pillars[i-1][0] > h:
            v += calc(i-pre, p[pre:i])
            g += [m] * (i-pre)
            pre = i
            m += 1
    
    # Aggregate the answers for individual groups
    pinv = [-1] * n
    for i in range(n):
        pinv[p[i]] = i
    seg = segment_tree(m)
    res = [0]
    for i in pinv:
        seg.add(g[i], v[i])
        res.append(seg.query(0, m))
    ans = [(res[i+1]-res[i]) % MOD for i in range(n)]
    return ans

# Input and Output
n, h = map(int, input().split())
x = list(map(int, input().split()))
ans = solve(n, h, x)
print(*ans)