给定长度为 $n$ 的字符串 $s$ 和系数序列 $f_1, f_2, \dots, f_n$。

定义一个正整数 $d$ 是一个子串 $s[l,r]$ ($1 \le l \le r \le n$) 的周期，当且仅当 $d \le r-l+1$ 且对于任意 $l \le i \le r-d$，均有 $s_i = s_{i+d}$。

定义一个正整数 $d$ 是一个子串 $s[l,r]$ ($1 \le l \le r \le n$) 的整周期，当且仅当 $d$ 是 $s[l \dots r]$ 的周期，且 $d$ 整除 $r-l+1$。

对于 $1 \le l \le r \le n$，定义子串 $s[l,r]$ 的价值为 $w(l,r) = f_{(r-l+1)/d}$，其中 $d$ 是子串 $s[l,r]$ 的最小整周期。

对于所有 $1 \le i \le n$，求所有以 $i$ 为右端点的子串的价值之和，即 $\sum_{j=1}^{i} w(j,i)$。由于答案可能较大，你只需要求出答案对 $998,244,353$ 取模后的结果。

输入格式

从标准输入读入数据。

输入的第一行包含一个正整数 $n$，表示字符串 $s$ 的长度。

输入的第二行包含一个长度为 $n$ 的字符串 $s$。

输入的第三行包含 $n$ 个非负整数 $f_1, f_2, \dots, f_n$，表示给定的系数序列。

输出格式

输出到标准输出。

输出一行 $n$ 个非负整数，其中第 $i$ ($1 \le i \le n$) 个非负整数表示所有以 $i$ 为右端点的子串的价值之和对 $998,244,353$ 取模后的结果。

8
babaaabb
0 1 1 0 0 0 0 0

0 0 0 1 1 2 0 1

以下为所有价值非 $0$ 的子串：

• 子串 $s[1,4] = \text{baba}$ 的最小整周期为 $2$，价值为 $1$。
• 子串 $s[4,5] = \text{aa}$ 的最小整周期为 $1$，价值为 $1$。
• 子串 $s[4,6] = \text{aaa}$ 的最小整周期为 $1$，价值为 $1$。
• 子串 $s[5,6] = \text{aa}$ 的最小整周期为 $1$，价值为 $1$。
• 子串 $s[7,8] = \text{bb}$ 的最小整周期为 $1$，价值为 $1$。

子任务

对于所有测试数据，均有：

• $1 \le n \le 10^6$；
• 对于所有 $1 \le i \le n$，$s_i$ 均为小写英文字母；
• 对于所有 $1 \le i \le n$，均有 $0 \le f_i \le 10^9$。

特殊性质 A：对于所有 $1 \le i \le n$，均有 $f_i = [2 \mid i]$。

特殊性质 B：存在正整数 $k$ 满足对于所有 $1 \le i \le n$，均有 $f_i = [k \mid i]$。