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 $-\mathrm{\infty }$ to $\mathrm{\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$.