← 返回题目列表

AtCoder · pakencamp_2018_day2_d

D. 一维奥赛罗 (1D 奥赛罗)

中文机器翻译题面 查看原题

配点: 100 点

問題文

N 有若干个黑白棋棋子从左到右排成一条直线。
棋子的颜色用字符串表示。 S 表示,S 从左数第 i 个字符对应从左数第 i 个棋子。W 为时棋子面朝白色,B 为时棋子面朝黑色。

魔术师 IOI 君将棋子 M 放了一个新棋子。i 第几个棋子的放置方式由D_i, F_i 两个值决定,

  • D_i = L 为时表示放在最左边棋子左边稍许位置,D_i = R 为时表示放在最右边棋子右边稍许位置,
  • F_i = W 为时表示棋子正面为白色,F_i = B 为时表示棋子正面为黑色后放置棋子。
  • 放下棋子的一瞬间。放下的棋子以及被最接近的同颜色其他棋子威胁到的棋子都会被返还!

但是,JOI君无法看到这个魔术。因此,为了知道魔术的内容是什么,Q 提出了个质问。 i 第个质问是,“T_i 第回放下棋子时,(当时的)从左数第 P_i 个棋子的颜色是什么?”

请为IOI君回答所有这些质问。

制約

  • 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 除此之外的输入都是整数

入力

输入是按以下格式从标准输入给出的。

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 输出第回质问的答案。

小課題

小課題 1 [25 点]

  • N \leq 100 很满意。 对于
  • M \leq 100 很满意。 对于
  • Q \leq 100 很满意。 对于

小課題 2 [29 点]

  • N = 1 很满意。 对于

小課題 3 [33 点]

  • N \leq 100 很满意。 对于

小課題 4 [13 点]

  • 没有额外的否定。

入力例 1

5
WWBBW
3
L B
R W
R B
2
1 2
3 4

出力例 1

B
B

最初,马匹的颜色是 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,也就是黑色。


入力例 2

1
B
5
L W
L B
R W
R W
L W
5
1 1
2 2
3 2
4 5
5 3

出力例 2

W
B
B
W
W

一开始,马是 B ,然后变成WB → BBB → BBBW → BBBWW → WWWWWW 会发生变化。

也就是说,在这个输入示例中,黑白棋的排列会像下面这样变化。