AT_joi2023ho_e 現代的な機械 (Modern Machine)

ビ太郎は，誕生日プレゼントとして JOI マシンをもらった． JOI マシンは， $ 1 $ 個の **ボール**， $ N $ 個の **ライトタイル**， $ M $ 個の **ボタン** からなる． ライトタイルにはそれぞれ $ 1 $ から $ N $ までの番号が付けられており， 電源を入れると，ライトタイル $ i $ ( $ 1 \leqq i \leqq N $ ) は色 $ C_i $ (青 (`B`)，赤 (`R`) のいずれか) で光るようになっている． また，ボタンにはそれぞれ $ 1 $ から $ M $ までの番号が付けられており， ボタン $ j $ ( $ 1 \leqq j \leqq M $ ) を押すと，次のようなことが起こる． 1. ライトタイル $ A_j $ の上にボールが置かれる． 2. ライトタイル $ A_j $ の色が (元の色にかかわらず) 赤になる． 3. ボールが取り除かれるまで，以下のことが繰り返し行われる． 今，ボールが置かれているライトタイルの番号を $ p $ とする． ライトタイル $ p $ の色が青の場合ライトタイル $ p $ の色が赤に変わる．その後，もし $ p=1 $ の場合はボールが取り除かれ，そうでない場合はボールがライトタイル $ p-1 $ の上に移動する．ライトタイル $ p $ の色が赤の場合ライトタイル $ p $ の色が青に変わる．その後，もし $ p=N $ の場合はボールが取り除かれ，そうでない場合はボールがライトタイル $ p+1 $ の上に移動する． JOI マシンに興味を持ったビ太郎は， $ Q $ 回の実験を計画している． $ k $ 回目 ( $ 1 \leqq k \leqq Q $ ) の実験は，JOI マシンの電源を入れた後，ボタン $ L_k, L_k+1, \ldots, R_k $ をこの順に押すというものである． ただし，ボールが取り除かれるまでは，次のボタンを押さずに待つものとする． JOI マシンの情報および実験の情報が与えられるので， それぞれの実験について，実験が終わった後における，色が赤であるようなライトタイルの個数を求めるプログラムを作成せよ． ---

入力は以下の形式で標準入力から与えられる． > $ N $ $ M $ $ C_1C_2 \cdots C_N $ $ A_1 $ $ A_2 $ $ \cdots $ $ A_M $ $ Q $ $ L_1 $ $ R_1 $ $ L_2 $ $ R_2 $ $ \vdots $ $ L_Q $ $ R_Q $

標準出力に $ Q $ 行出力せよ． $ k $ 行目 ( $ 1 \leqq k \leqq Q $ ) には， $ k $ 回目の実験が終わった後における，色が赤であるようなライトタイルの個数を出力せよ． ---

### 小課題 1. ( $ 3 $ 点) $ N \leqq 300 $ ， $ M \leqq 300 $ ， $ Q = 1 $ ． 2. ( $ 12 $ 点) $ N \leqq 7\,000 $ ， $ M \leqq 7\,000 $ ， $ Q = 1 $ ． 3. ( $ 10 $ 点) $ Q \leqq 5 $ ． 4. ( $ 11 $ 点) $ N = 10 $ ， $ C_i $ は `R` である ( $ 1 \leqq i \leqq N $ )． 5. ( $ 26 $ 点) $ i \leqq t $ ならば $ C_i $ が `R` であり， $ i > t $ であれば $ C_i $ が `B` であるような整数 $ t $ ( $ 0 \leqq t \leqq N $ ) が存在する． 6. ( $ 17 $ 点) $ A_j \leqq 20 $ または $ A_j > N - 20 $ ( $ 1 \leqq j \leqq M $ )． 7. ( $ 21 $ 点) 追加の制約はない． --- ### Sample Explanation 1 $ 1 $ 回目の実験は次のように進行する． 1. ボタン $ 1 $ が押され，ボールがライトタイル $ 4 $ の上に置かれる． 2. ライトタイル $ 4 $ の色が赤になる．ただし，元からライトタイル $ 4 $ の色が赤なので，ライトタイル $ 4 $ の色は変わらない． 3. その後，次のことが起こる． 1. 現在のライトタイル $ 4 $ の色は赤なので，ライトタイル $ 4 $ の色が青に変わり，ボールがライトタイル $ 5 $ の上に移動する． 2. 現在のライトタイル $ 5 $ の色は青なので，ライトタイル $ 5 $ の色が赤に変わり，ボールがライトタイル $ 4 $ の上に移動する． 3. 現在のライトタイル $ 4 $ の色は青なので，ライトタイル $ 4 $ の色が赤に変わり，ボールがライトタイル $ 3 $ の上に移動する． 4. 現在のライトタイル $ 3 $ の色は赤なので，ライトタイル $ 3 $ の色が青に変わり，ボールがライトタイル $ 4 $ の上に移動する． 5. 現在のライトタイル $ 4 $ の色は赤なので，ライトタイル $ 4 $ の色が青に変わり，ボールがライトタイル $ 5 $ の上に移動する． 6. 現在のライトタイル $ 5 $ の色は赤なので，ライトタイル $ 5 $ の色が青に変わり，ボールが取り除かれる． 実験が終わった時点で，色が赤であるようなライトタイルはライトタイル $ 1 $ の $ 1 $ つのみであるため， $ 1 $ を出力する． この入力例は小課題 $ 1, 2, 3, 6, 7 $ の制約を満たす． --- ### Sample Explanation 2 $ 1 $ 回目の実験については，実験が終わった時点で，色が赤であるようなライトタイルはライトタイル $ 1, 2, 3, 4, 5 $ の $ 5 $ つであるため， $ 5 $ を出力する． $ 2 $ 回目の実験については，実験が終わった時点で，色が赤であるようなライトタイルは存在しないため， $ 0 $ を出力する． この入力例は小課題 $ 3, 6, 7 $ の制約を満たす． --- ### Sample Explanation 3 この入力例は小課題 $ 1, 2, 3, 6, 7 $ の制約を満たす． --- ### Sample Explanation 4 この入力例は小課題 $ 3, 4, 5, 6, 7 $ の制約を満たす． --- ### Sample Explanation 5 この入力例は小課題 $ 3, 5, 6, 7 $ の制約を満たす． --- ### Sample Explanation 6 この入力例は小課題 $ 6, 7 $ の制約を満たす． ### Constraints - $ 3 \leqq N \leqq 120\,000 $ ． - $ 1 \leqq M \leqq 120\,000 $ ． - $ C_i $ ( $ 1 \leqq i \leqq N $ ) は `B` または `R` である． - $ 1 \leqq A_j \leqq N $ ( $ 1 \leqq j \leqq M $ )． - $ 1 \leqq Q \leqq 120\,000 $ ． - $ 1 \leqq L_k \leqq R_k \leqq M $ ( $ 1 \leqq k \leqq Q $ )． - $ N, M, A_j, Q, L_k, R_k $ は整数である．