Page not loading? Try clicking here.
Placeholder

#8062
Subtask

버스 갈아타기 2 5s 1024MB

Problems

N 개의 버스 정류장이 있고, M 개의 버스가 운행 중이다. 버스 정류장은 1번부터 N번까지 번호가 매겨져 있다.

각 버스는 (출발 정류장, 출발 시각)과 (도착 정류장, 도착 시각)으로 구성된 운행 정보가 있다.

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

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


Input

첫 줄에 버스 정류장의 수를 나타내는 정수 N, 버스의 수를 나타내는 정수 M, 도착 버스 정류장의 번호를 나타내는 정수 K, 쿼리의 수를 나타내는 정수 Q가 공백으로 구분되어 주어진다. (2 ≤ N ≤ 150,000; 1 ≤ M ≤ 300,000; 1 ≤ K ≤ N; 1 ≤ Q ≤ 90,000)

이어지는 M 개의 줄의 i 번째 줄에는 i 번째 버스의 정보를 나타내는 네 정수 s, t_s, d, t_d가 공백으로 구분되어 주어진다. 이는 i 번째 버스가 s번 버스 정류장에서 시각 t_s에 출발하여 d번 버스 정류장에 시각 t_d에 도착함을 의미한다. (1 ≤ s, d ≤ N; 1 ≤ t_s < t_d ≤ 1,000,000,000; s ≠ d)

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


Output

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


Subtask

# Score Condition
#120

N \le 10, M \le 20, Q \le 30

#230

N \le 1000, M \le 3000, Q \le 500

#350

추가 제약 조건 없음


Example 

4 8 4 4
1 1 2 9
1 3 3 4
1 6 3 7
3 5 2 7
2 8 4 15
2 9 3 10
2 13 4 17
3 10 4 20
1 1
1 3
1 5
2 11
15
15
20
17
You must sign in to write code.