题目描述

最近在 Bajtocja，一款名为 Potyczki Survival Shooter 的手机游戏非常流行。在这款游戏中，我们操控一支沿着笔直路线行进的战士队伍。每隔一段时间，队伍就会遇到一个事件。在第 $i$ 个事件中，玩家有两个选项可供选择：走道路左侧，获得 $a_i$ 名额外战士；或者走道路右侧，将当前战士数量乘以 $b_i$。尽管所有人都知道战士越多越好，但游戏的广告明确表明，做出正确的决策有时会非常复杂。

Bajtazar 在经历前 $l$ 个事件后拥有 $x$ 名战士。（数字 $x$ 不一定是按照上述规则从前 $l$ 个事件中可以得到的——毕竟这些是战士，而不是游客，差劲的玩家可能会在与僵尸的战斗中损失一部分，而这部分规则在本题中不作描述。）他想知道，如果他以最优策略进行游戏，在第 $r$ 号事件之后他会拥有多少名战士。请帮助他计算！

输入格式

输入的第一行包含整数 $n$ 和 $q$（$1 \leq n \leq 500\,000$，$1 \leq q \leq 100\,000$）。

接下来的 $n$ 行包含事件描述；其中第 $i$ 行包含两个整数 $a_i$ 和 $b_i$（$0 \leq a_i \leq 10^9 + 7$，$1 \leq b_i \leq 10^9 + 7$）。

接下来的 $q$ 行包含查询描述；其中第 $i$ 行包含三个整数 $x_i$、$l_i$ 和 $r_i$（$0 \leq x_i \leq 10^9 + 7$，$0 \leq l_i \leq 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$ 名战士。