Imagine a picturesque landscape made up of various ridges stretching across an ~xy~-plane. The ~x~-axis of the plane extends from ~0~ to ~M~, while the ~y~-axis extends from ~-\infty~ to ~\infty~. There are ~N~ ridges numbered from ~1~ to ~N~. The ~i~-th ridge can be represented as a line segment connecting ~(0, a_i)~ and ~(M, b_i)~, with an aesthetic value of ~v_i~.

For an interval ~[l,r]~, the goodness of the landscape from ridge ~k~ refers the sum of the aesthetic values of other ridges that are ever strictly above the height of ridge ~k~ within ~[l,r]~.

A person is planning to explore the landscape, and has a few questions. In the ~i~-th question, they wonder what the goodness of landscape ~p_i~ is over the interval ~[s_i,s_i+K]~. Note that ~K~ is the same for each query.

Constraints

For all subtasks:

~1 \le N \le 5 \times 10^3~

~1 \le K \le M \le 10^9~

~1 \le Q \le 5 \times 10^5~

~-10^9 \le a_i, b_i \le 10^9~

~1 \le v_i \le 10^9~

~1 \le p_i \le N~

~0 \le s_i \le M - K~

Subtask 1 [30%]

~1 \le Q \le 5 \times 10^3~

Subtask 2 [70%]

No additional constraints.

Input Specification

The first line contains four space-separated integers ~N~, ~M~, ~Q~, and ~K~.

The ~i~-th of the following ~N~ lines each contain three space-separated integers ~a_i~, ~b_i~, and ~v_i~.

The ~i~-th of the following ~Q~ lines each contain two space-separated integers ~p_i~ and ~s_i~.

Output Specification

For each query, output an integer, representing the goodness of the landscape.

Sample Input

3 15 2 7
6 9 3
2 11 2
10 1 1
1 3
1 4

Sample Output

1
3

Sample Explanation

For the first query, only ridge ~3~ is ever strictly above ridge ~1~ in the interval ~[3,10]~, so the answer is ~1~.

For the second query, both ridge ~2~ and ridge ~3~ are ever strictly above ridge ~1~ at some point in the interval ~[4,11]~, so the answer is ~1+2=3~.