在去年的新生赛的开始几分钟，评测机出了一点小事故——对于某道题的提交，评测机全部返回了Wrong Answer！

bug很快得到了解决，qdd看到了一些同学喜提Accepted。

因为qdd的心思全在吃M上了，所以他把发气球的任务交给了你。

新生赛一共有 $n$ 个选手参加，并且每个人都提交了自己代码，每份代码的返回结果不是Accepted就是Wrong Answer。qdd一共有 $q$ 个发气球指令，每一个指令为两个整数 $l,\ r$，你需要为$[l,r]$这一段区间中获得Accepted，但还没有得到气球的选手送一个气球。qdd想知道对于每一个指令，需要给多少选手发气球。

第一行为两个整数 $n,\ q\ (1\le n,\ q\le 10^6)$，表示参赛选手的个数（座位号为$1,\ 2,\ ...,\ n$）和指令的个数。

第二行是一个长度为 $n$ 的字符串 $S$，$S[i]\ (1 \le i \le n)$ 为W或A，表示 $i$ 号选手的代码返回结果，W表示Wrong Answer，A表示Accepted。

接下来 $q$ 行，每行一个指令，包含两个整数 $l, r\ (1\le l\le r\le n)$ ，表示给$[l, r]$ 这个区间内的选手，获得Accepted但没有得到气球的选手送一个气球。

对于每个询问：
输出一行包含一个整数，表示这次询问要发多少个气球。

第一次，给2号座位的选手送气球。
第二次，给3号座位的选手送气球。
第三次，给7, 9, 10号座位的选手送气球。