AT_pakencamp_2018_day2_d 一次元オセロ　(1D Othello)

[problemUrl]: https://atcoder.jp/contests/pakencamp-2018-day2/tasks/pakencamp_2018_day2_d $ N $ 個のオセロの駒が左から右に一直線に並べられています。 駒の色は文字列 $ S $ で表され、$ S $ の左から $ i $ 文字目が左から $ i $ 番目の駒に対応しており、`W` のとき白、`B` のとき黒が表になっていることを表します。 マジシャンの IOI 君は、駒を $ M $ 個新たに置きました。$ i $ 個目の駒の置き方は、$ D_i,\ F_i $ の 2 つの値で決まり、 - $ D_i\ = $ `L` のとき一番左の駒の少し左に置き、$ D_i\ = $ `R` のとき一番右の駒の少し右に置くことを表し、 - $ F_i\ = $ `W` のとき表を白、$ F_i\ = $ `B` のとき表を黒にして駒を置くことを表す。 - 駒を置いた瞬間。置いた石と、それに最も近い同じ色の別の石に挟まれた石はすべて裏返されます！ しかし、JOI 君はこの手品を見ることができませんでした。そこで、手品の内容がどのようなものだったか知るために、$ Q $ 個の質問をしました。 $ i $ 個目の質問は、「$ T_i $ 回目に駒を置いたとき、(その時点での) 左から $ P_i $ 番目の駒の色が何だったか？」です。 IOI 君のために、その質問すべてに答えてください。

入力は以下の形式で標準入力から与えられます。 > $ N $ $ S $ $ M $ $ D_1 $ $ F_1 $ $ D_2 $ $ F_2 $ : : $ D_M $ $ F_M $ $ Q $ $ T_1 $ $ P_1 $ $ T_2 $ $ P_2 $ : : $ T_Q $ $ P_Q $

$ Q $ 行にわたって出力してください。 $ i $ 行目には、$ i $ 回目の質問の答えを出力してください。

### 制約 - $ N $ は $ 1 $ 以上 $ 150\ 000 $ 以下の整数 - $ M $ は $ 1 $ 以上 $ 150\ 000 $ 以下の整数 - $ Q $ は $ 1 $ 以上 $ 150\ 000 $ 以下の整数 - $ S $ は長さ $ N $ の `W` と `B` だけで構成された文字列である - $ D_i $ は `L` または `R` - $ F_i $ は `W` または `B` - $ T_i $ は $ 1 $ 以上 $ M $ 以下 - $ T_i $ 回目に駒を置き終わったとき、駒は $ P_i $ 個以上ある - $ D_i $, $ F_i $, $ S $ 以外の入力は全て整数 ### 小課題 小課題 $ 1 $ \[$ 25 $ 点\] - $ N\ \leq\ 100 $ を満たす。 - $ M\ \leq\ 100 $ を満たす。 - $ Q\ \leq\ 100 $ を満たす。 小課題 $ 2 $ \[$ 29 $ 点\] - $ N\ =\ 1 $ を満たす。 小課題 $ 3 $ \[$ 33 $ 点\] - $ N\ \leq\ 100 $ を満たす。 小課題 $ 4 $ \[$ 13 $ 点\] - 追加の制約はない。 ### Sample Explanation 1 最初、駒の色は `WWBBW` となっています。 $ 1 $ 回目、左に `B` を置くと、`BWWBBW` → `BBBBBW` となります。一番左の `B` と次の (左から $ 4 $ 番目の) `B` に挟まれた駒はすべてひっくり返されるからです。 $ 2 $ 回目、右に `W` と置くと、`BBBBBWW` となるが、その後何も裏返されません。 $ 3 $ 回目、右に `B` と置くと、`BBBBBWWB` → `BBBBBBBB` となります。 次に、JOI 君の質問に答えます。 $ 1 $ 個目の質問は、「$ 1 $ 回目が終わった後に、左から $ 2 $ つ目はどちらが表を向いていたか？」です。$ 1 $ 回目が終わった後は `BBBBBW` なので、左から $ 2 $ つ目は `B`、すなわち黒色です。 $ 2 $ 個目の質問は、「$ 3 $ 回目が終わった後に、左から $ 4 $ つ目はどちらが表を向いていたか？」です。$ 3 $ 回目が終わった後は `BBBBBBBB` なので、左から $ 4 $ つ目は `B`、すなわち黒色です。 ### Sample Explanation 2 最初、駒は `B` となっていくが、`WB` → `BBB` → `BBBW` → `BBBWW` → `WWWWWW` と変化していきます。