题目背景

星の流れる夜に 星光流动的夜裡
北風が通りを吹き抜け 北风穿越过街道
待ち人から便りはなく 所盼之人音讯全无
明くる日を描くだけ 单单描画翌日之像
星は願いを乗せて 繁星承载祈愿
あの空を静かに散り行き 宁静漫步夜空
——じょん / 初音ミク《メテオ》

题外话：现在你看到的是这个题目修改后的版本，其初始版本不太可做（各种方面），有兴趣的可以看看原先出的 二维版本。

题目描述

现在你坐在观星台的监视屏幕前，这是一个 $n\times n$ 的屏幕，这个屏幕的信号转换算法相当老旧，所以不在整像素点上的流星将被暂时忽略直到它出现在整点上。正是流星雨爆发的时候，你调整屏幕使得流星雨像是瀑布一样向正下飞去。

恰好共有 $n$ 颗流星。为了方便，我们给流星依次标号，并以左下角为原点，将屏幕看作平面直角坐标系的第一象限。对第 $i$ 颗流星，有一个一开始能够被监测到的起点，$(x_i,y_i)$（是整点，此时是第 $0$ 时刻）；也有一个平行于 $y$ 轴且向下做匀速直线运动的速度，用 $(v_i,t_i)$ 表示每 $t_i$ 秒运动 $v_i$ 个像素。此外，我们保证 $x_i=i$。同时每个流星还有一个权值 $a_i$ 表示它的神秘学参数。

繁星承载着祈愿，但同时彗星在古代被称作灾难的象征，为了提前预知，你找来了魔法师来占卜。你为他锁定了 $Q$ 次观星台的镜头，找出可能的灾厄。镜头拍出的画面是一个会调整大小的矩形。为了让他提前准备，你需要确定他至少要对屏幕上的流星施法几次，这和流星的神秘学参数相关，也就是：

• 在某一时刻 $T_j$，确定当前纵坐标在某个区间内，且落在整点上的流星的权值 $a_i$ 的和；

由于法师过来还需要一会儿，所以允许你把问题离线。

输入格式

第一行两个整数 $n,Q$，分别表示流星数量（同时也是屏幕尺寸），和询问次数。

第二行到第 $n+1$ 行，每行四个整数 $y_i,v_i,t_i,a_i$ 表示流星的起始坐标、速度，以及神秘学参数。

接下来 $Q$ 行，每行三个整数 $(T_j,l_j,r_j)$ 表示询问时刻 $T_j$ 时纵坐标在 $[l_j,r_j]$ 内的流星的神秘学权值和。

悬赏：如果有人能发现区间询问的非常好的做法，请告知出题人。（即查询编号在某个区间内的答案）

输出格式

一共 $Q$ 行，每行一个非负整数，表示询问的答案。

5 5
4 3 1 10
4 1 1 8
1 1 2 6
5 0 1 8
3 1 2 10
2 1 3
4 4 4
3 1 5
2 1 2
1 3 4

18
0
16
18
8

提示

以下是数据范围。

对于所有的数据，保证 $n\leq 10^5,Q\leq3\times 10^5$，且 $0\leq v_i<n$，$1\leq t_i,T_j,l_j,r_j\leq n$，以及 $v_i,t_i$ 互质，$1\leq a_i\leq 10^9$。