Problem H
Sawmill
After the oak tree fell down, Owl needed a new home. Since there were no more trees with large convenient hollows left, Owl decided to build a new home from the logs sawed from some old dry trees.
Since the Owl does not want to saw herself, she gets to the nearest sawmill. This sawmill, like many others, uses innovative technologies — it has an automatic log cutter. It consists of a very long ruler along which coordinates are measured, a tree trunk holder, and $n$ stationary laser saws. The left end of the trunk being cut is secured by the holder at some point, and the trunk is cut at all points whose coordinates match the coordinates of the saws.
Since Owl needs logs that are no shorter than $a$ and no longer than $b$ to build her house, she wants to know for each of the tree trunks she has whether it can be cut at the sawmill into suitable logs in one attempt.
Input
The first line of the input contains one integer $n$ $(1 \le n \le 10^6)$— the number of saws in the automatic log cutter. The next line contains $n$ integers $x_i$ $(|x_i| \le 10^9)$— the coordinates of the $i$-th saw. All saw coordinates are distinct and are given in the sorted order.
The third line contains three integers: $l, a, b$ $(1 \le l \le 10^9, 1 \le a \le b \le 10^9)$— the length of the trunk that Owl wants to cut and the lengths of the shortest and longest logs that are suitable for Owl.
Output
The first line of the output should contain “YES” if it is possible to cut the trunk, otherwise, it should contain “NO”.
If it is possible, the second line should contain one integer — the coordinates of the point where the left end of the log should be placed so that it is cut into suitable logs.
Sample Input 1 | Sample Output 1 |
---|---|
3 0 1 3 3 1 1 |
YES -1 |
Sample Input 2 | Sample Output 2 |
---|---|
3 0 1 3 4 1 1 |
NO |
Sample Input 3 | Sample Output 3 |
---|---|
5 0 1 5 9 10 7 4 5 |
NO |