Description

在设计印刷电路板（PCB）时，每个用电设备必须通过导电导线连接到电源。PCB 是一个宽度为 $W$、高度为 $H$ 的矩形。它被表示为一个从 $(0,0)$ 到 $(W+1,H+1)$ 的整数坐标网格。

电路板左边缘有 $n$ 个电源，板内还有 $n$ 个用电设备。第 $i$ 个电源位于位置 $(0,h_i)$，第 $i$ 个用电设备位于位置 $(x_i,y_i)$。每个电源必须恰好连接到一个用电设备，反之亦然。

每条导线必须沿着网格线走线，最多只能弯曲一次。即，每条导线要么是一条垂直或水平的直线，要么恰好形成一个 $90$ 度的转弯，构成一个“L”形。导线在路径上的任何位置都不能相互交叉或重叠。

你的任务是确定电源与用电设备之间的一种匹配方案，使得所有导线的总长度最小。

Input Format

输入由以下几行组成：

• 第一行包含三个整数 $W$、$H$ 和 $n$ ($1 \leq W,H \leq 10^8$; $1 \leq n \leq 10^6$)。
• 接下来的 $n$ 行每行包含一个整数 $h_i$ ($1 \leq h_i \leq H$)。
• 接下来的 $n$ 行每行包含两个整数 $x_i$ 和 $y_i$ ($1 \leq x_i \leq W$; $1 \leq y_i \leq H$)。

保证电路板上的每个点最多有一个电源或用电设备。此外，不存在两个用电设备 $i$ 和 $j$ 使得 $x_i = x_j$。

Output Format

如果在给定约束下无法找到这样的匹配方案，则输出一行，包含 $-1$。

否则，输出一行，包含 $n$ 个用空格分隔的整数。第 $i$ 个整数表示 $p_i$，即电源 $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

Hint

翻译由 DeepSeek V3 完成