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 $WW$ and height $HH$. It is represented as a grid of integer coordinates from $(0,0)(0,\; 0)$ to $(W+1,H+1)(W\; +\; 1,\; H\; +\; 1)$.

There are $nn$ power supplies along the left edge of the board and $nn$ consumers each located somewhere inside the board. The $ii$^th power supply is located at position $(0,h_i)(0,\; h\_i)$ and the $ii$^th consumer is located at position $(x_i,y_i)(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 $9090$-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 $WW$, $HH$ and $nn$ ($1\le W,H\le {10}^{8}1\; \backslash le\; W,\; H\; \backslash le\; 10^8$; $1\le n\le {10}^{6}1\; \backslash le\; n\; \backslash le\; 10^6$).
• Each of the next $nn$ lines contains an integer $h_{i}h\_i$ ($1\le h_i\le H1\; \backslash le\; h\_i\; \backslash le\; H$).
• Each of the next $nn$ lines contains two integers $x_{i}x\_i$ and $y_{i}y\_i$ ($1\le x_i\le W1\; \backslash le\; x\_i\; \backslash le\; W$; $1\le y_i\le H1\; \backslash le\; y\_i\; \backslash le\; H$).

It is guaranteed that each point in the board contains at most one power supply or consumer. Moreover, no two consumers $ii$ and $jj$ exist where $x_i=x_{j}x\_i\; =\; x\_j$.

출력

If it is not possible to find such a matching under the given constraints, output a single line containing $-1-1$.

Otherwise, output a single line containing $nn$ space-separated integers. The $ii$^th integer describes $p_{i}p\_i$, indicating that power supply $ii$ is connected to consumer $p_{i}p\_i$.

5 5 2
2
4
3 2
5 4

1 2

10 10 5
9
6
2
8
1
2 3
5 8
3 8
4 8
1 2

2 4 5 3 1