题目描述

学校的篮球队组织队员们参加学校的三分球大赛。

大赛计分规则如下：

• 选手投中一个三分球，加 $1$ 分。
• 选手没投中，但球碰到了篮框、篮板或篮网，则既不得分也不扣分。
• 选手投球啥也没碰到（俗称三不沾），则倒扣 $1$ 分。

为了让比赛有更多的趣味性，比赛添加了一个新的规则：如果某选手投了三不沾，但当前的分数恰好是 $3$ 的倍数，那么本次投篮不扣分。

现给出一个仅包含字符 V、T、X 的字符串，其中 V 表示投中，T 表示没投中但碰到了篮框、篮板或者篮网，X 表示三不沾。

再给出 $Q$ 次询问，每次询问会给出三个整数 $L, R, S$ 表示某选手已经得到了 $S$ 分，如果其接下来的投篮成绩是给定字符串中 $[L,R]$ 中的字符，那么该选手的最终成绩是多少分？

输入格式

第 $1$ 行读入整数 $N, Q$ ，分别表示字符串的长度和询问的数量。
第 $2$ 行读入一个长度为 $N$ 的字符串。
接下来 $Q$ 行，每行读入三个整数 $L, R, S$ 。

输出格式

输出 $Q$ 行，代表对于每次询问的计算结果。

样例

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

5
10
0
4
7

20 6
VTTVTXTVTVXTTXXXXXXX
5 16 9
1 15 8
7 13 5
6 9 1
8 19 7
8 19 3

9
9
6
1
9
3

20 10
TXXTXTXTXVVXVVVTXTTX
13 18 3
4 12 0
1 6 6
2 19 10
13 14 3
4 10 2
3 6 4
1 17 2
8 15 9
3 10 10

6
1
6
12
5
1
3
3
13
10

数据范围与提示

• 对于 $50\%$ 的数据，$N, Q \leq 1000$。
• 对于 $100\%$ 的数据，$N, Q \leq 10^5$，$1 \leq L \leq R \leq N$，$0 \leq S \leq 10^9$。