#P6985. [2019年余姚中学集训]Radio Ga Ga
[2019年余姚中学集训]Radio Ga Ga
Radio Ga Ga
题目描述
Roger是个长得有点帅的鼓手,"Radio Ga Ga"就是他为Queen所作的词曲作品。
Roger想起来了儿时躺在家中听着收音机的日子,为了记下那些日子,作为一个高智商的(牙医)鼓手,他决定用自己喜欢的架子鼓来做点有意思的事情。
Roger一共有 个架子鼓(如果要问他为什么能弹 个鼓,那可能是因为他比较帅吧),排成一排,编号 。
他先选择第 个鼓。此后,假设已经打过的鼓恰为区间 ,下一次可以选择:
- 若 ,打第 个鼓;
- 若 ,打第 个鼓。
直到所有鼓都打过才结束。
有 条特殊情况。第 条为:如果第 次打的是第 个鼓,获得 点愉悦值。总愉悦值为所有满足情况的 之和。
有 个独立询问,每次指定起始鼓 ,求能够获得的最大总愉悦值。答案对 取模后输出。
两种打鼓顺序 不同,当且仅当存在 使得 。
输入格式
从标准输入读入。第一行三个整数 。
接下来 行,每行三个整数 ,表示一条特殊情况。
接下来 行,每行一个整数 。
输出格式
向标准输出写出 行,每行一个整数,表示该次询问的最大总愉悦值对 取模的结果。
样例输入1
7 7 7
1 7 3
1 3 80
4 1 9
4 5 83
2 2 28
2 1 26
5 2 92
1
2
3
4
5
6
7
样例输出1
28
83
191
92
92
92
3
数据范围
采用捆绑测试。所有数据满足 ,,,。
不存在两条特殊情况满足 且 。
| 子任务 | 分数 | 特殊限制 |
|---|---|---|
| 1 | 10 | |
| 2 | 20 | |
| 3 | 10 | |
| 4 | 20 | |
| 5 | ||
| 6 | 无额外限制 |