题目描述

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

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

在 C 市，两点之间的距离是曼哈顿距离，也就是横纵坐标差值之和。

每个信号塔都有一个半径 $d_i$，表示与 $i$ 曼哈顿距离不超过 $d_i$ 的地方都能被这个信号塔的信号覆盖到。

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

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

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

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

输入格式

第一行两个整数 $n,m$，分别表示信号塔个数与用户总个数。

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

接下来 $m$ 行，每行三个整数 $u,x,y$，表示第 $u$ 号信号塔有一个用户在坐标 $(x,y)$ 的地方。

输出格式

共 $n$ 行，第 $i$ 行两个整数 $(x,y)$ 表示第 $i$ 座信号塔的坐标。

数据保证有解，多解输出任意一种即可。

2 2
2 5
1 6 8
2 11 11 

5 9
6 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

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

数据规模与约定

对于 $100\%$ 的数据，$1\leq n,m\leq 10^5$，$|x|,|y|,|d|\leq 10^6$，$\forall i\in[1,n),d_i\leq d_{i+1}$。