Problem Statement

You are given a string $S$ of length $N$ consisting of 0, 1, and ?.

You are also given $Q$ queries $(x_1, c_1), (x_2, c_2), \ldots, (x_Q, c_Q)$. For each $i = 1, 2, \ldots, Q$, $x_i$ is an integer satisfying $1 \leq x_i \leq N$ and $c_i$ is one of the characters 0 , 1, and ?.

For $i = 1, 2, \ldots, Q$ in this order, do the following process for the query $(x_i, c_i)$.

1. First, change the $x_i$-th character from the beginning of $S$ to $c_i$.
2. Then, print the number of non-empty strings, modulo $998244353$, that can be obtained as a (not necessarily contiguous) subsequence of $S$ after replacing each occurrence of ? in $S$ with 0 or 1 independently.

Constraints

• $1 \leq N, Q \leq 10^5$
• $N$ and $Q$ are integers.
• $S$ is a string of length $N$ consisting of 0, 1, and ?.
• $1 \leq x_i \leq N$
• $c_i$ is one of the characters 0 , 1, and ?.

Input

Input is given from Standard Input in the following format:

N Q
S
x_1 c_1
x_2 c_2
\vdots
x_Q c_Q

Output

Print $Q$ lines. For each $i = 1, 2, \ldots, Q$, the $i$-th line should contain the answer to the $i$-th query $(x_i, c_i)$ (that is, the number of strings modulo $998244353$ at the step 2. in the statement).