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, the friends took out colorful necklaces made by stringing together multicolored beads.

The necklaces glittered in the afterglow of the sunset. Looking closely, they found that many birds had already gathered around the necklaces. The birds brought Madeline and her friends to a place they had never been to before. A huge flock of birds gathered here, seemingly trying to express something to them.

After Madeline observed carefully, she found that the way some birds flew seemed to form an ordered formula, while the way other birds flew formed some symbols. These symbols described a question.

The question described by the birds is as follows:

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

Specifically:

• ( and ) are parentheses. Operations inside parentheses have higher precedence.

• &, |, and ^ represent the three bitwise operations AND, OR, and XOR. These three operations have the same precedence.

• 0 and 1 are the constants 0 and 1.

• Lowercase letters represent variables. Multiple occurrences of the same lowercase letter represent different variables. Each variable takes a value of 0 or 1.

• The expression is defined as follows:

  • A variable, 0, and 1 are all expressions.
  • If $T$ is an expression, then $(T)$ is an expression.
  • If $S$ and $T$ are expressions, then $S\&T$, $S|T$, and $S\ \hat{}\ T$ are expressions.
  • For example, $(1\ \hat{}\ 1\&0)$ is an expression, and its result is $0$, but $(1\&0$ is not an expression.

The birds believe that an expression that can evaluate to $1$ is beautiful. Define the beauty of an expression as the number of assignments (among all $2^v$ assignments to its $v$ variables) that make the expression evaluate to $1$.

The birds also believe that the harmony of an expression is the sum of the beauties of all its contiguous subexpressions (including itself).

The birds are fickle. From time to time, they will change the character at one position, but they promise Madeline and her friends that they will not change the parentheses, and after each modification the whole string is still an expression.

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

The birds also said that the expression may be too harmonious, so Madeline only needs to output the harmony modulo $998244353$.

Input Format

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

The second line contains a string representing the initial expression.

The next $m$ lines each contain an integer $a$ and a character $b$, meaning the birds change the character at position $a$ to $b$.

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

Output Format

Output $m$ lines. The $i$-th line contains the value after the $i$-th modification. Since the harmony may be very large, you need to output it modulo $998244353$.

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

6
8
4
6
4

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

29
30
27
35
35
43
35
35
56
35

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

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

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

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

Hint

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

There are subtasks.

For $5\%$ of the testdata: $n \leq 12$, $len \leq 50$, $m \leq 50$, time limit $1\text{s}$.

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

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

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

For the first $50\%$ of the testdata: $n \leq 10^5$, $len \leq 4\times 10^5$, $m \leq 10^5$, and the parentheses are guaranteed to be generated randomly.

For $100\%$ of the testdata: $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 testdata, the time limit is $3\text{s}$.

Translated by ChatGPT 5