[AdditionalFile5677.zip](file://AdditionalFile5677.zip?type=additional_file)

#5677. 「PA 2026」Gra Mobilna

标签: 传统 | 时间限制: 1000 ms | 内存限制: 1024 MiB |

题目描述

题目译自 PA 2026 Runda 1 Gra Mobilna

最近在 Bajtocja 中，一款名为《Potyczki Survival Shooter》的手机游戏非常流行。在游戏中，我们控制着一支在一条直线上行进的战士部队。队伍会不时遇到各种事件。在第 $i$ 次事件中，玩家有两个选择：走道路的左侧，获得 $a_{i}$ 名额外战士；或者走道路的右侧，将当前战士数量乘以 $b_{i}$。尽管大家都知道战士越多越好，但游戏广告明确表明，做出正确的决策有时非常复杂。

Bajtazar 在经历了前 $l$ 次事件后拥有 $x$ 名战士。（$x$ 的值不一定能通过上述规则从前 $l$ 次事件中推导出来的。毕竟他们是战士而不是游客，技术较差的玩家可能会在与僵尸的战斗中损失部分战士，这些损失规则在本题中不做描述。）他想知道，如果他进行最优操作，在第 $r$ 次事件后他将拥有多少名战士。请帮他计算！

输入格式

第一行输入包含整数 $n$ 和 $q$ $(1 \leq n \leq 500000, 1 \leq q \leq 100000)$。

接下来的 $n$ 行包含事件描述；第 $i$ 行包含两个整数 $a_{i}$ 和 $b_{i}$ $(0 \leq a_{i} < 10^{9}+7, 1 \leq b_{i} < 10^{9}+7)$。

接下来的 $q$ 行包含查询描述；第 $i$ 行包含三个整数 $x_{i}, l_{i}$ 和 $r_{i}$ $(0 \leq x_{i} < 10^{9}+7, 0 \leq l_{i} < r_{i} \leq n)$。

输出格式

对于每个查询，输出一个数字表示采用最优策略时的战士数量。输出结果需对 $10^{9}+7$ 取模。

样例

输入

10 2
3 2
3 2
3 2
0 1000
0 1000
0 1000
0 1000
0 1000
0 1000
123 1
1 0 3
1 3 9

输出

16
49

在第一个查询中，Bajtazar 开始时有 $1$ 名战士。在第一次事件中，他可以选择获得 $3$ 名额外战士，或者将战士数量乘以 $2$。为了达到最优策略，他会选择前者，从而拥有 $4$ 名战士。接下来的两次事件相同，但这次加倍战士数量更划算。最终，Bajtazar 将拥有 $16$ 名战士。