Birds’ Harmonious Expression

In a series of banquets, friends showed off their colorful necklaces made by stringing beads. As the necklaces shimmered in the sunset, birds gathered around them and led Madeline and her friends to an unfamiliar place. There, a huge flock of birds gathered, seemingly trying to express something.

After careful observation, Madeline discovered that some of the birds flew in patterns that formed an expression while others arranged themselves as symbols that stated a problem.

The birds’ expression is a string composed of the characters ( ) ^ & | 0 1 and lowercase letters. The characters mean the following:

• ( and ) are parentheses; anything inside them has higher priority.
• &, |, and ^ denote bitwise AND, OR, and XOR respectively. These three operators have the same priority.
• 0 and 1 represent the constants 0 and 1.
• A lowercase letter represents a variable. Note that every occurrence of a letter (even if identical) is a distinct variable which may take either 0 or 1.

The grammar of an expression is defined 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, and S^T are expressions. (When constructed this way, the expression is written simply by concatenating S, the operator, and T without extra parentheses.)

For example, (1 \(\hat{}\ 1&0) is a valid expression, evaluating to 0, while (1&0 is not.

The birds believe that for an expression to be elegant it must evaluate to 1 for some assignments of values to its variables. Define the beauty of an expression as the number of assignments (out of the \(2^v\) possible, where \(v\) is the number of variables in that expression) for which the expression evaluates to 1.

Furthermore, the harmony of an expression is defined as the sum of the beauties of all its contiguous subexpressions that are valid expressions (including the expression itself).

The birds are whimsical, and sometimes they change one character in the expression. They promise not to change any parentheses and that after any change the entire string remains a valid expression. Can you help Madeline compute the harmony (modulo \(998244353\)) of the entire expression after each modification?

inputFormat

The first line contains a non-empty string S representing the initial expression. The expression consists only of characters from the set {(, ), ^, &, |, 0, 1} and lowercase letters. It is guaranteed that S is a valid expression according to the grammar described above.

The second line contains an integer Q representing the number of modifications.

Each of the following Q lines contains a modification in the format:

pos c

Here, pos (1-indexed) is the position in the string to be modified, and c is the new character. It is guaranteed that c is not a parenthesis and that after each modification, the whole string remains a valid expression.

outputFormat

For each modification, output one line containing a single integer — the harmony of the entire expression modulo \(998244353\).

sample

1
1
1 0

0

</p>