Given a string $s$ of length $n$ and a sequence of coefficients $f_1, f_2, \dots, f_n$.

A positive integer $d$ is defined as a period of a substring $s[l, r]$ ($1 \le l \le r \le n$) if and only if $d \le r - l + 1$ and $s_i = s_{i+d}$ for all $l \le i \le r - d$.

A positive integer $d$ is defined as a full period of a substring $s[l, r]$ ($1 \le l \le r \le n$) if and only if $d$ is a period of $s[l, r]$ and $d$ divides $r - l + 1$.

For $1 \le l \le r \le n$, the value of the substring $s[l, r]$ is defined as $w(l, r) = f_{(r-l+1)/d}$, where $d$ is the minimum full period of $s[l, r]$.

For all $1 \le i \le n$, calculate the sum of the values of all substrings ending at $i$, i.e., $\sum_{j=1}^i w(j, i)$. Since the answer may be large, you only need to output the result modulo $998,244,353$.

Input

The input is read from standard input. The first line contains a positive integer $n$, representing the length of the string $s$. The second line contains a string $s$ of length $n$. The third line contains $n$ non-negative integers $f_1, f_2, \dots, f_n$, representing the given sequence of coefficients.

Output

Output to standard output. Output a single line containing $n$ non-negative integers, where the $i$-th ($1 \le i \le n$) non-negative integer represents the sum of the values of all substrings ending at $i$, modulo $998,244,353$.

Examples

Input 1

8
babaaabb
0 1 1 0 0 0 0 0

Output 1

0 0 0 1 1 2 0 1

Note 1

The following are all substrings with non-zero value: Substring $s[1, 4] = \text{baba}$ has a minimum full period of $2$, value is $1$. Substring $s[4, 5] = \text{aa}$ has a minimum full period of $1$, value is $1$. Substring $s[4, 6] = \text{aaa}$ has a minimum full period of $1$, value is $1$. Substring $s[5, 6] = \text{aa}$ has a minimum full period of $1$, value is $1$. * Substring $s[7, 8] = \text{bb}$ has a minimum full period of $1$, value is $1$.

Subtasks

For all test data, it is guaranteed that: $1 \le n \le 10^6$; For all $1 \le i \le n$, $s_i$ is a lowercase English letter; * For all $1 \le i \le n$, $0 \le f_i \le 10^9$.

Special Property A: For all $1 \le i \le n$, $f_i = [2 \mid i]$. Special Property B: There exists a positive integer $k$ such that for all $1 \le i \le n$, $f_i = [k \mid i]$.