Putata 最近沉迷于玩《黄金矿工》。游戏设定在一个二维平面上，地图中包含 $n$ 个金矿，第 $i$ 个金矿位于 $(x_i, y_i)$，其中 $y_i < 0$。

玩家位于地面上的点 $(p, 0)$。每一关都有一个目标 $k$，表示为了通关必须收集的金矿数量。由于特殊的地质特性，当玩家与金矿之间的欧几里得距离为 $s$ 时，拉动金矿所需的力为 $2 \cdot s$。收集金矿所需的能量等于将金矿拉到玩家位置所需的功$^\dagger$。Putata 将采取最优策略来通关，同时最小化总能量消耗。

现在，Budada 设计了 $q$ 个随机关卡。对于第 $i$ 个关卡，玩家的位置 $p$ 是从区间 $[a_i, b_i]$ 中均匀随机生成的实数，且所需的金矿数量为 $k_i$。你的任务是帮助 Putata 计算每个随机关卡所需的最小总能量的期望值，对 $10^9 + 7$ 取模。

可以证明答案可以表示为一个不可约分数 $\frac{x}{y}$，其中 $x$ 和 $y$ 为整数且 $y \not\equiv 0 \pmod{10^9 + 7}$。输出等于 $x \cdot y^{-1} \pmod{10^9 + 7}$ 的整数。换句话说，输出一个整数 $a$，满足 $0 \le a < 10^9 + 7$ 且 $a \cdot y \equiv x \pmod{10^9 + 7}$。

$\dagger$：在科学中，功是力沿位移方向对物体所做的能量转移。当力是变量时，功由线积分给出：$W = \int \mathbf{F} \cdot d\mathbf{s}$。将距离为 $s$ 的金矿拉回所做的功等于 $\int_0^s 2x \, dx = s^2$。

输入格式

第一行包含两个整数 $n, q$ ($1 \le n \le 2000, 1 \le q \le 5 \cdot 10^5$)，分别表示金矿的数量和关卡的数量。

接下来的 $n$ 行，第 $i$ 行包含两个整数 $x_i, y_i$ ($0 \le x_i \le 10^9, -10^9 \le y_i < 0$)，表示第 $i$ 个金矿的坐标。

接下来的 $q$ 行，第 $i$ 行包含三个整数 $a_i, b_i, k_i$ ($0 \le a_i \le b_i \le 10^9, 1 \le k_i \le n$)，表示一个关卡。

输出格式

输出 $q$ 行，第 $i$ 行包含第 $i$ 个关卡的答案。

样例

样例输入 1

4 4
1 -2
4 -1
4 -3
5 -2
2 3 1
0 6 4
3 4 2
4 7 2

样例输出 1

333333339
40
666666679
9

样例输入 2

6 10
7 -5
2 -7
2 -7
5 -3
9 -4
5 -3
2 4 1
2 10 2
5 8 3
3 9 1
5 8 5
1 2 4
4 5 3
7 10 6
3 8 3
2 9 2

样例输出 2

333333349
846354201
625000051
406250015
143
333333477
50
273
575000054
443452410

说明

对于第一个样例，四个查询的答案分别为 $\frac{10}{3}, 40, \frac{23}{3}, 9$。