航空业的新纪元已经到来——首批太阳能巨型喷气式客机即将投入公共旅行使用！然而，这项尖端技术引发了一些安全担忧，因为为这些飞机提供动力的阳光可能会被天空中的其他物体遮挡。因此，必须首先计算一些关于计划中初始航线的统计数据。

我们考虑一组 $N$ 条航线，所有航线都从一个城市向东飞行到另一个城市。飞机可以被视为一个点。它们经过的天空可以建模为笛卡尔平面，其中 $x$ 坐标表示距离一个任意固定点的向东距离，$y$ 坐标表示高度。我们只对 $x$ 坐标在闭区间 $[0, X]$ ($1 \le X \le 10^9$) 内的天空部分感兴趣，在该范围内所有航线均为直线。第 $i$ 架飞机从 $(0, A_i)$ 飞往 $(X, B_i)$ ($1 \le A_i, B_i \le 10^9$)。所有的 $A$ 值各不相同，所有的 $B$ 值也各不相同。飞机沿其航线以未知的、可能不恒定的速度飞行，因此在任何时间点，飞机可能位于其航线上的任何位置。然而，已知飞机之间永远不会相撞，因此如果两条航线交叉，两架飞机不会在同一时间到达交叉点。

飞机还有一个干扰因子：每架飞机 $i$ 都有一个干扰因子 $C_i$ ($1 \le C_i \le 10^9$)，用于衡量飞机 $i$ 对其下方任何飞机的太阳能吸收能力产生多大的负面影响。

每架飞机上的太阳能电池板非常特殊，它们只能收集飞机正上方的能量。这意味着给定飞机所能吸收的阳光可能会被其他占据相同 $x$ 坐标且 $y$ 坐标比它大的飞机遮挡。特别地，它们的效率会根据所有此类飞机的干扰因子之和而降低。

给定这些信息以及一个固定的距离常数 $K$ ($1 \le K \le X$)，你必须回答 $Q$ 个关于飞机太阳能电池板在不同时间可能受到的影响的查询。第 $i$ 个查询询问在飞机 $P_i$ 的 $x$ 坐标处于闭区间 $[S_i, S_i + K]$ ($0 \le S_i \le X - K$) 内的任何时刻，其太阳能电池板可能被遮挡的最大可能数值。

输入格式

第一行包含四个空格分隔的整数：$X$ ($1 \le X \le 10^9$)，要考虑的最大 $x$ 坐标；$K$ ($1 \le K \le X$)，固定的距离常数；$N$ ($1 \le N \le 2000$)，航线数量；$Q$ ($1 \le Q \le 800\,000$)，查询数量。

接下来的 $N$ 行，每行包含三个整数 $A_i, B_i, C_i$ ($i = 1..N$, $1 \le A_i, B_i, C_i \le 10^9$)，分别代表飞机 $i$ 的起始 $y$ 坐标、结束 $y$ 坐标和干扰因子。

接下来的 $Q$ 行，每行包含两个整数 $P_i$ 和 $S_i$ ($i = 1..Q$)，代表关于飞机 $P_i$ 在其 $x$ 坐标处于区间 $[S_i, S_i + K]$ 时的查询。

对于本题 40% 的分数，$Q \le 1000$。

输出格式

输出包含 $Q$ 行，每行一个整数，为第 $i$ 个查询的答案。

样例

样例输入 1

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

样例输出 1

11
6
0

说明

以下是飞机航线的示意图：

第一个查询是针对飞机 2 在 $x$ 坐标闭区间 $[1, 5]$ 内的情况。当该飞机处于 $x$ 坐标小于或等于 4 时，它可能被飞机 3 遮挡，但绝对不会被飞机 1 遮挡。然而，当它处于大于 4 的 $x$ 坐标时，它可能同时被其他两架飞机遮挡。因此，该查询的答案是其他飞机干扰因子之和，即 $5 + 6 = 11$。

对于第二个查询，飞机 1 在其 $x$ 坐标小于 10 时可能被飞机 3 遮挡，而在其 $x$ 坐标大于或等于 10 时不会被任何物体遮挡。因此，它仅可能受到干扰因子为 6 的飞机 3 的干扰。

飞机 1 和飞机 2 都不可能在到达 $x$ 坐标 10 之前直接位于飞机 3 的正上方，因此最后一个查询的答案为 0。