問題 D : 撃墜フェーズ

時は2011年，世界ではG〇〇gle社やT〇pC〇der社によってプログラミングコンテストが頻繁に開催されており， 多くのプログラマが参加している． 東京大学の学生である私もその一人であり，(iwi)というIDで活動している．

今日も友人のkita_masaとともにT〇pC〇der社のコンテストに参加している． 今ちょうど75分のコーディングフェイズが終わり，あと数分で撃墜フェイズが始まろうとしている． 撃墜フェイズでは，他の人のソースコードを読んで，間違った答えを返す入力を与えることによりスコアを得ることができる． kita_masaはとてもドジなので，いつもいろいろなバグを埋めこんで撃墜されている． 奴とはもう長い付き合いだから問題を読めばどんなバグを埋めこんでいるのかが簡単に想像できる． 問題文をちゃんと読まないkita_masaのことだ．おそらく今日は Medium問題の入力の制約を読み飛ばしてint型で解いてしまい，オーバーフローを起こしているに違いない． オーバーフローが起きた場合に間違った答えを返すような入力を用意せねば．

問題

変数 x を含む数式と x の値の範囲が与えられる． この範囲のなかで，式をint型(符号付き32ビット整数)で評価した際に間違った答えを返すような x の値を一つ出力せよ． そのような x が存在しないならば"Passed System Test"と出力せよ．

ただし，式は以下のBNFで表現されるものとする:

<expr> ::= "x"
         | <num>
         | "(" <expr> + <expr> ")"
         | "(" <expr> - <expr> ")"
         | "(" <expr> * <expr> ")"

<num>は  - 231 以上 231 未満の整数である． 「x--1」のような通常のC言語などでは文法エラーとなる式も正しい式とみなされることに注意せよ．

式の評価は，再帰的に内側の式を評価していくことにより行うものとする．

入力

入力の一行目には数式が与えられる． 入力の二行目には二つの整数 s, t が与えられ，これは変数 x の範囲が s 以上 t 以下であることを示す．

出力

間違った答えを返す x の値，もしくは"Passed System Test"を出力せよ．

制約

部分点

20点分の入力は， t - s ≤ 100 を満たす．

入出力例

入力例1:

(x*-1)
-2147483648 2147483647

入力例 1 に対する出力の例:

-2147483648

入力例2:

((x*(x+1))-(x*x))
0 100000

入力例 2 に対する出力の例:

Passed System Test
Problemsetter: 岩田 陽一