1860. [国家集训队2011]信号塔

【试题来源】

$2011$ 中国国家集训队命题答辩

【问题描述】

$lanwuni$ 接到一个任务，在 $C$ 市建立 $N$ 个信号塔来完成城市中的通讯任务。

假设 $C$ 市是一个坐标范围 $[-2000000 , 2000000]$ 的网格，一些整点上有用户，你也可以在整点上建立信号塔。一个点上可以建立多座。

在 $C$ 市，两点之间的距离是曼哈顿距离，也就是横纵坐标差值之和。每个信号塔都有一个半径 $D_i$，表示与 $i$ 曼哈顿距离不超过 $D_i$ 的地方都能被这个信号塔的信号覆盖到。

建立信号塔要满足一些性质：

$1$. 每个信号塔有一定的用户，$lanwuni$ 要把信号塔建立在某个地方，使得属于该塔的用户都能被信号覆盖到；

$2$. 信号塔有一定等级和安装限制，所以，第 $i$ 号信号塔能覆盖的所有整点，必须也被第 $i+1$ 号信号塔覆盖到。即使这个整点上没有用户。

现在告诉你每个信号塔的半径，以及每个信号塔的用户，请你帮 $lanwuni$ 谋划一下应该把这 $N$ 个信号塔建立在什么地方。

【输入格式】

第一行 $2$ 个整数 $N$、$M$，分别表示信号塔个数、用户总个数。

第二行 $N$ 个整数，第 $i$ 个数 $D_i$ 表示第 $i$ 号信号塔的半径。

第 $3$ 到第 $N+2$ 行，每行 $3$ 个整数 $U_i、X_i、Y_i$，表示第 $U_i$ 号信号塔有一个用户在坐标 $[X_i,Y_i]$ 的地方。

数据保证 $D_i < D_{i+1}（i<N）$。

【输出格式】

输出包括 $N$ 行，每行 $2$ 个整数，表示第 $i$ 个信号塔的坐标。

数据保证有解。

【样例输入1】

2 2
2 5
1 6 8
2 11 11

【样例输出1】

5 9
6 11

【样例输入2】

6
1 3 5 6 6 7
1 21 27
2 23 27
3 19 27
4 21 33
5 23 29
6 26 30

【样例输出2】

20 27
20 27
19 28
19 29
19 29
19 30

【数据规模和约定】

$30\%$ 的数据中，$1 \leq N,M \leq 10，|X_i|,|Y_i|,|D_i| \leq 50$。

$50\%$ 的数据中，$1 \leq N,M \leq 11$。

$65\%$ 的数据中，$1 \leq N,M \leq 5000$。

$100\%$ 的数据中，$1 \leq N,M \leq 100000，|X_i|,|Y_i|,|D_i| \leq 1000000$。

题目附有 $Special$ $Judge$，对于每个测试点：

如果你输出中坐标绝对值大于 $2000000$，你将得到 $0$ 分；

如果你输出不满足题中所述的性质，你将得到 $0$ 分；否则你将得到 $5$ 分。