AT_xmascon22_b Battle Solving

整数 $ N, K, P $ および，文字 `A`, `B` からなる長さ $ N $ の文字列 $ S $ が与えられる．各 $ k = 1, 2, \ldots, K $ に対して以下の問に答えよ (各 $ k $ に関する問は別々に考えよ)． くろうさとしろうさが問題の速解き競争を行う．問題は $ 1 $ 問ずつ出題され， $ i $ 問目 ( $ i = 1, 2, \ldots $ ) は以下のようになる： - $ i \le N $ かつ $ S $ の $ i $ 文字目が `A` である場合，確率 $ \frac{P}{100} $ でくろうさが先に解き，確率 $ 1 - \frac{P}{100} $ でしろうさが先に解く． - $ i \le N $ かつ $ S $ の $ i $ 文字目が `B` である場合，確率 $ 1 - \frac{P}{100} $ でくろうさが先に解き，確率 $ \frac{P}{100} $ でしろうさが先に解く． - $ i > N $ の場合，確率 $ \frac{1}{2} $ でくろうさが先に解き，確率 $ \frac{1}{2} $ でしろうさが先に解く． 「 $ i $ 問目をくろうさが先に解く」という事象たちは互いに独立である． 「先に解いた問題」が $ k $ 問に到達したうさぎが現れた時点で競争を終了し，そのうさぎの優勝とする．くろうさが優勝する確率と $ \frac{1}{2} $ の**大小を比較せよ．**

入力は以下の形式で標準入力から与えられる． > $ N $ $ K $ $ P $ $ S $

以下のような長さ $ K $ の文字列を出力せよ：各 $ k = 1, 2, \ldots, K $ に対し， - くろうさが優勝する確率が $ \frac{1}{2} $ より大きい場合， $ k $ 文字目は `+` である． - くろうさが優勝する確率が $ \frac{1}{2} $ に等しい場合， $ k $ 文字目は `0` である． - くろうさが優勝する確率が $ \frac{1}{2} $ より小さい場合， $ k $ 文字目は `-` である．

### Sample Explanation 1 $ k = 1 $ のとき， $ 1 $ 問目をくろうさが先に解く確率は $ \frac{1}{4} $ なので，くろうさが優勝する確率は $ \frac{1}{4} $ である． $ k = 2 $ のとき， - $ 1 $ 問目をくろうさが先に解き， $ 2 $ 問目をくろうさが先に解く確率は $ \frac{3}{16} $ - $ 1 $ 問目をくろうさが先に解き， $ 2 $ 問目をしろうさが先に解き， $ 3 $ 問目をくろうさが先に解く確率は $ \frac{1}{32} $ - $ 1 $ 問目をしろうさが先に解き， $ 2 $ 問目をくろうさが先に解き， $ 3 $ 問目をくろうさが先に解く確率は $ \frac{9}{32} $ なので，くろうさが優勝する確率は $ \frac{1}{2} $ である． ### Constraints - $ 1 \le N \le 10^5 $ ． - $ 1 \le K \le 10^5 $ ． - $ 0 \le P \le 100 $ ． - $ S $ は `A`, `B` からなる長さ $ N $ の文字列である．