UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#2297. 信号塔

统计 下载数据

Description

lanwuni接到一个任务,在C市建立N个信号塔来完成城市中的通讯任务。
假设C市是一个坐标范围[-2000000,2000000]的网格,一些整点上有用户,你也可以在整点上建立信号塔。一个点上可以建立多座。
在C市,两点之间的距离是曼哈顿距离,也就是横纵坐标差值之和。每个信号塔都有一个半径Di,表示与i曼哈顿距离不超过Di的地方都能被这个信号塔的信号覆盖到。
建立信号塔要满足一些性质:
1.       每个信号塔有一定的用户,lanwuni要把信号塔建立在某个地方,使得属于该塔的用户都能被信号覆盖到;
2.       信号塔有一定等级和安装限制,所以,第i号信号塔能覆盖的所有整点,必须也被第i+1号信号塔覆盖到。即使这个整点上没有用户。
现在告诉你每个信号塔的半径,以及每个信号塔的用户,请你帮lanwuni谋划一下应该把这N个信号塔建立在什么地方。

Input

第一行2个整数NM,分别表示信号塔个数、用户总个数。
第二行N个整数,第i个数Di表示第i号信号塔的半径。
第3到第M+2行,每行3个整数UiXiYi,表示第Ui号信号塔有一个用户在坐标[Xi,Yi]的地方。
数据保证Di<=Di+1(i<N)。

Output

输出包括N行,每行2个整数,表示第i个信号塔的坐标。
数据保证有解。

Sample Input

【样例输入一】
2 2
2 5
1 6 8
2 11 11

【样例输入二】
6 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

Sample Output

【样例输出一】
5 9
6 11

【样例输出二】
20 27
20 27
19 28
19 29
19 29
19 30

Hint



【数据范围】

100%的数据中,1<=N,M<=100000,|Xi|,|Yi|,|Di|<=1000000。

Source

鲁逸沁 鸣谢Benz提供SJ程序!