만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

기차 지연

시간 제한3초메모리 제한1024 MB

요약
지연 보고 N개가 주어질 때, 각 질의 시각 T_i + 0.5 cho에서 출발까지 K cho 이내인 열차 구간(빨간 구간)의 개수를 구합니다.
난이도

어려움10점 중 9점

유형
세그먼트 트리, 구간, 정렬
정답자
아직 제출이 없습니다

문제

IOI 도시는 세계에서 가장 인구가 많고 바쁜 도시이다. 보통 하루는 86 40086\,400초이지만, IOI 도시에서는 시간의 단위인 '쵸'를 정의하여 하루를 101210^{12}쵸로 잘게 나누어 쓴다. 하루의 시작은 00쵸이다. 실수 tt (0≤t<10120 \leq t < 10^{12})에 대하여, 00쵸에서 tt쵸가 지난 시각을 tt쵸라고 한다. 1012−110^{12}-1쵸에서 11쵸가 지나면 다음 날 00쵸가 된다.

IOI 도시는 교통량이 매우 많아서 기차역에서는 매일 101210^{12}대의 기차가 출발한다. 기차에는 00부터 1012−110^{12}-1까지 정수 번호가 붙어 있고, ii번 기차(0≤i≤1012−10 \leq i \leq 10^{12}-1)는 ii쵸에 출발하도록 예정되어 있다.

기차역에는 행이 101210^{12}개인 대형 전광판이 있다. 행에는 00부터 1012−110^{12}-1까지 번호가 붙어 있다. 그날 출발하기로 예정되어 있지만 아직 출발하지 않은 기차가 MM대일 때, 전광판의 00번 행부터 M−1M-1번 행까지는 이 MM대의 기차 정보를 번호가 작은 순서대로 표시한다. 기차가 출발하기까지 KK쵸 이하로 남았으면 그 기차의 정보는 탑승 준비를 알리는 뜻으로 빨간색으로 표시하고, KK쵸를 넘게 남았으면 흰색으로 표시한다.

예를 들어 K=20K=20이고 모든 기차가 예정대로 출발한다고 하자. 5.55.5쵸에 전광판의 ii번 행(0≤i≤999 999 999 9930 \leq i \leq 999\,999\,999\,993)에는 i+6i+6번 기차의 정보가 표시된다. 00번 행부터 1919번 행은 25.525.5쵸 이전에 출발하는 기차를 나타내므로 빨간색이고, 2020번 행부터 999 999 999 993999\,999\,999\,993번 행까지는 흰색이다.

기차 수 MM과 정수 ll, rr(0≤l≤r≤M−10 \leq l \leq r \leq M-1)에 대하여 다음 세 조건을 모두 만족하면, 순서쌍 (l,r)(l, r)을 빨간색 연속 구간이라고 한다.

  • 모든 정수 kk(l≤k≤rl \leq k \leq r)에 대하여, 전광판의 kk번 행은 빨간색으로 표시된다.
  • l=0l = 0이거나, 전광판의 l−1l-1번 행은 흰색으로 표시된다.
  • r=M−1r = M-1이거나, 전광판의 r+1r+1번 행은 흰색으로 표시된다.

M≥1M \geq 1이고 모든 기차가 예정대로 출발하면, 전광판의 앞쪽 몇 개 행은 빨간색이고 나머지는 흰색이므로 빨간색 연속 구간은 1개이다.

그러나 기차가 지연되면 기차 번호 순서와 출발 시각 순서가 어긋나서 빨간색 연속 구간이 여러 개 생길 수 있다. 예를 들어 K=20K=20이고, 33번 기차가 3030쵸 지연되어 3333쵸에 출발하고 1010번 기차가 2020쵸 지연되어 3030쵸에 출발한다고 하자. 5.55.5쵸에는 M=999 999 999 995M = 999\,999\,999\,995이고, 전광판에는 다음 정보가 표시된다.

전광판의 행 번호00[1,4][1,4]55[6,20][6,20][21,999 999 999 994][21, 999\,999\,999\,994]
표시하고 있는 기차의 번호33[6,9][6,9]1010[11,25][11,25][26,999 999 999 999][26, 999\,999\,999\,999]
색깔흰색빨간색흰색빨간색흰색

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

빨간색 연속 구간이 많으면 중요한 정보가 한곳에 모이지 않아 승객이 혼란을 겪을 수 있다. 그래서 기차가 지연되면 각 순간의 빨간색 연속 구간 수를 파악하고, 그에 맞추어 전광판의 표시 방식을 바꾸거나 안내 방송을 해야 한다. 2024년까지는 많은 기차가 한꺼번에 지연된 적이 없어서, 직원이 사람의 손으로 빨간색 연속 구간의 수를 세어 조치했다.

그런데 2024년 12월 31일 999 965 277 778999\,965\,277\,778쵸에, 2025년 1월 1일 출발 예정인 많은 기차가 지연되었다는 제보 NN개가 동시에 들어왔다. ii번 제보에 따르면, 번호가 LiL_i 이상 RiR_i 이하인 기차의 출발 시각은 각각 DiD_i쵸씩 늦추어졌다. 한 기차에 대해 제보가 여러 개 있으면, 그 기차의 출발 시각은 제보들의 DiD_i를 모두 합한 만큼 늦추어졌다.

관리자는 2025년 1월 1일 00쵸가 되기 전에 2025년 1월 1일의 여러 시각에 대한 빨간색 연속 구간의 수를 알아내야 한다. QQ개의 시각 T1,T2,…,TQT_1, T_2, \ldots, T_Q가 주어질 때, 각 ii(1≤i≤Q1 \leq i \leq Q)에 대하여 2025년 1월 1일 Ti+0.5T_i + 0.5쵸에 빨간색 연속 구간의 수를 구하라.

입력

첫째 줄에 제보의 수 NN과 빨간색 표시 기준이 되는 시간 KK가 공백으로 구분되어 주어진다.

각 ii(1≤i≤N1 \leq i \leq N)에 대하여, i+1i+1번째 줄에 ii번 제보의 내용 LiL_i, RiR_i, DiD_i가 공백으로 구분되어 주어진다.

N+2N+2번째 줄에 시각의 수 QQ가 주어진다.

각 ii(1≤i≤Q1 \leq i \leq Q)에 대하여, i+N+2i+N+2번째 줄에 TiT_i가 주어진다.

출력

QQ개의 줄에 걸쳐 정답을 출력한다. ii번째 줄에는 2025년 1월 1일 Ti+0.5T_i + 0.5쵸에서의 빨간색 연속 구간의 수를 출력한다.

제한

  • 1≤N≤200 0001 \leq N \leq 200\,000
  • 1≤K≤1012−11 \leq K \leq 10^{12} - 1
  • 각 ii(1≤i≤N1 \leq i \leq N)에 대하여 0≤Li≤Ri≤1012−10 \leq L_i \leq R_i \leq 10^{12}-1이고 1≤Di≤1061 \leq D_i \leq 10^6
  • 1≤Q≤200 0001 \leq Q \leq 200\,000
  • 0≤T1<T2<⋯<TQ≤1012−10 \leq T_1 < T_2 < \cdots < T_Q \leq 10^{12} - 1
  • 주어지는 모든 수는 정수이다.

예제2

  1. 예제 1

    입력
    4 20
3 3 30
10 10 20
999999999000 999999999999 1019
999999999000 999999999000 2
3
5
10
999999999999
    예상 출력
    2
1
0

  2. 예제 2

    입력
    4 10
1 4 3
8 10 10
18 19 1
18 20 1
5
0
1
6
7
21
    예상 출력
    1
2
2
1
1