P14696 [ICPC 2024 Tehran R] PCB

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 $W$ and height $H$. It is represented as a grid of integer coordinates from $(0,0)$ to $(W+1,H+1)$. There are $n$ power supplies along the left edge of the board and $n$ consumers each located somewhere inside the board. The $i^{th}$ power supply is located at position $(0,h_i)$ and the $i^{th}$ consumer is located at position $(x_i,y_i)$. 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 $W$, $H$ and $n$ ($1 \leq W,H \leq 10^8$; $1 \leq n \leq 10^6$). - Each of the next $n$ lines contains an integer $h_i$ ($1 \leq h_i \leq H$). - Each of the next $n$ lines contains two integers $x_i$ and $y_i$ ($1 \leq x_i \leq W$; $1 \leq y_i \leq H$). It is guaranteed that each point in the board contains at most one power supply or consumer. Moreover, no two consumers $i$ and $j$ exist where $x_i = x_j$.

If it is not possible to find such a matching under the given constraints, output a single line containing $-1$. Otherwise, output a single line containing $n$ space-separated integers. The $i^{th}$ integer describes $p_i$, indicating that power supply $i$ is connected to consumer $p_i$.