题目描述

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$.

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