태양광 비행

새로운 항공 시대가 열렸다. 최초의 태양광 점보 제트기가 곧 일반 승객을 태우고 운항을 시작한다. 그런데 이 비행기에 동력을 공급하는 햇빛은 하늘에 있는 다른 물체에 가려질 수 있어서 안전 문제가 제기되었다. 그래서 첫 운항 계획에 관한 몇 가지 통계를 먼저 계산해야 한다.

$N$개의 비행 경로가 있고, 모두 한 도시에서 다른 도시로 동쪽을 향해 날아간다. 비행기는 하나의 점으로 생각한다. 하늘은 좌표평면으로 나타내며, x좌표는 임의로 정한 기준점에서 동쪽으로 떨어진 거리이고 y좌표는 고도이다. 관심 있는 부분은 x좌표가 닫힌구간 $[0, X]$ 안에 있는 하늘뿐이고, 이 구간에서 모든 비행 경로는 직선이다. $i$번째 비행기는 $(0, A_i)$에서 $(X, B_i)$로 날아간다. $A$ 값은 모두 서로 다르고, $B$ 값도 모두 서로 다르다. 비행기는 경로를 따라 알 수 없는 속도로 날아가며 속도가 일정하지 않을 수도 있다. 따라서 어느 시각에든 비행기는 자기 경로 위 어디에나 있을 수 있다. 다만 비행기끼리 충돌하는 일은 없다. 두 비행 경로가 교차하더라도 두 비행기가 교차점에 정확히 같은 시각에 도착하지는 않는다.

각 비행기 $i$에는 간섭 계수 $C_i$가 있다. 이 값은 비행기 $i$가 자기보다 아래에 있는 비행기의 태양광 흡수 능력을 얼마나 떨어뜨리는지 나타낸다.

비행기의 태양광 패널은 조금 특이해서 바로 위에서 오는 빛만 모은다. 그래서 어떤 비행기가 받는 햇빛은 그 비행기와 같은 x좌표에 있고 y좌표가 더 큰 다른 비행기에 가려진다. 이때 패널이 가려지는 정도는 그런 비행기 모두의 간섭 계수를 더한 값이다.

고정된 거리 상수 $K$가 주어질 때, 질의 $Q$개에 답해야 한다. $i$번째 질의는 비행기 $P_i$의 x좌표가 닫힌구간 $[S_i, S_i + K]$ 안에 있는 동안, 어느 한 순간에 비행기 $P_i$의 태양광 패널이 가려질 수 있는 정도의 최댓값을 묻는다.

첫째 줄에 네 정수 $X$, $K$, $N$, $Q$가 공백으로 구분되어 주어진다. $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 800000$)는 질의의 수이다.

다음 $N$개의 줄 가운데 $i$번째 줄에는 세 정수 $A_i$, $B_i$, $C_i$ ($1 \le A_i, B_i, C_i \le 10^9$)가 주어진다. 차례대로 비행기 $i$의 출발 y좌표, 도착 y좌표, 간섭 계수이다.

다음 $Q$개의 줄 가운데 $i$번째 줄에는 두 정수 $P_i$, $S_i$ ($1 \le P_i \le N$, $0 \le S_i \le X - K$)가 주어진다. 비행기 $P_i$의 x좌표가 구간 $[S_i, S_i + K]$ 안에 있는 동안에 관한 질의이다.

$Q$개의 줄을 출력한다. $i$번째 줄에는 $i$번째 질의의 답을 정수로 출력한다.