In designing a printed circuit board (PCB), each consumer must be connected to a power supply via conductive wires. The PCB is a rectangle of width and height . It is represented as a grid of integer coordinates from to .
There are power supplies along the left edge of the board and consumers each located somewhere inside the board. The power supply is located at position and the consumer is located at position . Each power supply must connect to exactly one consumer and vice versa.
Each wire must run along the grid lines, bending at most once. i.e., each wire is either a straight vertical or horizontal line or makes exactly one 90-degree turn, forming an "L" shape. Wires cannot cross or overlap with each other anywhere along their paths.
Your task is to determine a matching between power supplies and consumers such that the total length of all wires is minimized.
输入格式
The input consists of several lines:
The first line contains three integers , and (; ).
Each of the next lines contains an integer ().
Each of the next lines contains two integers and (; ).
It is guaranteed that each point in the board contains at most one power supply or consumer. Moreover, no two consumers and exist where .
输出格式
If it is not possible to find such a matching under the given constraints, output a single line containing .
Otherwise, output a single line containing space-separated integers. The integer describes , indicating that power supply is connected to consumer .
