Solar Flight

A new era of aviation has arrived: the first solar-powered jumbo jets are about to open for public travel. The sunlight that powers these planes can be blocked by other objects in the sky, which raises some safety concerns. So some statistics about the planned initial flights must be calculated first.

Consider $N$ flight paths, all travelling east from one city to another. Treat each plane as a single point. Model the sky as a Cartesian plane, where the x-coordinate is the distance east of an arbitrary fixed point and the y-coordinate is the altitude. Only the part of the sky with x-coordinates in the closed range $[0, X]$ matters, and every flight path is a straight line there. Plane $i$ flies from $(0, A_i)$ to $(X, B_i)$. All $A$ values are distinct, and all $B$ values are distinct. The planes travel along their paths at unknown, possibly non-constant speeds, so at any moment a plane can be anywhere along its path. The planes never crash into each other, though: if two flight paths cross, the two planes do not reach the intersection point at exactly the same time.

Each plane $i$ has an interference factor $C_i$, which measures how much plane $i$ reduces the solar absorbing capability of any plane below it.

The solar panels on each plane are unusual: they collect energy only from directly above the plane. So the sunlight a plane absorbs can be blocked by other planes that are at the same x-coordinate and have a larger y-coordinate. The amount by which its panels are obstructed is the sum of the interference factors of all such planes.

Given a fixed distance constant $K$, answer $Q$ queries. Query $i$ asks for the largest possible amount by which the solar panels of plane $P_i$ could be obstructed at a single moment, at any point while the x-coordinate of plane $P_i$ is in the closed range $[S_i, S_i + K]$.

The first line contains four space-separated integers $X$, $K$, $N$, and $Q$: $X$ ($1 \le X \le 10^9$) is the maximum x-coordinate to consider, $K$ ($1 \le K \le X$) is the fixed distance constant, $N$ ($1 \le N \le 2000$) is the number of flight paths, and $Q$ ($1 \le Q \le 800000$) is the number of queries.

Line $i$ of the next $N$ lines contains three integers $A_i$, $B_i$, and $C_i$ ($1 \le A_i, B_i, C_i \le 10^9$): the starting y-coordinate, the ending y-coordinate, and the interference factor of plane $i$.

Line $i$ of the next $Q$ lines contains two integers $P_i$ and $S_i$ ($1 \le P_i \le N$, $0 \le S_i \le X - K$), a query about plane $P_i$ while its x-coordinate is in the range $[S_i, S_i + K]$.

Print $Q$ lines. Line $i$ contains the integer answer to query $i$.