Жила-була принцеса в чудовому королівстві. Королівство представляло собою пряму лінію на рівнинній землі, де стояли $N$ високих веж висотою $H$. Вежі були пронумеровані від 1 до $N$ в хронологічному порядку. Вежа $i$ $(1 \le i \le N)$ вертикально розташована на координаті $X_i$. Підстава кожної вежі міцно прикріплена до землі. Уявімо, що вежі дуже тонкі.

Принцеса планувала організувати свято, під час якого трапляться $N$ землетрусів. Під час $i$-го землетрусу $(1 \le i \le N)$ відбуватимуться наступні події:

1. Якщо вежа $i$ ще не впала, вона падає вліво або вправо на числовій прямій, кожен напрямок з ймовірністю $\frac{1}{2}$.
2. Якщо падаюча вежа стикається з іншою вежею, яка ще не впала (включаючи зіткнення з підставою вежі), остання вежа також падає в тому ж напрямку. Це може спричинити ланцюгову реакцію.
3. Напрямок падіння вежі під час кроку 1 не залежить від напрямку падіння інших веж.

Для забезпечення безпеки під час святкування принцесі було потрібно знайти для кожного $t=1,2,\ldots,N$ ймовірність того, що всі вежі впадуть рівно до $t$-го землетрусу. Помножити це на $2^N$ і вивести результат по модулю $998244353$. Можна довести, що значення, яке потрібно вивести, є цілим числом.

Input Specification

Перше рядок це два числа розділені пробілом де:

Перше число $N$ --- кількість веж $(1 \le N \le 2 \times 10^5)$.

Друге число $H$ --- висота кожної вежі $(1 \le H \le 10^9)$.

В наступному рядку йдуть $N$ чисел $X_1, X_2, \ldots, X_N$ --- координати розташування кожної вежі $(0 \le X_i \le 10^9, 1 \le i \le N)$. Всі координати різні.

Output Specification

У відповідь виведіть результат для кожної вежі розділені пробілами.

Sample Input 1

4 10
10 55 20 45

Sample Output 1

0 4 4 8

Sample Input 2

3 2
0 3 1

Sample Output 2

4 2 2