Skibidus thinks he's Him! He proved it by solving this difficult task. Can you also prove yourself?

Given a binary string$^{\text{∗}}$ $t$, $f(t)$ is defined as the minimum number of contiguous substrings, each consisting of identical characters, into which $t$ can be partitioned. For example, $f(\texttt{00110001}) = 4$ because $t$ can be partitioned as $\texttt{[00][11][000][1]}$ where each bracketed segment consists of identical characters.

Skibidus gives you a binary string $s$ and $q$ queries. In each query, a single character of the string is flipped (i.e. $\texttt{0}$ changes to $\texttt{1}$ and $\texttt{1}$ changes to $\texttt{0}$); changes are saved after the query is processed. After each query, output the sum over all $f(b)$ where $b$ is a non-empty subsequence$^{\text{†}}$ of $s$, modulo $998\,244\,353$.

Input

The first line contains an integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.

The first line of each test case contains a binary string $s$ ($1 \leq |s| \leq 2 \cdot 10^5$).

The following line of each test case contains an integer $q$ ($1 \leq q \leq 2 \cdot 10^5$) — the number of queries.

The following line contains $q$ integers $v_1, v_2, \ldots, v_q$ ($1 \leq v_i \leq |s|$), denoting $s_{v_i}$ is flipped for the $i$'th query.

It is guaranteed that the sum of $|s|$ and the sum of $q$ over all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, output $q$ integers on a single line — the answer after each query modulo $998\,244\,353$.

见题面 Input 部分

见题面 Output 部分

In the first test case, $s$ becomes $\texttt{001}$ after the first query. Let's calculate the answer for each subsequence:

• $f(s_1) = f(\texttt{0}) = 1$
• $f(s_2) = f(\texttt{0}) = 1$
• $f(s_3) = f(\texttt{1}) = 1$
• $f(s_1 s_2) = f(\texttt{00}) = 1$
• $f(s_1 s_3) = f(\texttt{01}) = 2$
• $f(s_2 s_3) = f(\texttt{01}) = 2$
• $f(s_1 s_2 s_3) = f(\texttt{001}) = 2$

The sum of these values is $10$, modulo $998\,244\,353$.