#2297. 信号塔

题目描述

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到第 M +2行，每行3个整数 U i、 X i、 Y i，表示第 _U i_号信号塔有一个用户在坐标[ X i, Y i]的地方。

数据保证 D i<=Di+1（i<N）。

输出格式

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

数据保证有解。

样例

样例输入

【样例输入一】  

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  

样例输出

【样例输出一】  

5 9  

6 11  

  

【样例输出二】  

20 27  

20 27  

19 28  

19 29  

19 29  

19 30  

数据范围与提示

【数据范围】

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