I. Hile and Array
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

给定一个长为 $$$n$$$ 的操作序列，第 $$$i$$$ 个位置有 $$$op_{i},w_{i}$$$ 代表 加/减/乘 一个数 $$$w_{i}$$$ ，一共有 $$$q$$$ 次询问，每次询问给定三个整数 $$$x,l,r$$$ ，求初始值为 $$$x$$$ 时，依次经过位置 $$$l$$$ 到位置 $$$r$$$ 共 $$$r-l+1$$$ 个运算操作后得到的结果，考虑到这个数可能很大，请对 $$$1000000007$$$ 取模。

注意：在本题中，所有操作都是按照先后顺序严格依次序执行的；换言之，靠前的加减法操作比靠后的乘法操作拥有更高的运算优先级。

Input

输入第一行包含一个正整数 $$$T$$$ $$$(1\le{T}\le{10^4})$$$ ，代表测试组数。

对于每组测试用例，输入第一行包含一个正整数 $$$n$$$ $$$(1\le{n}\le{10^5})$$$ ，代表操作序列长度。

随后 $$$n$$$ 行每行包含两个正整数 $$$op_i,w_i$$$ $$$(1\le{op_i}\le{3},1\le{w_i}\le{10^9})$$$，其中 $$$op_i=1$$$ 代表操作为加法，$$$op_i=2$$$ 代表操作为减法，$$$op_i=3$$$ 代表操作为乘法。

第 $$$n+2$$$ 行包含一个正整数 $$$q$$$ ，代表询问次数。

随后 $$$q$$$ 行每行包含三个正整数 $$$x,l,r$$$ $$$(1\le{x}\le{10^9},1\le{l}\le{r}\le{n})$$$ 。

确保 $$$\sum n\le{10^5}$$$ 。

Output

对于每组测试用例，输出 $$$q$$$ 行代表 $$$x$$$ 在操作后对 $$$1000000007$$$ 取模的结果。

Example
Input
1
6
1 1
2 1
3 4
1 5
2 1
3 4
2
1 1 6
100 3 4
Output
32
405