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

在电路板的左边界上有 $n$ 个电源，在电路板内部的某个位置有 $n$ 个用电器。第 $i$ 个电源位于位置 $(0, h_i)$，第 $i$ 个用电器位于位置 $(x_i, y_i)$。每个电源必须恰好连接到一个用电器，反之亦然。

每条导线必须沿着网格线延伸，且最多只能弯折一次。也就是说，每条导线要么是一条直的水平或垂直线段，要么恰好进行一次 90 度的转弯，形成一个“L”形。导线在路径上的任何地方都不能相互交叉或重叠。

你的任务是确定电源和用电器之间的一个匹配，使得所有导线的总长度最小。

输入格式

输入包含多行：

• 第一行包含三个整数 $W$、$H$ 和 $n$（$1 \le W, H \le 10^8$；$1 \le n \le 10^6$）。
• 接下来的 $n$ 行，每行包含一个整数 $h_i$（$1 \le h_i \le H$）。
• 接下来的 $n$ 行，每行包含两个整数 $x_i$ 和 $y_i$（$1 \le x_i \le W$；$1 \le y_i \le H$）。

保证电路板上的每个点最多包含一个电源或用电器。此外，不存在两个不同的用电器 $i$ 和 $j$ 满足 $x_i = x_j$。

输出格式

如果在给定的约束条件下无法找到这样的匹配，输出单行，包含 -1。

否则，输出单行，包含 $n$ 个空格分隔的整数。第 $i$ 个整数表示 $p_i$，表示电源 $i$ 连接到用电器 $p_i$。

样例

输入样例 1

5 5 2
2
4
3 2
5 4

输出样例 1

1 2

输入样例 2

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

输出样例 2

2 4 5 3 1