PS 이야기

A. 새 집 (New Home) $N$개의 상점이 주어진다. $i$번째 상점은 위치 $x_i$에 지어지며, 종류는 $t_i$이고, $a_i$년 초에 생겨, $b_i$년 말에 없어진다. 상점의 종류는 $K$가지이다. $Q$개의 질문이 주어진다. $i$번째 질문은, $y_i$년 중순에 $l_i$위치에 집을 지을 경우, 상점 종류마다 제일 가까운 상점과의 거리를 구해 그 중 최대값을 요구한다. 예를 들어, $K=2$이고 어떤 특정 시점에 1번 종류 상점이 좌표 2, 5, 13에 있고, 2번 종류 상점이 좌표 6, 10, 15에 있다고 했을 때, 아래와 같은 그래프를 그릴 수 있다. 그래프에서 파란색 선은 1번 종류 상점에 대한 거리를 나타내고, 주황색 선은 2번 종류 상점에 대해 거리를 나타낸다. 이 순간 좌..