Oscar is playing games throughout an entire course! In this course, there are ~N~ friends, and ~M~ snitches. Each friend will cover Oscar for a number of lessons, from ~a~ to ~b~, inclusive. Each snitch will also be next to Oscar for a number of lessons, from ~c~ to ~d~, inclusive. Oscar is only able to play games during lessons when there are strictly more friends covering him than snitches.

Given that there are ~K~ lessons in this course, and ~Q~ queries, can you figure out at what point in time Oscar will game for ~t_i~ lessons for each query? If he will never reach this many lessons, print ~-1~.

Input Specification

The first line will contain ~N~ ~(1 \leq N \leq 10^5)~, ~M~ ~(1 \leq M \leq 10^5)~, ~K~ ~(1 \leq K \leq 10^5)~, and ~Q~ ~(1 \leq Q \leq 10^5)~, the number of friends, snitches, lessons in the course, and queries respectively.

The next ~N~ lines will contain integers ~a_i~ and ~b_i~ ~(1 \leq a_i \leq b_i \leq K)~, the lessons where Oscar is covered for.

The next ~M~ lines will contain integers ~c_i~ and ~d_i~ ~(1 \leq c_i \leq d_i \leq K)~, the lessons where a snitch will be next to Oscar.

The next ~Q~ lines will contain integer ~t_i~ ~(1 \leq t_i \leq K)~, the query that Oscar wants you to figure out.

Output Specification

For each query, output the earliest point in time Oscar will have gamed for ~t_i~ lessons in total, or ~-1~ if he can't achieve this.

Subtask 1 [30%]

~(1 \leq N, M, K, Q \leq 10^3)~

Subtask 2 [70%]

No further constraints.

Sample Input 1

4 2 10 4
1 3
3 6
4 4
9 10
2 8
2 4
1
2
3
4

Sample Output 1

1
9
10
-1

Sample Explanation

Oscar can only play games during the ~1~st, ~9~th and ~10~th lessons. Since he will never game for ~4~ lessons in total, the answer is ~-1~.