Comet OJ

C1327 [SHOI2010]滚动的正四面体

内存限制：256 MB 时间限制：1000 ms

题目描述

正四面体总共有 $4$个面，每个面都是一个正三角形。现在把它的一个面标记上字母 $A$，如图 $3$ 中所示，$A$标记在底面上：

image.png

于是，这个正四面体的滚动过程就可以用一个只包含“L”“R”“B”的字符串来描述。初始时，正四面体的 $A$面朝下，现在SECSA将给这个正四面体一串滚动指令——当然就是一个这样的字符串——让这个正四面体每秒滚动一下。也就是说，第 $1$秒内正四面体 $A$面朝下，第 $1$秒末执行第一条指令，第 $2$秒末执行第 $2$条指令，依次类推，直至将整个指令串执行完毕。

你的任务就是当SECSA询问你的时候告诉他：这个正四面体在第 $L$ 秒到第 $R$ 秒内 $A$ 面有多少秒朝着地面。当然，SECSA可能因为对这个正四面体的滚动路径不满意，他随时会修改他的某一条指令。因此你的程序应该能执行下面两个操作：

  1. 接受SECSA修个第 $i$ 条指令的信息
  2. 回答SECSA的“在第 $L$ 秒到第 $R$ 秒内 $A$ 面有多少秒朝着地面”的询问

例如，假如原指令串为“LLLLB”，那么第1、4、6秒内 $A$ 面是朝下的。此时，如果SECSA向你询问第 $3$ 秒到第 $6$ 秒的情况，你就应该回答“$2$”。而SECSA将第 $3$ 条指令修改为“R”的话，指令串就变成了“LLRLB”，那么正四面体就只有在第1、5秒内 $A$ 面朝下了。如图5所示：

image.png

一个正四面体的一次滚动显然有 $3$ 个方向可以选择：向左（L）、向右（R）、向后（B）。如图4所示：

image.png

输入格式

输入的第一行是一个整数 $n$，表示指令串中包含的指令条数。

输入的第二行是一个字符串，共包含 $n$ 个字符，每个字符是“L”“R”“B”之一，表示初始的指令串。

输入的第三行是一个整数 $m$，表示你的程序需要处理的操作总数。

接下去 $m$ 行，每行描述一个操作，为以下两种格式之一：

  1. 0 i c：表示把第 $i$ 个操作改成 $c$，$c$ 为“L”“R”“B”之一

  2. 1 L R：表示询问第 $L$ 秒到第 $R$ 秒内，$A$ 面有多少秒朝下

输入保证：$1 \le i \le N,1 \le L \le R \le N+1$

输出

对于每一个询问操作依次输出你的程序给出的回答，每个回答为一个整数，占一行。

样例

样例输入 1

5
LLLLB
3
1 3 6
0 3 R
1 3 6

样例输出 1

2
1

提示