방학 중 기차 여행

플랫랜드의 철도는 직선이고, 그 위에 n개의 역이 놓여 있다. 한 역에서 바로 다음 역까지의 철도 구간을 구간이라고 부른다. 열차는 1번 역에서 n번 역까지 달리며 모든 역에 정차한다. 열차에는 1번부터 k번까지 번호가 붙은 k개의 좌석이 있다. 승차권은 세 개의 수 s, t, a로 표현되며, 이 승차권으로 s번 역에서 t번 역까지 a번 좌석에 앉아 갈 수 있다.

바시는 여름 방학의 어느 날 한 역에서 다른 역까지 열차를 타려고 한다. 그날은 이미 m장의 승차권이 팔렸고, 그가 가려는 역 사이의 모든 구간에서 비어 있는 좌석이 없을 수도 있다. 두 역 사이의 승차권은 그 두 역 사이의 모든 구간에서 해당 좌석이 비어 있을 때만 살 수 있다.

바시는 중간 역에서 좌석을 바꾸며 승차권 여러 장을 사면 두 역 사이를 갈 수 있는 경우가 있다는 것을 알아챘다. 좌석을 바꾸는 것은 불편하므로, 바시는 여행의 모든 구간마다 자기 좌석이 하나씩 있도록 승차권을 최소 개수만 사려고 한다.

바시는 아직 출발역과 도착역을 정하지 않았다. 그는 가능한 여행 q가지를 적어 두었고, 각 여행마다 그 여행을 하려면 최소 몇 장의 승차권을 사야 하는지 알고 싶어 한다.

이미 팔린 승차권 정보와 여행 목록이 주어질 때, 각 여행에 필요한 승차권의 최소 개수를 구하라.

첫 줄에 세 정수 n, m, k가 주어진다 (2 이상 200000 이하, 0 이상 200000 이하, 1 이상 200000 이하). 각각 역의 수, 이미 팔린 승차권의 수, 열차의 좌석 수이다.

이어지는 m줄에는 승차권 정보 s_i, t_i, a_i가 한 줄에 하나씩 주어진다. 각각 승차권이 시작되는 역, 끝나는 역, 좌석 번호이다. 1 이상 s_i 미만 t_i 이하 n 이하이고, 1 이상 a_i 이하 k 이하이다.

어떤 구간의 어떤 좌석에도 승차권이 두 장 이상 팔리지 않았음이 보장된다.

다음 줄에 q (1 이상 200000 이하)가 주어진다. 이어지는 q줄에는 여행의 출발역 f_j와 도착역 d_j가 주어진다. 1 이상 f_j 미만 d_j 이하 n 이하이다.

q개의 수를 출력한다. 각 여행에 대해 바시가 그 여행을 하기 위해 사야 하는 승차권의 최소 개수를 출력한다. 여행이 불가능하면 -1을 출력한다.

2번 역에서 3번 역 사이의 구간은 모든 좌석이 차 있으므로 1번 역에서 5번 역까지는 갈 수 없다. 3번 역에서 5번 역까지는 3번에서 4번 역까지 2번 좌석 승차권과 4번에서 5번 역까지 1번 좌석 승차권, 이렇게 두 장으로 갈 수 있다. 4번 역에서 5번 역까지는 1번 좌석 승차권 한 장으로 갈 수 있다.