기차 여행

먼 미래 인류는 우리은하 내에 수많은 행성을 연결하는 우주 철도 시스템을 개발하였다. 이 철도 시스템에 $N$ 개의 기차역이 있고, $M$ 개의 기차가 운행 중이다. 기차역은 $1$번부터 $N$번까지 번호가 매겨져 있다.

각 기차는 (출발역, 출발 시각)과 (도착역, 도착 시각)으로 구성된 운행 정보가 있다.

철이는 이 철도 시스템을 이용해서 목적지인 $K$번 기차역으로 가려고 한다. 철이는 어떤 역에서 출발하여 필요하면 중간에 환승하여 목적지까지 갈 수 있다. 환승하는 데 시간은 걸리지 않는 것으로 가정하자. 다시 말해서, 어떤 역에 시각 $t$에 도착하였다면, 시각 $t$ 또는 그 이후에 출발하는 기차로 환승이 가능하다.

기차들의 운행 정보와, 출발역 번호 $S$와 출발 시각 $T$로 구성된 $Q$ 개의 쿼리가 주어진다. 각 쿼리마다 철이가 $S$번 기차역에서 시각 $T$에 여행을 시작하여, 필요하면 환승을 통해 $K$번 기차역에 도착하는 최소 시각을 구하는 프로그램을 작성하라.

입력 형식

첫 줄에 기차역의 수를 나타내는 정수 $N$, 기차의 수를 나타내는 정수 $M$, 도착 기차역의 번호를 나타내는 정수 $K$, 쿼리의 수를 나타내는 정수 $Q$가 공백으로 구분되어 주어진다. ($2 \le N \le 100\,000;$ $1 \le M \le 300\,000;$ $1 \le K \le N;$ $1 \le Q \le 100\,000$)

이어지는 $M$ 개의 줄의 $i$ 번째 줄에는 $i$ 번째 기차의 정보를 나타내는 네 정수 $s$, $t_s$, $d$, $t_d$가 공백으로 구분되어 주어진다. 이는 $i$ 번째 기차가 $s$번 기차역에서 시각 $t_s$에 출발하여 $d$번 기차역에 시각 $t_d$에 도착함을 의미한다. ($1 \le s, d \le N;$ $1 \le t_s \lt t_d \le 1\,000\,000\,000;$ $s \ne d$)

이어지는 $Q$ 개의 줄의 $i$ 번째 줄에는 $i$ 번째 쿼리의 정보를 나타내는 두 정수 $s$와 $t$가 공백으로 구분되어 주어진다. 이는 $i$ 번째 쿼리가 $s$번 기차역에서 시각 $t$에 출발하는 것임을 의미한다. ($1 \le s \le N;$ $1 \le t \le 1\,000\,000\,000;$ $s \ne K$)

출력 형식

$Q$ 개의 줄에 걸쳐 답을 출력한다. $i$ 번째 줄에는 $i$ 번째 쿼리에 대한 답을 출력한다. 만약, 도착 기차역으로 가지 못하는 경우 $-1$을 출력한다.

예제

4 5 4 3
1 1 2 5
2 5 4 10
1 5 3 12
3 14 4 25
3 15 4 24
1 1
1 4
1 7

10
24
-1

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞혀야 그 종류에 배정된 점수를 받을 수 있다.

해설