题目描述

三分球大赛用字符串记录投篮结果：

• 字符 V：投中，得分增加 $1$；
• 字符 T：未投中但碰到篮框、篮板或篮网，得分不变；
• 字符 X：三不沾。若投篮前的得分不是 $3$ 的倍数，得分减少 $1$；否则得分不变。

有 $Q$ 次询问。每次给出 $L,R,S$，表示初始得分为 $S$，依次完成字符串第 $L$ 个到第 $R$ 个投篮后，最终得分是多少。

输入格式

第一行包含两个整数 $N,Q$。

第二行包含一个长度为 $N$ 的字符串。

接下来 $Q$ 行，每行包含三个整数 $L,R,S$。

输出格式

对于每次询问，输出一行一个整数。

10 5
TTXVXXXVVV
5 9 3
5 8 10
1 5 1
4 8 2
4 8 7

5
10
0
4
7

数据范围与提示

• $1 \le N,Q \le 10^5$
• $1 \le L \le R \le N$
• $0 \le S \le 10^9$