题目描述

学校的篮球队组织队员们参加三分球大赛，大赛计分规则如下：

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

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

现给出一个仅包含字符V、T、X的字符串，其中：

• V表示投中
• T表示没投中，但碰到了篮框、篮板或者篮网
• X表示三不沾

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

输入格式

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

输出格式

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

样例输入1

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

样例输出1

5
10
0
4
7

样例输入2

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

样例输出2

9
9
6
1
9
3

样例输入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

样例输出3

6
1
6
12
5
1
3
3
13
10

数据范围

• 对于50%的数据，N、Q ≤ 1000。
• 对于100%的数据，N、Q ≤ 1e5，1 ≤ L ≤ R ≤ N，0 ≤ S ≤ 1e9。