정올국에는 1~N번까지의 번호가 순서대로 붙어있는 N개의 역이 있다.

i번 역과 i+1번 역 사이에는 철로가 깔려있다.

주식회사 박재민은 이 역들을 지나는 M개의 기차 노선을 운영하고 있다. j번 노선은 A_j 번 역에서 출발해 B_j번 역까지 운행한다.

A_j < B_j 라면 기차는 A_j, A_j + 1, ... , B_j번 역을 차례대로 지나고, 그 반대라면 기차는 A_j, A_j - 1, ... , B_j번 역을 차례대로 지난다.

기차는 항상 지나는 모든 역에서 정차하고 승객은 어느 역에서든 내릴 수 있다.

준혁이는 여행자이다. 준혁이는 Q개의 여행 계획을 가지고 있다.

준혁이의 k번째 여행 계획은 S_k번 역에서 T_k번 역으로 기차를 타고 이동하는 것이다.

하지만 준혁이는 연약하고 지쳐 기차에 앉아서 가고 싶어한다.

따라서 준혁이는 어떤 노선이든 시작역으로부터 K번째 이내인 역에서만 승차해 빈 자리를 사수할 계획이다.

보다 정확히, A_j < B_j라면 준혁이는 A_j, A_j + 1, ... , min{A_j + K - 1, B_j + 1}에서만 j번 노선에 탑승할 것이고,

A_j > B_j라면 준혁이는 A_j, A_j - 1, ... , min{A_j - K + 1, B_j + 1}에서만 j번 노선에 탑승할 것이다.

준혁이는 이런 조건을 지키면서 각 여행계획마다 역들 사이를 이동하는 방법을 알고 싶다.

연약한 준혁이는 기차를 갈아타는 횟수를 최소화 하고 싶어한다. 여러분이 준혁이를 도와주자!

칙칙폭폭 timer 2초 memory 512MB

칙칙폭폭 2초 512MB