기차 지연 | cho.sh

문제

IOI 도시는 세계에서 가장 인구가 많고 바쁜 도시이다. 일반적으로 하루는 $86 \ 400$초이지만, IOI 도시에서는 시간의 단위 '쵸'를 정의하여 하루를 무려 $10^{12}$쵸로 세분화하여 사용한다. 하루의 시작을 $0$쵸로 정의하고, 실수 $t(0 \leq t < 10^{12})$에 대하여 $0$쵸에서 $t$쵸가 지난 뒤의 시각을 $t$쵸로 정의한다. $10^{12}-1$쵸에서 $1$쵸가 지나면 다음날 $0$쵸가 된다.

IOI 도시는 교통량이 어마어마하기 때문에, IOI 도시의 기차역에서는 매일 $10^{12}$ 개의 기차가 출발한다. $10^{12}$개의 기차는 $0$부터 $10^{12} - 1$ 까지의 정수 번호가 붙어 있으며, $i (0 \leq i \leq 10^{12} - 1)$번 기차는 $i$쵸에 출발하기로 예정되어 있다.

IOI 도시의 기차역에서는 많은 기차의 탑승 정보를 표시하기 위해 $10^{12}$개의 행이 있는 거대한 전광판을 가지고 있다. 전광판의 $10^{12}$개의 행에는 $0$부터 $10^{12}-1$까지의 번호가 붙어 있다. 그날 출발하기로 예정되어 있던 기차 중 아직 출발하지 않은 기차가 $M$개라고 할 때, 전광판의 $0$번 행부터 $M-1$번 행까지는 이 $M$개의 기차의 정보를 번호가 커지는 순서대로 보여준다. 또한, 기차가 출발하기까지 $K$쵸 이하로 남은 경우에는 탑승을 준비하라는 의미에서 해당 기차의 정보는 빨간색으로 표시하고, $K$쵸 초과로 남은 경우에는 흰색으로 표시한다. 예를 들어, $K=20$이고 모든 기차가 예정된 시각에 출발하는 경우, $5.5$쵸에 전광판의 $i(0 \leq i \leq 999 \ 999\ 999\ 993)$번 행에는 $i+6$번 기차의 정보가 표시된다. 또, $0$번 행부터 $19$번 행까지는 출발 시각이 $25.5$쵸 이전인 기차의 정보를 표시하고 있으므로 빨간색이며, $20$번 행부터 $999 \ 999\ 999\ 993$번 행까지는 흰색이다.

아직 출발하지 않은 기차의 수 $M$과 두 정수 $l, r(0 \leq l \leq r \leq M-1)$에 대하여 다음 세 조건이 모두 성립할 경우, $l$과 $r$의 순서쌍 $(l, r)$을 빨간색 연속 구간이라고 부른다.

임의의 정수 $k(l \leq k \leq r)$에 대하여, 전광판의 $k$번 행에서는 빨간색으로 정보를 표시하고 있다.
$l = 0$이거나, 전광판의 $l-1$번 행에서는 흰색으로 정보를 표시하고 있다.
$r = M-1$ 이거나, 전광판의 $r+1$번 행에서는 흰색으로 정보를 표시하고 있다.

$M\ge 1$이고 모든 기차가 예정된 시각에 출발하는 경우, 전광판의 첫 몇 개의 행은 빨간색이고 나머지는 흰색이므로 빨간색 연속 구간의 개수는 $1$이다. 하지만 몇몇 기차가 지연될 경우, 기차의 번호 순서와 출발 시각 순서가 일치하지 않아 빨간색 연속 구간의 개수가 많아질 수 있다. 예를 들어, $K=20$이고 $3$번 기차가 $30$쵸 지연되어 $33$쵸에 출발하고, $10$번 기차가 $20$쵸 지연되어 $30$쵸에 출발하는 경우, $5.5$쵸에 $M = 999 \ 999 \ 999 \ 995$이고 전광판에 표시되는 정보는 다음과 같다.


전광판의 행 번호	$0$	$[1,4]$	$5$	$[6,20]$	$[21, 999\ 999 \ 999\ 994]$
표시하고 있는 기차의 번호	$3$	$[6,9]$	$10$	$[11,25]$	$[26, 999\ 999\ 999\ 999]$
색깔	흰색	빨간색	흰색	빨간색	흰색

따라서 이 경우 빨간색 연속 구간은 $(1, 4)$와 $(6, 20)$이며 그 개수는 $2$이다.

빨간색 연속 구간의 개수가 많으면, 중요한 정보가 한곳에 모여 있지 않아 기차를 타는 사람들에게 혼란을 줄 수 있다. 따라서 기차가 지연될 경우, 각 순간에 빨간색 연속 구간의 개수를 파악한 후에, 이에 맞추어 전광판의 표시 형식을 바꾸거나 공지하는 등의 조치를 취해야 한다. 다행히도 $2024$년까지는 많은 기차가 한꺼번에 지연된 사례가 없어서, 컴퓨터의 도움 없이 사람이 직접 빨간색 연속 구간의 개수를 파악하여 조치를 취했다.

그러나 $2024$년 $12$월 $31$일 $999 \ 965 \ 277 \ 778$쵸, $2025$년 $1$월 $1$일 출발 예정인 많은 기차가 지연되었다는 제보 $N$개가 동시에 들어왔다. $i(1 \leq i \leq N)$번 제보에 의하면, 번호가 $L_i$ 이상 $R_i$ 이하인 기차의 출발 시각은 각각 $D_i$쵸만큼 늦추어졌다. 이때, 한 기차에 대해 출발 시각이 늦추어졌다는 제보가 여러 개인 경우, 이 기차의 출발 시각은 제보들에 대한 $D_i$의 합만큼 늦추어졌다고 한다. 당황한 IOI 기차역의 관리자는 $2025$년 $1$월 $1$일 $0$쵸가 되기 전에 $2025$년 $1$월 $1$일의 여러 시각에 대해 빨간색 연속 구간의 수를 파악해야 해서 여러분에게 도움을 요청했다. $Q$개의 시각 $T_1, T_2, …, T_Q$가 주어졌을 때, 각 $i(1 \leq i \leq Q)$에 대해 $2025$년 $1$월 $1$일 $T_i + 0.5$쵸에 빨간색 연속 구간의 수를 구하여라.

입력

첫째 줄에 제보의 수 $N$, 빨간색으로 표시하는지 여부의 기준이 되는 시간 $K$가 공백을 사이에 두고 주어진다.

각 $i (1 \leq i \leq N)$에 대하여, $i+1$번째 줄에는 $i$번 제보의 내용 $L_i, R_i, D_i$가 순서대로 공백을 사이에 두고 주어진다.

$N+2$번째 줄에, 빨간색 연속 구간의 수를 구해야 하는 시각의 수 $Q$가 주어진다.

각 $i(1 \leq i \leq Q)$에 대하여, $i+N+2$번째 줄에는 $T_i$가 주어진다.

출력

$Q$개의 줄에 걸쳐 정답을 출력한다. $i(1 \leq i \leq Q)$번째 줄에는 $2025$년 $1$월 $1$일 $T_i + 0.5$쵸에 빨간색 연속 구간의 수를 출력한다.

제한

$ 1 \leq N \leq 200\ 000 $
$1 \leq K \leq 10^{12} - 1 $
각 $1 \leq i \leq N$에 대하여, $0 \leq L_i \leq R_i \leq 10^{12}-1$이고 $1 ≤ D_i ≤ 10^6$
$ 1 \leq Q \leq 200\ 000 $
$0 \leq T_1 < T_2 < … < T_Q\leq 10^{12} - 1$
주어지는 모든 수는 정수이다.