Problem Background

Sever the Skyline

Black Moonrise

Good Karma

Golden Feather

Mirror Magic

Center of the Earth

No More Running

And...

Say Goodbye.

Problem Description

At the farewell banquet, friends present colorful necklaces made of beads.

The necklaces sparkle in the sunset, and upon closer inspection, many birds have gathered around them. These birds lead Madeline and her friends to a place they have never been before, where a large flock of birds seems to want to convey something to them.

After careful observation by Madeline, she noticed that some birds' flight patterns formed an ordered expression, while others' patterns were symbols representing a question.

The question posed by the birds is as follows:

The expression formed by the birds consists of (, ), ^, &, |, 0, 1, and lowercase letters, and is a valid expression.

Where:

• (, ) denote parentheses, with operations inside the parentheses having higher precedence.

• &, |, ^ represent the bitwise operations AND, OR, XOR, respectively, which have the same precedence.

• 0, 1 are simply 0 and 1.

• Lowercase letters represent variables, and multiple occurrences of the same letter represent different variables, each taking a value of 0 or 1.

• The definition of an expression is as follows:

  • A variable, 0, or 1 is an expression.
  • If $T$ is an expression, then $(T)$ is an expression.
  • If $S$ and $T$ are expressions, then $S\&T$, $S|T$, $S\ \hat{}\ T$ are also expressions.
  • For example, $(1\ \hat{}\ 1\&0)$ is an expression with a result of $0$, but $(1\&0$ is not a valid expression.

The birds believe that an expression is beautiful if it can evaluate to 1. The beauty of an expression is defined as the number of ways to assign values to its $v$ variables such that the expression evaluates to 1 out of the $2^v$ possible assignments.

The birds also believe that the harmony of an expression is the sum of the beauties of all its sub-continuous expressions (including itself).

The birds are fickle and may change a character in the expression from time to time, but they assure Madeline and her friends that they will not change the parentheses, and the modified string will still be a valid expression.

Can you help Madeline and her friends calculate the harmony of the expression after each modification?

The birds also mentioned that since the expression might be too harmonious, Madeline can simply report the harmony modulo $998244353$.

Input Format

The first line contains an integer $m$, representing the number of modifications.

The second line is a string representing the initial expression.

The next $m$ lines, each containing an integer $a$ and a character $b$, indicate that the character at position $a$ is changed to $b$.

In the input expression, a lowercase letter represents a variable. (Note that a letter may appear multiple times but represents different variables)

Output Format

Output $m$ lines, where the $i$-th line is the harmony value after the $i$-th modification, modulo $998244353$.

Sample Input and Output

Input Sample #1

5
(1&b)
3 |
2 a
3 &
3 ^
4 1

Output Sample #1

6
8
4
6
4

Input Sample #2

10
1|a&1&(0&0|1)&1^1^a
1 0
10 1
2 &
1 a
14 ^
4 |
17 0
4 ^
15 a
15 1

Output Sample #2

29
30
27
35
35
43
35
35
56
35

Input Sample #3

30
0|0&0^(a&a&(1^0&0^0)^0&1)|0&a|1|(a&a|0|1|0^a&0&a|(a^0&1|a|a)^a|a&0&0)^a
71 1
51 0
57 0
65 &
26 |
5 a
71 a
56 |
4 &
41 ^
52 |
52 ^
59 a
44 0
54 ^
65 &
51 a
36 1
16 ^
1 1
52 ^
2 |
59 0
58 |
37 ^
55 1
10 1
26 ^
18 |
44 0

Output Sample #3

21323
10686
5360
5360
5360
8469
16277
16277
16277
16277
16277
16277
16277
8223
8253
8253
16354
8359
8385
8394
8394
8394
4262
4262
4262
4262
2430
2430
2430
2430

Input Sample #4

20
a^1&0^1^1&1&a&1^a|1&a|0&a^a^1^a^0&1^a&a|a|1^0|a|0^1^a|0^0&1&1&a&a|0^0&a&1&a|a&a^a|0^a^a|a^1|a|1^a|0|a^0&0&0|a|a|a^0^1&0^1&a|1&0
8 ^
28 |
100 ^
119 a
40 &
105 1
31 1
125 1
53 1
98 &
98 &
98 &
52 &
2 ^
38 |
6 ^
58 ^
106 |
12 ^
57 1

Output Sample #4

957521426
957521583
874091659
57281108
57278566
140708493
120472431
120472431
561701787
551192201
551192201
551192201
551120577
551120577
551121853
551121853
551178140
656274015
656274025
656222855

Notes/Hints

Let $n$ be the number of variables and 0,1 in the expression, and $len$ be the length of the expression.

There are subtasks:

For $5\%$ of the data, $n \leq 12, len \leq 50, m \leq 50$, 1s.

For an additional $10\%$ of the data, $n \leq 150, len \leq 400, m \leq 200$.

For an additional $10\%$ of the data, $n \leq 10^5, len \leq 2 \times 10^5, m \leq 10$, no parentheses.

For an additional $10\%$ of the data, $n \leq 10^5, len \leq 2 \times 10^5, m \leq 10^5$, no parentheses.

For the first $50\%$ of the data, $n \leq 10^5, len \leq 4 \times 10^5, m \leq 10^5$, parentheses are randomly generated.

For $100\%$ of the data, $n \leq 10^5, len \leq 4 \times 10^5, m \leq 10^5, len - 2 \times n \leq 2 \times 10^5$.

For the last $95\%$ of the data, the time limit is 3s.

见题面 Input 部分

见题面 Output 部分