#P18179. Cosmic Travel
Cosmic Travel
Cosmic Travel
BaoBao 是一名宇宙旅行者,可以在无穷多个平行宇宙之间穿梭。这些宇宙从 开始,用整数编号。
每个宇宙中都有 个魔法苹果。第 个宇宙中,第 个苹果的魔力为
其中 表示按位异或。
BaoBao 准备了 个旅行计划。每个计划由三个整数 描述:他会访问编号为 的每一个宇宙,并在每个宇宙中收集魔力第 小的苹果。
对每个计划,求收集到的苹果的魔力之和,对 取模。
每个计划相互独立,不会真的从任何宇宙中删除苹果。苹果按个数参与排名,魔力相同的苹果仍分别计算。
输入格式
每个输入文件只有一组数据。
第一行两个整数 ,分别表示每个宇宙中的苹果数和旅行计划数。
第二行 个整数 。
接下来 行,每行三个整数 ,表示一个计划。
输出格式
输出 行,每行一个整数,表示对应计划的答案对 取模的结果。
数据范围
- ;
- ;
- ;
- 。
样例输入
8 3
2 0 2 4 0 5 2 6
1 1 6
2 7 5
0 1048575 4
样例输出
4
23
720895450