暂无测试数据。

题目描述

在藏宝室外，
探险家詹·邦发现了一道谜题，
如果解开这道谜题就可以进入藏宝室内取走宝藏了。

在大门上有一行整数 (\(|x| \leq 100\))，
在它下面有一行字，
与上面的整数一一对应，
表示这个数字是由哪一个建造者写下的。
再往下还有一些空位。
经过仔细研究，
探险家发现了解开这个谜题的方法：
这座藏宝室是由 3 名建造者建的，
他们 3 人共同设计了这道谜题。
他们的名字分别是 Alice、Bob 和 Cathy。
下面的空位里可以放入一个特殊的机械装置，
这个机械装置可以设定为表示一个特定的数字。

每一个空位都是由一个建造者设计的，
里面要求填的数字是：
从第 L 到第 R 个整数中，
由当前建造者写下的数字之和。（从 1 开始数。）

现在请你帮助探险家詹·邦，找出每一个空位需要放入的机械装置要设定成多少。

输入

第 1 行:两个正整数 \(n\) 和 \(Q\) 表示数字个数和空位个数。

第 2 行：n个数字，它们的绝对值不大于100。

第 3 行：n个字符串，只可能是Alice、Bob、Cathy中的一种。

第 \(4 \sim n+3\)行：每一行首先是一个字符串，表示建造者的名字，然后是两个正整数 L,R，表示范围。

输出

每行一个数，表示每个空位要填的数字。

样例输入

7 3
3 -1 8 5 -2 4 6
Alice Alice Bob Cathy Bob Alice Cathy
Alice 1 7
Bob 2 3
Cathy 2 5

样例输出

6
8
5

数据范围限制

\(1 \leq n,q \leq 100\),\(|x| \leq 100\)

来源

基础篇补充3.3