题目描述

本题原题时限15s，由于系统限制，现单点时限暂时设置为10s，请知悉。

本题译自 CCO 2015 Day1 T3「Solar Flight」

航空的新纪元正在来临——第一个太阳能驱动的巨型喷气式飞机即将商用！然而，公众对前沿技术有一些在安全方面的焦虑，因为驱动飞机的阳光的光线可能会被其他在空中的物体挡住。因此，必须先进行一些统计和计算来规划第一次航行。

我们考虑一个包含 $N$ 个从一个城市到另外一个城市的航路组成的图。一架飞机可以被考虑成一个点。它穿过的天空可以被模型化为一个笛卡尔坐标系，其中 $X$ 轴表示从任意一个点向东出发的距离，$Y$ 轴表示高度。我们只考虑 $x$ 值的范围在 $[0,X]$，所有航路均为直线的部分。第 $i$ 架飞机从 $(0,A_i)$ 飞到 $(X,B_i)$。所有$A$值互不相同，对于$B$也如此。飞机以未知的，可能是非恒定的速度沿着航路行驶，所以任意时间点，飞机可能在航路的任意位置上。然而，已知的是飞机从不与其他飞机相撞，所以如果两个航道交错，两个飞机不会同时到达交点。

每个飞机 $i$ 同时也有一个干扰因素值 $C_i$，表示一个飞机影响它下面飞机太阳吸收能力的强弱。

各个飞机上的太阳能板非常奇怪，那些太阳能板只能收集飞机正上方的能量。这就意味着一个飞机能吸收的阳光可能会被其他与其的 $x$ 值相同，但是 $y$ 值比他大的飞机挡住。具体来说，太阳能板吸收的太阳光减少的值为挡住它的飞机的干扰因素值之和。

根据这些信息，以及一个距离常数 $K$，你要回答 $Q$ 个关于可能对太阳能板影响的询问。第 $i$ 个询问询问你在一个时刻飞机 $P_i$ 的太阳能板吸收的太阳光减少的值。在任意时刻飞机的 $x$ 值均在 $[S_i,S_i+K]$之间。

输入格式

第一行四个整数 $X,K,N,Q$，分别表示最大考虑的 $x$ 值，距离常数，航路总数，询问总数。

接下来 $N$ 行每行三个整数 $A_i,B_i,C_i(1\le i \le N)$，表示飞机 $i$ 初始 $y$ 值，终止 $y$值，干扰因素值。

接下来 $Q$ 行每行两个整数，$P_i, S_i(1\le i \le Q)$，表示根据 $P_i$ 和 $S_i$ 回答题目中的问题。

输出格式

输出 $Q$ 行，每行一个整数表示对于询问 $i(1\le i \le Q)$ 的回答。

样例

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

11
6
0

飞机的航路示意图如下图所示。

询问 $1$ 是对于 $2$ 号飞机在 $[1,5]$ 范围内所提出的询问，当飞机在 $x\le 4$ 时可能会被飞机 $3$ 挡住，但是绝不是飞机 $1$。然而，但是当它的 $x>4$ 时可能会被其他所有飞机挡住，因此，该询问的答案即其他所有飞机的影响因素值之和，为 $5+6=11$。

对于询问 $2$，当 $x<10$ 时飞机 $1$ 可能会被飞机 $3$ 挡住，并且当 $x\geq10$ 时不会被任何飞机盖住，因此只可能被飞机 $3$ 影响，即结果等于飞机 $3$ 的影响因素值 $6$。

对于询问 $3$，飞机 $1,2$ 都不能在飞机 $3$ 的正上方除非 $x$ 达到 $10$。所以该询问的答案为0。

数据范围与提示

对于 $40\%$ 的数据，$1\le Q\le 1000$；

对于 $100\%$ 的数据，$1\le N\le 2000,$ $1\le K\le X,$ $1\le X,A_i,B_i,C_i\le 10^9,$ $0\le S_i\le X-K,$ $1\le Q \le 800000$。