题目描述

Hubtown 是一座大型北欧城市，城中有 $n$ 位市民。每天早晨，每位市民都想乘坐通勤列车前往城市中心枢纽。城市中心位于坐标原点 $(0,0)$。

每条列车线路是一条以城市中心为端点、向外无限延伸的射线。不同线路容量可能不同，因此若某些线路满员，部分市民就只能开车。

市议会希望尽量减少开车人数。为此，他们会发布指令，规定哪些市民可以乘坐哪些列车。

一名市民总会选择与自己家方向夹角最小的列车线路。如果市民的方向恰好位于两条线路的正中间，那么他愿意乘坐这两条线路中的任意一条，此时市议会可以决定分配哪一条。

你的任务是找出最多能有多少市民乘坐列车，并给出这些市民分别乘坐哪条线路。分配必须满足：每名被选中的市民只能乘坐离自己最近的线路之一，且每条线路乘客数不超过其容量。

输入格式

第一行包含两个整数 $n,m$：

• $0\le n\le 200000$，表示市民数量；
• $1\le m\le 200000$，表示列车线路数量。

接下来 $n$ 行，每行包含两个整数 $x,y$，表示一名市民家的笛卡尔坐标。保证没有市民住在城市中心。

随后 $m$ 行，每行包含三个整数 $x,y,c$，描述一条列车线路。其中 $(x,y)$ 是该线路经过的一个非原点点，线路为从 $(0,0)$ 出发、经过 $(x,y)$ 的射线；$c$ 表示该线路容量，满足 $0\le c\le n$。

所有坐标 $x,y$ 的绝对值均不超过 $1000$。没有两条列车线路重合，但多个市民可以住在同一坐标。

输出格式

第一行输出一个整数 $s$，表示最多能乘坐列车的市民数量。

接下来输出 $s$ 行，每行两个整数：一个市民编号和一个列车线路编号，表示该市民乘坐该线路。

市民按输入顺序从 $0$ 到 $n-1$ 编号，列车线路按输入顺序从 $0$ 到 $m-1$ 编号。输出行顺序任意。

输入输出样例 #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

输入 #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