题目描述

小 T 即将从 TeaLand 小学毕业！现在他正在进行期末考试，并且被最后一道题卡住了。

这道题是这样说的：给出 $\red{n}$ 个线性函数 $\red{f_1,f_2,f_3,\dots,f_n}$，求出 $\red{f_r(f_{r-1}(f_{r-2}(\dots f_l(x))))}$ 的值。

很显然，只需要从后往前求出每一个值后再继续计算就可以了，但是 TeaLand 位于充满魔法与奇迹的世界上，所以试卷上的 $\red{l,r,x}$ 都会随着时间变化，不过好在 $\red{f_i}$ 不会变化！

你能帮帮小 T 吗？

说人话：给出 $\red n$ 个线性函数 $\red{f_i(x)=k_ix+b_i}$，有 $\red m$ 次询问，求出从 $\red l$ 到 $\red r$ 依次计算 $\red{f_i(x)}$ 的结果，其中 $\red{i>l}$ 时 $\red x$ 是 $\red{f_{i-1}}$ 的结果 ，否则为给定的参数 $\red x$。

输入格式

第一行两个正整数 $\red{n,m}$。

之后 $\red n$ 行，每行两个整数 $\red{k_i,b_i}$，表示初始时的一个线性函数 $\red{f_i}$。

之后 $\red m$ 行，每行三个整数 $\red{l,r,x}$，表示一个询问。

输出格式

假设第 $\red i$ 次询问的答案是 $\red{A_i}$，由于答案非常大，所有首先将 $\red{A_i}$ 对 $\red{10^9+7}$ 取模，由于询问量也非常大，所以你只需要输出所有 $\red{A_i}$ 的异或即可。

即：如果 $\red{m=3}$ 而你的答案分别是 $\red{\{10^9+8, 2, 3\}}$，那么你应该输出一行一个整数 $\red 0$，因为 $\red{10^9+8\bmod10^9+7=1}$，$\red{1\texttt{ xor }2\texttt{ xor }3=0}$。

样例

输入样例

3 4
1 2
3 4
5 6
1 1 1
2 2 1
3 3 1
1 3 2

输出样例

89

提示

对于 $\red{30\%}$ 的数据，保证 $\red{n,m\le10^3}$。

对于另外 $\red{10\%}$ 的数据，保证 $\red{l=1}$。

对于另外 $\red{30\%}$ 的数据，保证 $\red{n,m\le10^5}$。

对于所有的数据，保证 $\red{1\le n,m\le2\times10^6}$，$\red{1\le k_i\,b_i,x\le 10^9}$，$\red{1\le l\le r\le n}$，$\red{1\le i\le n}$。

由于输入数据量非常大，你可能需要如下的快速读入：

// Here we don't need long long because the input data never greater than 1e9
int read() {
    int x = 0; char ch = 0;
    while(ch < '0' || ch > '9') ch = getchar();
    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    return x;
}