Hubtown 是一个大型北欧城市，居住着 $n$ 名市民。每天早上，每位市民都希望通过城市中的 $m$ 条通勤列车线路前往市中心的枢纽。每条列车线路都是一条射线（即从市中心出发向一个方向无限延伸的线段），市中心位于坐标 $(0, 0)$。然而，列车线路的容量有限（不同线路的容量可能不同），因此某些线路可能会满载，导致部分市民不得不开车通勤。市议会希望尽量减少开车的人数。为此，他们将发布指令，规定哪些市民可以乘坐哪条列车。

市民总是会选择距离其住所角距离最小的列车线路。但是，如果某位市民恰好位于两条列车线路的中间，他们愿意乘坐其中任意一条，市议会可以决定该市民应该使用哪两条线路中的哪一条。参见图 1 示例。

图 1：样例 1 的说明。虚线箭头表示市民距离最近的列车线路（注意我们测量的是角距离，而非欧几里得距离）。

你的任务是帮助市议会找到一个最大规模的市民子集，使他们能够在早上乘坐列车前往市中心，并确保每位市民乘坐的都是他们距离最近的线路之一，同时不超过任何列车线路的容量。对于这个子集，你还需要输出他们应该乘坐的列车线路。

输入格式

第一行包含两个整数 $n$ 和 $m$，其中 $0 \le n \le 200\,000$ 是市民人数，$1 \le m \le 200\,000$ 是列车线路条数。

接下来的 $n$ 行，每行包含两个整数 $x$ 和 $y$，表示市民住所的笛卡尔坐标。没有市民居住在市中心。

随后是 $m$ 行，每行包含三个整数 $x$、$y$ 和 $c$，描述一条列车线路，其中 $(x, y)$ 是该列车线路经过的一个点（与市中心不同），$0 \le c \le n$ 是该列车线路的容量。该列车线路是从 $(0, 0)$ 出发并经过 $(x, y)$ 的射线。

所有坐标 $x$ 和 $y$（包括市民住所和定义列车线路的点）的绝对值均不超过 $1000$。没有两条列车线路重合，但多名市民可能居住在同一坐标。

输出格式

首先，输出一个整数 $s$，表示能够乘坐列车前往市中心的最大市民人数。然后，输出 $s$ 行，每行对应一名乘坐列车的市民。在每一行中，输出该市民的编号，后跟该市民乘坐的列车线路编号。市民编号从 $0$ 到 $n-1$，按输入顺序排列。列车编号从 $0$ 到 $m-1$，按输入顺序排列。输出行可以以任意顺序给出。

样例

样例输入 1

3 2
2 0
-1 0
-2 -1
1 -1 1
1 1 2

样例输出 1

3
0 1
1 1
2 0

样例输入 2

6 3
1 1
1 1
1 1
-1 1
-1 1
0 1
-1 0 2
0 1 2
1 0 2

样例输出 2

6
0 2
1 2
2 1
5 1
3 0
4 0