J. Shifting Tournament
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output
Destiny is spinning like the wheels of a waterwheel. Those who were high yesterday are inferior today.
— Miguel de Cervantes Saavedra, Don Quijote de la Mancha

$$$2^k$$$ teams participate in a special tournament called Shifting Tournament.

The process of Shifting Tournament is the same as the standard tournament, which consists of $$$2^k - 1$$$ games. They are held as follows:

During the first round, all teams are split into pairs: team $$$1$$$ against team $$$2$$$, team $$$3$$$ against team $$$4$$$ (exactly in this order), and so on. Within the $$$2 ^ {k - 1}$$$ games, a team who loses the game will be eliminated, and it's guaranteed that each game results in elimination of one team (no ties). After that, $$$2 ^ {k - 1}$$$ teams remain.

During the second round, the remaining team continues according to the rules above. That means $$$2 ^{k - 2}$$$ games will take place, and $$$2^{k - 2}$$$ teams remain.

During the third round, ...

This process repeats until only one team remains, and the team is declared the champion. It's clear that there are $$$k$$$ rounds exactly.

For example, the picture below describes the chronological order of games with$$$~k=3$$$.

visual picture of $$$k = 3$$$

The specialty of the tournament is the elimination method.

Let the string $$$s$$$ consisting of $$$k$$$ characters describe the elimination method in each round as follows:

  • if $$$s_i$$$ is $$$\mathtt{0}$$$, then during the $$$i$$$-th round, the team with lower index will be eliminated;
  • if $$$s_i$$$ is $$$\mathtt{1}$$$, then during the $$$i$$$-th round, the team with higher index will be eliminated;
  • if $$$s_i$$$ is $$$\mathtt{?}$$$, then during the $$$i$$$-th round, the team with lower or higher index will be eliminated.

Note that during the same round, the elimination method is the same.

Let $$$F(s)$$$ be the number of possible winners described by the string $$$s$$$. A team $$$i$$$ is a possible winner of the tournament if it is possible to replace every $$$\mathtt{?}$$$ with either $$$0$$$ or $$$1$$$ in such a way that team $$$i$$$ is the champion.

You are given the initial state of the string $$$s$$$, and you need to process $$$q$$$ queries:

  • $$$p~c$$$ — replace $$$s_p$$$ with character $$$c$$$, and print $$$F(s)$$$ as the result of the query.

Since the answer can be huge, print it modulo $$$998244353$$$.

Input

The first line contains a single integer $$$k$$$ $$$(1 \leq k \leq 10 ^ 5)$$$, denoting the number of rounds.

The second line contains a string consisting of $$$k$$$ characters, denoting the initial state of the string $$$s$$$. Each character is either $$$\mathtt{0}$$$, $$$\mathtt{1}$$$, or $$$\mathtt{?}$$$.

The third line contains a single integer $$$q$$$ $$$(1 \leq q \leq 10 ^ 5)$$$, denoting the number of queries.

The $$$i$$$-th of the next $$$q$$$ lines contains an integer $$$p$$$ and a character $$$c$$$ $$$(1 \leq p \leq k; c$$$ is either $$$\mathtt{0}$$$, $$$\mathtt{1}$$$, or $$$\mathtt{?})$$$, denoting the $$$i$$$-th query.

Output

For each query, print one integer, denoting $$$F(s) \bmod 998244353$$$.

Examples
Input
3
0?1
2
2 1
3 ?
Output
1
2
Input
36
????????????????????????????????????
1
36 1
Output
419430366
Note

In the first test case, there are exactly $$$2^3 = 8$$$ teams.

After the first query, $$$s = \mathtt{011}$$$. It's clear that there is only one champion — the team $$$2$$$.

After the second query, $$$s = \mathtt{01?}$$$. In the third round, the remaining teams are team $$$2, 6$$$. If you replace the $$$\mathtt{?}$$$ with $$$1$$$, then team $$$2$$$ will win. Otherwise, team $$$6$$$ will win. So there are $$$2$$$ possible winners.

In the second test case, note that the answer is huge, and you need to print it modulo $$$998244353$$$.