English Problem Statement

在智能电网的建设过程中，伏特需要做一些电学实验。作为电磁学高手，伏特设计了一个机器来研究电子的运动。

这个机器由 $n$ 个排成一行的舱室组成。每个舱室内部有磁场，可以看作有一个为 + 或 - 的状态。

电子的运动规律如下：

• 假设在某个舱室 $i$ 有一个电子。
• 如果电子所在舱室的状态是 -，就会向左移动到 $i-1$ 的舱室，否则会向右移动到 $i+1$ 的舱室。
• 在移动之后，电子原本所在的 $i$ 号舱室会翻转状态（从 - 变成 +，或从 + 变成 -）。
• 如果电子掉到外面（$0$ 或 $n+1$ 的位置），运动过程就结束了，否则会继续运动。

伏特提出了以下问题：

• 现在每个舱室的状态是 +/-/?。
• 在实验开始前，伏特会以 $\frac{1}{2}$ 的概率把每个 ? 的舱室设定为 +/- 的状态。
• 然后伏特以 $p_x$ 的概率在 $x$ 处放一个电子，让电子不断运动，直到掉到外面。
• 设最后电子掉到外面后，有恰好 $i$ 个舱室状态为 + 的概率是 $an{s}_i$。

你需要求出所有 $an{s}_i$，答案对 $998244353$ 取模。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数，表示 $p_1\sim p_n$。

第三行一个长度为 $n$ 的字符串 $s$，每个字符为 +/-/? 的其中之一，表示每个舱室的状态。

输出格式

输出 $n+1$ 个整数，表示 $an{s}_0\sim an{s}_n$。

样例一

input

3
499122177 748683265 748683265
+?-

output

748683265 873463809 748683265 623902721

样例解释 1

初始的 $p_i$ 分别为 $\frac{1}{2},\frac{1}{4},\frac{1}{4}$。

$an{s}_0\sim an{s}_n$ 分别为 $\frac{2}{8},\frac{1}{8},\frac{2}{8},\frac{3}{8}$。

以下是一种可能的运动过程：

• 初始电子处于 $1$ 位置，状态为 +--。
• 电子运动到 $2$ 位置，状态为 ---。
• 电子运动到 $1$ 位置，状态为 -+-。
• 电子运动到 $0$ 位置，状态为 ++-。此时运动结束。

样例二

input

5
499122177 748683265 873463809 935854081 935854081
?+-??

output

889061377 935854081 904658945 772079617 701890561 787677185

样例解释 2

初始的 $p_i$ 分别为 $\frac{1}{2},\frac{1}{4},\frac{1}{8},\frac{1}{16},\frac{1}{16}$。

样例三 ~ 十

见下发文件。

数据范围

对于所有数据，保证 $1\le n\le 5\times {10}^5$，$0\le p_i<998244353$，$(\sum p_i)mod998244353=1$。

时间限制：$\mathtt{\text{2s}}$

空间限制：$\mathtt{\text{2GB}}$