Pinholes
本题没有可用的提交语言。
Description
You are planning lighting in a warehouse room, which in the cross section consists of the ceiling (line $y=2$) and the floor (line $y=0$). The room is infinite and extends to left and right indefinitely. To illuminate the room, some lamps must be installed in the ceiling, where each lamp shines in all possible downwards directions.
The ceiling is ugly (you can see all of the pipes and wires), hence an aesthetic drop ceiling will be installed (at the line $y=1$). To let the lamps shine through, $n$ pinpoint holes (pinholes) were made at distinct positions. For each pinhole, each lamp will shine through in a single straight line. The result is that there are some points on the floor which light shines on.
For the desired lighting, it is necessary to illuminate $m$ distinct points on the floor (such points may be illuminated by one or multiple lamps). No other points on the floor should be illuminated. Your task is, given the list of the coordinates of $n$ pinholes and $m$ points on the floor required to be illuminated, determine whether it is possible to install some lamps in the ceiling so that the required points (and only such points) are illuminated.
The first line of input contains two integers $n$ and $m$ ($1 \leq n, m \leq 2\,000$), the numbers of pinholes and points to be illuminated. The second line contains $n$ distinct integers $a_1$, $\ldots$, $a_n$ ($-10^8 \leq a_i \leq 10^8$) which mean that the $i$-th pinhole is located at the coordinates $(a_i,1)$. The third line contains $m$ integers $b_1$, $\ldots$, $b_m$ ($-10^8 \leq a_i \leq 10^8$) which mean that the $i$-th point on the floor that needs to be illuminated is located at the coordinates $(b_i,0)$.
If the required is impossible, output "No". Otherwise output "Yes" and an integer $k$ ($1 \leq k \leq m$) in the next line, the number of lamps. In the third line output $k$ distinct integers $c_1$, $\ldots$, $c_k$ ($-10^9 \leq c_i \leq 10^9$) which mean that the $i$-th lamp should be installed at the coordinates $(c_i,2)$.
If there are multiple solutions, output any of those. It can be proven that if the solution exists, then there is a solution that uses at most $m$ lamps.
Input
The first line of input contains two integers $n$ and $m$ ($1 \leq n, m \leq 2\,000$), the numbers of pinholes and points to be illuminated. The second line contains $n$ distinct integers $a_1$, $\ldots$, $a_n$ ($-10^8 \leq a_i \leq 10^8$) which mean that the $i$-th pinhole is located at the coordinates $(a_i,1)$. The third line contains $m$ integers $b_1$, $\ldots$, $b_m$ ($-10^8 \leq a_i \leq 10^8$) which mean that the $i$-th point on the floor that needs to be illuminated is located at the coordinates $(b_i,0)$.
Output
If the required is impossible, output "No". Otherwise output "Yes" and an integer $k$ ($1 \leq k \leq m$) in the next line, the number of lamps. In the third line output $k$ distinct integers $c_1$, $\ldots$, $c_k$ ($-10^9 \leq c_i \leq 10^9$) which mean that the $i$-th lamp should be installed at the coordinates $(c_i,2)$.
If there are multiple solutions, output any of those. It can be proven that if the solution exists, then there is a solution that uses at most $m$ lamps.
3 4
0 -1 1
4 0 -2 2
2 2
3 4
2 6
Yes
2
-2 0
No