Solar Flight

This problem is adapted from CCO 2015 Day 1 T3 "Solar Flight".

We are entering a new era of aviation – the first giant solar‐powered jet is about to be put into commercial use! However, concerns have been raised about safety because sunlight that powers the plane might be blocked by other objects in the sky. In order to plan the inaugural flight, some statistics and computations are needed.

Consider a set of N flight paths connecting two cities. Each airplane is modeled as a moving point and its flight path (over the sky) is a straight line. In our Cartesian coordinate system the X–axis represents the horizontal (eastward) distance and the Y–axis represents altitude. We only consider the part where x lies in the interval [0, X]. The i^th flight goes from (0, A_i) to (X, B_i). All the A_i values are distinct, and so are all the B_i values. Although the speeds along these paths are unknown and may even be non‐constant (so each plane can be anywhere along its flight path at any given time), it is known that no two airplanes ever collide. In particular, if two flight paths cross then the corresponding airplanes will not be at the intersection at the same time.

Each plane i also has an interference factor C_i which quantifies how much it interferes with the solar energy collected by a plane flying underneath.

The solar panels on these planes are very peculiar – they only harvest energy from directly above. This means that the amount of sunlight a plane absorbs is reduced by the total interference factors of only those airplanes that are exactly above it (i.e. vertically aligned with it and at a higher altitude). (Note that two airplanes can be arranged to be vertically aligned by choosing appropriate positions along their flight paths.)

You are given an additional distance constant K and asked to answer Q queries. The i^th query asks for the maximum possible reduction in sunlight on the solar panels of plane P_i at some moment in time, under the guarantee that at that moment every airplane’s x–coordinate lies in the interval [S_i, S_i+K].

---

Mathematical Formulation

For each airplane i its altitude at a horizontal coordinate x (with 0 ≤ x ≤ X) is given by

$$f_i(x)=A_i+\frac{B_i-A_i}{X}x.$$

For a fixed plane P (with parameters A_P, B_P) and any other plane j, define the difference

$$f_j(x)-f_P(x)=(A_j-A_P)+\frac{(B_j-A_j)-(B_P-A_P)}{X}x. $$

Since we are allowed to choose the x–positions for each plane arbitrarily in the interval [S, S+K] (subject to lying on their flight paths), we can arrange for some planes to be exactly vertically above plane P if at the chosen common x value the inequality f_j(x) > f_P(x) holds. In that case, plane j will block plane P contributing an interference of C_j.

Thus, for any chosen x in [S, S+K], the total reduction for plane P is

$$F(x)=\sum_{j\neq P} \mathbf{1}_{\{f_j(x)>f_P(x)\}}\,C_j. $$

Your goal is to compute, for each query,

$$\max_{x\in[S,S+K]} F(x).$$

---

Notes

• The linear functions are such that the values of A_i (at x=0) and B_i (at x=X) are all distinct.
• For any pair of planes whose flight paths cross, it is possible to choose x so that one of them is exactly above the other.
• Your answer for each query should be the maximum possible total interference (i.e. the sum of the appropriate C values) that can block plane P by selecting an optimal x in the given window.

inputFormat

The first line of input contains four integers N, X, K and Q, where N (1 ≤ N ≤ 10⁵) is the number of flights, X (1 ≤ X ≤ 10⁹) is the total horizontal distance, K (0 ≤ K ≤ X) is the window length, and Q is the number of queries.

The next N lines each contain three integers A_i, B_i and C_i (1 ≤ A_i, B_i, C_i ≤ 10⁹), representing that the i^th flight starts at (0, A_i) and ends at (X, B_i) with interference factor C_i. It is guaranteed that all A_i values are distinct and all B_i values are distinct.

The following Q lines each contain two integers P_i and S_i (1 ≤ P_i ≤ N and 0 ≤ S_i ≤ S_i+K ≤ X), representing a query for flight P_i when all airplanes have their x–coordinates in the interval [S_i, S_i+K].

outputFormat

For each query, output a single line containing one integer – the maximum possible reduction in solar energy (i.e. the sum of interference factors from those planes that can be arranged to be directly above the queried plane).

sample

3 10 5 3
1 5 10
2 6 20
3 4 30
1 0
2 2
3 5

50
30
30