The country of JOI exists on a plane. Within the country, there are N villages numbered from 1 to N. Village i is located at (i, 0). Currently, the country of JOI is in the process of establishing a communication system that connects the N villages. To reduce the probability of failure, two communication systems will be built. These will be called system 1 and system 2.
In system k, there are Mk hubs and N + Mk - 1 communication lines. The hubs in system k are numbered from 1 to Mk. Hub j from system k is located at (Xkj, Ykj). Each communication line in system k is a straight line that connects a system k hub and another system k hub or one of the N villages. It is guaranteed that any pair of communication lines will not share any common point aside from their endpoints. For each hub j in system 1, its y-coordinate Y1j is greater than 0. For each hub j in system 2, its y-coordinate Y2j is less than 0.
We will call a pair of points connected if they are connected by a set of communication lines. In other words, two points are connected if, moving along communication lines between points on the plane, it is possible to move from either of the points to the other. The villages are connected with respect to system 1. In other words, considering only the communication lines and hubs in system 1, any pair of the N villages are connected. Similarly, the villages are also connected with respect to system 2.
The following diagram shows several possible layouts of the country's communication systems. Grey circles are system 1 hubs and black circles are system 2 hubs. The white circles represent the villages.
|
|
Figure 1: Example communication system 1 |
Figure 2: Example communication system 2 |
To evaluate several possible plans for the system's layout, we will investigate the resilience of the proposed communication system to external attacks. Each attack on the communication system can be expressed by two integers A and B (A ≥ 0, B ≤ 0), which indicate that all hubs with y-coordinate greater than A or less than B are destroyed. It is not possible to communicate between two communication lines if the hub joining them has been destroyed.
Given the proposed layout of the communication system, you are to answer Q queries about it. Query q is represented by one integer Aq. This means that all hubs with y-coordinate greater than Aq are destroyed. For each query, determine an integer Bq (Bq ≤ 0) such that even if all hubs with y-coordinate less than Bq are also destroyed, the N villages are still connected. If there are multiple such Bq, output the largest possible value of Bq.
Input
Read from standard input.
Output
Print to standard output.
For each query q of the Q queries, print one integer Bq on one line, representing the answer to the query. If the answer is 0, you are not allowed to output -0.
Constraints
All test cases satisfy the following constraints:
- 1 ≤ N, M1, M2 ≤ 100 000.
- -1 000 000 000 ≤ X1i ≤ 1 000 000 000 (1 ≤ i ≤ M1).
- -1 000 000 000 ≤ X2i ≤ 1 000 000 000 (1 ≤ i ≤ M2).
- 1 ≤ Y1i ≤ 1 000 000 000 (1 ≤ i ≤ M1).
- -1 000 000 000 ≤ Y2i ≤ -1 (1 ≤ i ≤ M2).
- X1i ≠ X1j or Y1i ≠ Y1j (1 ≤ i, j ≤ M1 and i ≠ j).
- X2i ≠ X2j or Y2i ≠ Y2j (1 ≤ i, j ≤ M2 and i ≠ j).
- 1 ≤ Q ≤ 100 000.
- 0 ≤ Aq ≤ 1 000 000 000 (1 ≤ q ≤ Q).
- No two distinct communication lines will share points other than their endpoints.
- The villages are connected with respect to system 1 and also with respect to system 2.
Subtasks
Subtask 1 (20 points):
The following constraints are satisfied.
- N, M1, M2 ≤ 1 000.
- Q ≤ 1 000.
Subtask 2 (80 points):
No further constraints.
Sample Input 1
4 3 3 1
1 1
3 2
2 3
1 1 1
1 2 1
1 3 2
1 4 2
2 1 3
2 2 3
3 -1
2 -2
1 -3
1 1 3
1 2 2
1 3 1
1 4 1
2 1 2
2 2 3
2
Sample Output 1
-2
This test case is corresponds to Figure 1 above.
Sample Input 2
6 4 5 4
2 1
4 1
3 3
5 2
1 1 1
1 2 1
1 3 2
1 4 2
2 2 4
1 5 4
1 6 4
2 1 3
2 4 3
3 -3
5 -1
2 -2
2 -1
4 -2
1 2 4
1 3 4
1 1 4
2 1 3
1 5 2
1 6 2
1 4 5
2 2 5
1 3 1
2 5 1
3
1
2
0
Sample Output 2
0
-2
-1
-3
This test case corresponds to Figure 2 above.