跳蚤国计算机协会 UOI 主席“王中王”认为 UOI 比赛普及程度过低。

比如蚂蚁国的比赛，选手只需要瞎编能力强就可以通过，但 UOI 决赛就需要训练三十二项能力才能获取资格。

但是 UOI 比赛系列委员会全体反对，教学大纲并没有被删减，因此“王中王”决定调整一些知识点顺序以减轻学生负担。

大纲上有 $n$ 个知识点，最初第 $i$ 个知识点的难度排名为第 $p_i$ 难的。“王中王”的终极目标是让大纲排成从最难到最简单的顺序。

为了避免被怀疑，“王中王”只能制定一份规章，并且每年都按照这份规章来调整大纲。规章 $R$ 包含 $k$ 道依次执行的程序，其中每道程序是 $U,D$ 之一，对大纲顺序的调整效果如以下代码所示：

void U(int p[], int n){ // p[1...n]
  for(int i=1; i<n; i++)
    if(p[i]>p[i+1])
      swap(p[i], p[i+1]);
}
void D(int p[], int n){ // p[1...n]
for(int i=n-1; i>=1; i--)
if(p[i]>p[i+1])
swap(p[i], p[i+1]);
}

</p>

现在其它委员已经确定了规章中的一部分程序，“王中王”可以决定剩余每个位置的程序是 $U,D$ 中的哪个。王中王希望越早排完顺序越好，所以他希望你求出他所有可能得到的规章中，排好序需要的最小年数为 $0,1,\dots ,n-1$ 的分别有多少种。每个结果分别对 $998244353$ 取模。

输入格式

第一行两个整数 $n,k$。

第二行一个长度为 $k$ 的，只包含 UD? 的字符串 $R$。依次表示规章的每一道程序，其中 ? 是“王中王”可以自由选择为 $U,D$ 之一的程序。

第三行 $n$ 个整数，第 $i$ 个整数为 $p_i$。表示最初的大纲知识点难度顺序。

输出格式

共一行，$n$ 个整数，分别表示给大纲排好序最小所需年数分别为 $0,1,\dots ,n-1$ 的方案数对 $998244353$ 取模的结果。相邻两个整数之间用一个空格隔开。

7 3
?DU
2 4 5 6 3 1 7

0 1 1 0 0 0 0

当规章为 UDU 时：

零年（所有操作开始前）还未排好序。

第一年知识点的难度排名变化如下： $$ [2,4,5,6,3,1,7]\xrightarrow{U} [2,4,5,3,1,6,7]\xrightarrow{D}[1,2,4,5,3,6,7]\xrightarrow{U}[1,2,4,3,5,6,7]$$

第二年知识点的难度排名变化如下：

$$ [1,2,4,3,5,6,7]\xrightarrow{U} [1,2,3,4,5,6,7]\xrightarrow{D} [1,2,3,4,5,6,7]\xrightarrow{U} [1,2,3,4,5,6,7]$$

因此需要 2 年才能完成排序。

当规章为 DDU 时：

零年（所有操作开始前）还未排好序。

第一年知识点的难度排名变化如下：

$$ [2,4,5,6,3,1,7]\xrightarrow{D} [1,2,4,5,6,3,7]\xrightarrow{D}[1,2,3,4,5,6,7]\xrightarrow{U} [1,2,3,4,5,6,7]$$

因此只需 1 年就能完成排序。

20 4
?D??
18 6 14 11 2 19 3 7 10 20 9 12 13 15 16 17 1 5 8 4

0 0 0 6 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0

样例三 $\sim$ 八

见“附件下载”。

限制与约定

对于所有数据，保证 $1\le n\le 10^5$，$1\le k\le 1000$，$R$ 的长度为 $k$ 且只包含 UD? 三种字符，$1\le p_i\le n$ 且 $p$ 是一个排列。

时间限制：$3\texttt{s}$

空间限制：$512\texttt{MB}$