近所に住む秋田博士は在野の歴史研究家であり, 最近小野小町に関する新たな古文書を発見したそうだ.
小野小町が交際を望む深草少将に100夜欠かさず通い続けることを条件に出したという伝説は広く知られているが, 彼の主張によると, この発見により新たに, 2人は毎晩とあるゲームをしていたことがわかったという.
そのルールは以下の通りである.
有効な数式の詳しい定義は下記を見てほしい.
このゲームにおいて, 最終的な数式の計算結果が大きいほど, 深草少将の通うべき日数を減らしてあげることになっていたらしい. すなわち, 深草少将は結果を最大化させることが目的であり, 小野小町は最小化させることが目的である.
ところで, 古文書には召使が決めた編集回数と数式については記録が残っていたのであるが, 肝心の結果の方は虫食いにより読めなくなってしまっていた. 博士は結果に興味を持ち, 自力で計算してみようと思ったものの, ゲーム理論が得意でない彼には難しすぎたため, とりあえず近所のあなたに助けを求めてきたようだ. そこであなたはプログラムを書いて彼に協力することにした.
平安時代に現代的な数式があったということに胡散臭さを感じるかもしれないが, 近所付き合いという大義の前に, そのような些事を気にするべきではないのだ.
このゲームにおける有効な数式とは, "(", ")", "*", "+", "-", "&", "^", "|", "0" - "9" の 18 種類の文字のみからなる空でない文字列であり, さらに, 有限個の項を2項演算子で結合したものである. 書き下すと,
[項][2項演算子][項][2項演算子]...[2項演算子][項]
のようになる.
項とは, "("[有効な数式]")" のようにカッコで挟まれた有効な数式, または正の整数である. 正の整数は, 先頭に "0" を持たない, 数字のみからなる文字列である.
最後に, 2項演算子とは, "*", "+", "-", "&", "^", "|" のいずれかちょうど 1 文字である. 詳しい定義は下記を見てほしい.
以上の規則から,
などは, 無効な数式であるとみなされる.
一方で,
などは, 冗長ではあるが, 上の規則の下では受理され, 有効な数式とみなされることに注意してほしい.
このゲームにおいて, 2項演算子は "*", "+", "-", "&", "^", "|" の 6 種類がある. それぞれ, 乗算, 加算, 減算, ビットごとの論理積, ビットごとの排他的論理和, ビットごとの論理和である. なお, ビット演算を考えるとき, 負の数は十分大きな桁数の2の補数で表現されていると見なされる. すなわち, 普通の符号付き整数型で計算すると考えてもよい.
また, 優先順位は高い方から,
の順である.
なお, + より * の方が優先順位が高いとは,
2*4+3*5
のような式において * のほうが先に計算されるという意味であり, 言い換えると,
(2*4)+(3*5)
となるということである.
また, すべての2項演算子は左結合であるとする. これは,
2^4^3^5
のような式において左から順に計算するという意味であり, 言い換えると,
((2^4)^3)^5
となるということである.
入力は複数のデータセットから構成される. 各データセットは1回のゲームで召使が決めた編集回数と数式を表し, その形式は以下の通りである.
N Expression
N は召使が決めた編集回数であり, 1 ≤ N ≤ 11 と仮定してよい. また, Expression は召使が決めた数式であり, "(", ")", "*", "+", "-", "&", "^", "|", "0" - "9" の 18 種類の文字のみからなる, 7 文字以下の空でない文字列として与えられる. なお, 上で定義した有効な数式のみが与えられ, 無効な数式が与えられることはないと仮定してよい.
入力の終わりは,
0 #
で表される.
なお, データセットは 99 個以下であると仮定してよい.
各データセットに対して, 両者が最善を尽くしたときの最終的な数式の計算結果を 1 行で出力せよ. それ以外の余計な文字を出力してはならない.
1 1 2 2 3 1+2*3-4 3 1|2^3&4 3 (1+2)*3 3 1-1-1-1 0 #
91 2 273 93 279 88