题目描述

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

大赛计分规则如下：

• 选手投中一个三分球，加 $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$ 行，代表对于每次询问的计算结果。

样例 #1

输入

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

输出

5
10
0
4
7

数据范围

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