2297 - 信号塔

lanwuni接到一个任务，在C市建立N个信号塔来完成城市中的通讯任务。 假设C市是一个坐标范围[-2000000,2000000]的网格，一些整点上有用户，你也可以在整点上建立信号塔。一个点上可以建立多座。 在C市，两点之间的距离是曼哈顿距离，也就是横纵坐标差值之和。每个信号塔都有一个半径Di，表示与i曼哈顿距离不超过Di的地方都能被这个信号塔的信号覆盖到。 建立信号塔要满足一些性质：

1. 每个信号塔有一定的用户，lanwuni要把信号塔建立在某个地方，使得属于该塔的用户都能被信号覆盖到；
2. 信号塔有一定等级和安装限制，所以，第i号信号塔能覆盖的所有整点，必须也被第i+1号信号塔覆盖到。即使这个整点上没有用户。 现在告诉你每个信号塔的半径，以及每个信号塔的用户，请你帮lanwuni谋划一下应该把这N个信号塔建立在什么地方。

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

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

【数据范围】

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