最近在 Bajtocja，一款名为 Potyczki Survival Shooter 的手机游戏非常流行。在这款游戏中，我们控制一支沿着直线路径行进的战士小队。小队会不时遇到事件。在第 $i$ 个事件中，玩家有两个选择：走道路左侧，获得 $a_i$ 名额外战士；或者走道路右侧，将当前战士数量乘以 $b_i$。尽管大家都知道战士越多越好，但游戏广告清楚地表明，做出正确的决定往往非常复杂。

Bajtazar 在前 $l$ 个事件后拥有 $x$ 名战士。（数字 $x$ 不一定是通过上述规则在前 $l$ 个事件中可能得到的——毕竟他们是战士而不是游客，弱小的玩家可能会在与僵尸的战斗中损失一部分战士，本题不描述其规则。）他想知道，如果他采取最优策略，在第 $r$ 个事件之后他将拥有多少名战士。请帮他计算一下！

输入格式

第一行包含两个整数 $n$ 和 $q$ ($1 \le n \le 500\,000$, $1 \le q \le 100\,000$)。

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

接下来的 $q$ 行包含查询的描述；第 $i$ 行包含三个整数 $x_i$, $l_i$ 和 $r_i$ ($0 \le x_i < 10^9 + 7$, $0 \le l_i < r_i \le n$)。

输出格式

对于每个查询，输出一个数字，即采取最优策略后的战士数量。结果请对 $10^9 + 7$ 取模。

样例

输入 1

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

输出 1

16
49

说明 1

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