Problem Description: Dr. Akita, an amateur historian living nearby, has recently discovered a new document concerning Ononokomachi. It is widely known that Ononokomachi set a condition for Fugiwara Michinaga that he should visit her for 100 consecutive nights, but according to his claim, this discovery reveals that they were playing a game every evening.
The rules of the game are as follows:
A servant decides the editing count and valid formula at the beginning
Ononokomachi and Fugiwara Michinaga edit the formula alternately in the order of Michinaga Fukuda, Ononokomachi, Michinaga Fukuda, Ononokomachi,...
The game ends once Michinaga and Ononokomachi collectively edited the number of times decided by the servant
In one formula edit, you can either add 1 character to the formula or delete 1 character from it
You must not edit the formula in such a way that it becomes invalid
Please refer to the detailed definition of valid formula below.
In this game, the larger the calculation result of the final formula is, the less the days Michinaga has to visit Ononkomachi. Hence, Michinaga's goal is to maximize the result, while Ononokomachi's goal is to minimize it.
However, while there were records of the formulas and edit counts that the servants had determined in the old documents, the important results were eaten away by insects and could not be read. Dr. Akita was interested in the outcome and tried to calculate it by himself, but since he was not good at game theory, he asked for help from his neighboring friend - you. So you decided to help him by writing a program.
Whether manipulative on the pretext of good-neighborliness or not, you might feel suspicious about the existence of modern-day formulas in the Heian period, but in light of social obligations, that should not be your concern.
Definition of a valid formula
A valid formula in this game is a non-empty string consisting only of the 18 types of characters: "(", ")", "*", "+", "-", "&", "^", "|", and "0" - "9", and it is formed by connecting a finite number of terms with binary operators. It can be written as:
[term][binary operator][term][binary operator]...[binary operator][term]
The term is enclosing the valid data between "(", ")" or a positive integer. A positive integer is a string consisting only of digits without a leading "0."
Finally, binary operators are exactly 1 character and include "*", "+", "-", "&", "^", and "|." Please see the details below.
From these rules, expressions that are invalid include those that:
Have a 2-character binary operator that is not valid, such as "1+-1"
Are not joined by a binary operator, such as "+1"
Are not valid terms due to mismatched parentheses, such as "2)", or "(3"
Do not start with 0 or have a character other than a valid positive integer, such as "0" or "01"
On the other hand, be aware that:
Expressions like "(1+2)" with parentheses on the outermost part,
Expressions like "("(1+2))К3" with double parentheses,
Expressions like "(1)+3" with only numbers inside parentheses,
Expressions like "(1*2)+3" with binary operators that have the same precedence,
are redundant but are considered valid under the above rules.
1 1
2 2
3 1+2*3-4
3 1|2^3&4
3 (1+2)*3
3 1-1-1-1
0 #